ENRICHMENT RESOURCE: THINKADOT ALGEBRA

Presented by: Richard Singer, Edition Date 1/2005

F. Richard Singer III

Website and Email: http://www.conceptualstudy.org

Prerequisites: This resource assumes you are familiar with the Think-a-dot device and its puzzles. If you have not solved some of these then go to the puzzle page. The main mathematical background needed is an understanding of the concept of function composition and the concept of solving equations in Z₈. What you need to know about Z₈ is covered in the appendix.

Overview: The main part of this resource is a Type 3 constructivist learning resource, as conceptualized in the paper Constructivist Learning Resources. The supplement is a Type 2 resource in which a fictional cast of characters uses the activities as a Type 1 resource. The purpose of these resources is to provide a broader perspective on algebraic equations and operations than the one usually encountered in ordinary algebra. Specifically the activities show how an understanding of either function algebra or the algebra of the ring Z₈ can be used to analyze questions related to Think-a-dot puzzles.

Reference for Main Notation:

• P: set of patterns that can be obtained from the initial pattern on the thinkadot device
• Z₈: the cyclic ring (mod 8)
• Å : addition (mod 8) in the main part of this resource
• +: ordinary addition in some contexts
• +: function composition in some contexts
• 0: either the number 0 or the identity function on P
• f: the function on P corresponding to a marble drop in left hole
• g: the function on P corresponding to a marble drop in middle hole
• h: the function on P corresponding to a marble drop in right hole
• D: the set of functions generated by composing {f, g, h}
• Î : belongs to a set

SECTION 0 THE PROBLEM

The Think-a-Dot Device: Recall that this device has three holes at the top thru which a marble can be dropped. It then falls thru gates inside the device, each set to send the marble left or right. As a marble goes thru a gate, it sets the gate in the opposite direction. A blue dot shows that a gate is set to send a marble left. A pink dot shows that a gate is set to send a marble right. A marble does not hit a gate in the middle level when dropped thru a side hole whose gate in the top level is set toward the wall. For a puzzle, we always start with the initial pattern with all dots blue, so all gates are set to the left. However we will also consider the effects of marble drops on other patterns. f, g, h denote functions for the marble drops thru the left hole, middle hole, right hole respectively. The diagram below shows what you would see from the sequence f, g, h if you start with the initial pattern.

The unseen inside gate settings are as follows.

Since any setting can be in one of 2 states, it is convenient to think of bits rather than colors. A zero indicates that a gate is set so marble goes left. A one indicates that it is set so marble goes right. Thus you can think of the result of applying these marble drops in terms of these bit patterns.

Activity 0a: Show the bit patterns which result from applying the sequence g,g,h,h,f. Altho the sequence f,g,h,h,g gives different intermediate patterns, these two sequences both yield the pattern 100 10 010. Discuss whether or not you think any sequence using f once and both g and h twice on the initial pattern will yield 100 10 010.

Activity 0b: Clearly the sequence f,h will have the same effect on any gate in the top row as the sequence h,f. Explain why these sequences will have the same effect on any gate in the second row. Explain why they sequences have the same effect on gates in the third row. Do the h,g and g,h have the same effect on any pattern? Explain. What about f,g and g,f?

Notation: Since it is only the number of marble drops thru each hole that matters, we can represent marble drops by a triple of natural numbers rather than by a sequence.

[n,k,m] denotes n drops thru the left, k drops thru the center, m drops thru the right.

Activity 0c: Explain why [2,2,2] always results in the same pattern to which you applied it.

Activity 0d: After a marble drop there is always exactly one bit change in the top row. Is this also true of the second row? What about the third row. Explain why 100 00 000 is not in P. Find some other imaginable patterns that are not in P.

Main Problem: P denotes the set of patterns that can be obtained by marble drops. Give simple criteria for determining when a pattern is in P. For any pattern in P, determine a triple that produces this pattern.

Optional Problem 1: For any x in P, give a minimal triple for x, i.e. a way which uses the minimum number of drops needed to obtain x. Given any other natural number j, determine if x can be obtained using exactly j marble drops. If so, give such a triple. See ?? for a solution to this problem.

Optional Problem 2: Let y and x be any patterns. Give a simple way to determine if there is a triple that changes y to x. Indicate a way to find the smallest number s of drops needed to obtain x from y a triple that does this. Given any other natural number j, determine if x can be obtained from y using exactly j marble drops.

Optional Problem 3: Let yÏP. Investigate which patterns can be obtained by application of marble drops D to y, and how they can be obtained.

Notation: We use additive notation for D, with left to right convention for composition. Thus g+f means do g then do f, while f+g means do f then do g. We also use the standard additive abbreviations.

0: the identity function

nx: n applications of any xÎ{f, g, h}.

Overview: Section 1 presents a top down strategy for making patterns in P. It is based on some observations about the effects that various numbers of drops thru a single hole will have on gate setting in each of the levels. It uses such observations to determine algebraic properties of D and use these to determine which patterns are in P and how to use marble drops top obtain them. The top down strategy does not allow us to predict a sequence that will produce a pattern dropping any marbles. Section 2 uses a code from Z₈ to represent half of the patterns in P. The activities indicate how to determine a simple Z₈ formula for using multiples of f and h on these patterns. They then focus on the effect of using of g exactly once. Unlike the strategy from Section 1, this allows us to calculate the marble drops needed to make a pattern prior to dropping any marbles.

Section 1 and Section 2 are independent of each other and can be done in either order.

SECTION 1 TOP DOWN STRATEGY

Remark: This section focuses on a simple top down strategy for making any possible pattern. This means a strategy that will yield any desired top row, then any desired second row with that top row, and finally any desired third row with those top and second rows. Before looking at the activities, see if you can find such a strategy. You may want to use the puzzle device to help you formulate such a strategy.

Activity 1a Explain how to obtain any pattern of upper level bits by using some subset of {f,g,h}. Indicate how use of an even number of drops thru any hole will effect the upper level bit pattern.

Activity 1b: Starting with any pattern, explain the effect 2f will have on the top row and the second row. Do the same for 2h and 2g.

Activity 1c: Explain the effect of 4f on each gate. Do the same for 4h and 4g.

Activity 1d: Explain the effect of 8f. Do the same for 8h and 8g.

Application: Using the information from these activities we can obtain the pattern 100 11 111. Starting with 000 00 000, to obtain 100 we need to change the left bit, so begin with f. After this, we have 100 00 100. Since the middle both bits differs from the desired ones, we can use 2g leaving the top bits alone but reversing both middle bits. After f+2g we have 100 11 010. Now the left and right lower bits differ from the desired ones. 4g changes these 2 bits but leaves all others alone. Thus f+2g+4g will give this pattern, and so [1,6,0] is a triple we can use.

Activity 1e: Apply a strategy like the above to find a triple giving 111 00 010.
Do the same for 101 11 011 and for 001 11 010.

Activity 1f: Before reading the strategy below, see if you can describe a strategy.

Top Down Strategy: The strategy used above can be used to find a function for making other patterns in which the Z₂ sum of the top and lower bits is 0.

(Step 1) Use some subset of {f, g, h} to obtain the desired top bits.

(Step 2) Do nothing or use one element of {2f, 2g, 2h} to obtain the desired second row.

(Step 3) Do nothing or select an element of {4f, 4g, 4h} to change 2 bits in the last row.

Activity 1f: Find a pattern that cannot be obtained from the initial pattern by the top down strategy. Do you think the pattern you found can it be obtained from the initial pattern by marble drops?

Activity 1g: Observe that any marble drop must change a bit in the first row and a bit in the third row. Explain why this implies that 100 00 000 is not in P. Look at the pattern you found that could not be obtained by the top down strategy, and explain why it is not in P. Find other imaginable patterns that are not in P. How many imaginable patterns are not in P?

Activity 1h: Determine how many different patterns can be obtained from the initial pattern using the top down strategy? Does the top down strategy give all patterns in P? Explain.

Algebraic Properties of D: From earlier activities we have 2f+2h+2g = 0, 8f = 0, 8g = 0, 8h = 0. The application below suggests how these properties can be related Optional Problem 1.

Application: Earlier we saw that the triple [1,6,0] of 7 drops gives the pattern 100 11 111. This triple corresponds to the function f+ 6g. Since 2f+2h+2g = 0 & 8g = 0, we can also represent this function as 3f+2h. This gives the triple [3,0,2] of 5 drops which can be used to obtain this pattern. [5,2,4] or [7,4,6] could also be used. There are additional ones using more than 7 drops thru the same hole, such as [9,6,0], but clearly none of these can be minimal. You might want to convince yourself that no fewer drops than 5 give 100 11 111. Similar analysis gives four triples to obtain the pattern 111 00 010. The top down strategy gives [1,3,5]. We can also use [3,5,7] or [5,7,1] or [7,1,3]. Of these the top down strategy gave the one with the fewest drops. You might want to convince yourself that no fewer drops than 9 give 111 00 010.

SECTION 2 CALCULATING THE EFFECT OF MARBLE DROPS

Remark: The focus of this section is to find Z₈ formulas for calculating the effects of f and h. This will allow us to obtain 64 of the possible patterns. Using one application of g along with these formulas will allow us to obtain 64 more patterns.

A Code for P: For a pattern in P, the number of ones in the top row plus the number of ones in the third row is odd. In other words the Z₂ sum of the bits in the top and lower rows is 0 for any x in P. Thus the center lower bit is the Z₂ sum of these other five bits, and so we can ignore this bit when trying to obtain a pattern. This is convenient because it is the only bit affected by all types of marble drops. We can focus only on the left bits when examining the effect of a drop thru the left hole. Likewise, we can focus only on the right bits when examining the effect of a drop thru the right hole. One compact way to describe the effects of f is to think of the left bits as binary codes for numbers in Z₈. To be specific, code each blue dot with a zero. Code each pink dot in the top level as a one, a pink dot in the middle level as a two, a pink dot in the bottom level as a four. We then add the left side bits, giving a number in Z₈. A similar remark applies to the right side bits. For now we ignore the center bit in the top row and focus only on patterns where this dot is blue, and we code any such pattern as a pair [a, c] from where aÎZ₈ & cÎZ₈. Later we will add the letter b to code the center top bit.

Example: The red and blue fonts are used below to help focus on the bit being coded.

[6, 5] = [0+2+4, 1+0+4]

This means that the left bits are 011 and the right bits are 101. Thus [6, 5] codes 001 10 111. The center top bit is 0 since those are the only patterns being coded as pairs. The center lower bit is 1 because of the bit sum condition.

Activity 2a: Decode the following triples as bit patterns: [0, 0], [5, 2], [2, 3]

Strategy For Main Problem Part 2: Using this code, we can obtain a Z₈ formula for calculating the effect of f. To do this, see what happens when apply multiples of f to [0, c]. Activity2b gives a detailed hint. Use a similar strategy to find a formula for the effects of h. Next find a formula for calculating the effects of nf+mh. Use this to give a formula that would yield a marble drop for any pattern in which the center top dot is blue.

Notation: To distinguish addition for functions from addition for Z_8, we use Å for Z₈ addition.

Activity 2b: Find a Z₈ formula for f[a, c]. Hint, look at f[0, c], f[5, c], f[2, c], etc.
Also find a Z₈ for h[a, c].

Activity 2c: Show f+h = h+f

Formulas for f and h: Below we list the formulas for f and h along with a formula that can be derived from them for using multiples of f and h.

f[a, c] = [aÅ5, c] h[a, c] = [a, cÅ3] (nf+mh)[a, c] = [aÅ5n, cÅ3m]

Using f and h: Using (nf+mh)[0, 0] = [5n, 3m], we determine how to obtain any pattern whose top middle bit is 0. For example, to obtain 000 11 110, first code it as [6, 2] and then solve the Z₈ equations below.

5n = 6 & 3m = 2.

This gives n = 6 and m = 6, so we can use 6f+6h. Latter we will see that using fewer marble drops could be used.

Activity 2d: Tell how to make each of the patterns below using marble drops only f and h.

100 11 111 001 10 001 100 10 001 000 00 101

Activity 2e: Use (nf+mh)[0, 0] = [5n, 3m] to show that ((5a)f+(3c)h)[0, 0] = [a, c].

The Remaining Patterns: In order to examine the patterns for which the center top dot is pink we extend the code to a triple [a, b, c] where a and c are as before and b is 0 or 1 depending on whether this dot is blue or pink. Since g[0, 0, 0] = [6, 1, 0] we can obtain any pattern in which the top middle dot is pink by using g and then using only combinations of f and h.

Activity 2f: Write a formula for (g+nf+mh)[0, 0, 0]

Remark: Activity2e shows how to obtain any element in P of the form [a, 0, c]. Use the result from Activity2f to give a formula for obtaining [a, 1, c] from [0, 0, 0].

We need 5n Å 6 = a & 3m = c. Thus n = 5a Å 2 & m = 3c.

This gives (g+(5aÅ2)f+(3c)h)[0, 0, 0] = [a, 1, c]

Main Problem: These activities give the formulas below showing a way to obtain any of the 128 patterns of the form [a, b, c]. So P consists of the 128 patterns for which the bit sum of the top and lower bits is 0. This solves the main problem.

((5a)f+(3c)h)[0, 0, 0] = [a, 0, c] ((5a Å 2)f+(3c)h+ g)[0, 0, 0] = [a, 1, c]

Remark: The above formula does suggest using the center hole to obtain patterns of the form
[a, 0, c]. For example, it gives (6f+ 6h)[0, 0, 0] = [6, 0, 2], suggesting 6 drops thru the right hole and 6 drops thru the left hole. However 2 drops thru the center hole gives the minimal way to produces [6, 0, 2].

Formulas for g: If the center top dot and the left middle dot are both blue then g changes the value of the left middle dot to pink and switches the bottom left dot. If the center top dot is blue and the left middle dot is pink then g changes the value of the left middle dot to blue and leaves the bottom left the same. In either case, the effect on the code is to add 6 modulo 8.

Thus g[a, 0, c] = [a Å 6, 1, c].

Similar reasoning yields g[a, 1, c] = [a, 0, c Å2]

Together they give a formula for 2g, namely 2g[a, b, c] = [a Å6, b, c Å2].

Remark: Since (6f+6h)[a, b, c] = [a Å6, b, c Å2], we have 2g = 6f+6h. Given this result, it is easy to see why 3g give the same result as g+6f+6h.

Results About D: The formula for marble drops can be used to derive the same results about D as were derived in Section 1. From the formulas for f and h we have 8f = 0 & 8h = 0. The formula for 2g shows that 8g = 0. We can also show that addition of functions in D is commutative. We have already shown f+h = h+f. The cases below show f+g = g+f, and the proof of h+g = g+h is similar.

(f+g)[a, 0, c] = g[a Å5, 0, c] = [a Å3, 1, c] = f[a Å6, 1, c] = (g+f)[a, 0, c]

(f+g)[a, 1, c]=g[a Å5, 1, c] = [a Å5, 0, c Å2] = f[a, 0, c] = (g+f)[a, 1, c]

Activity 2g: Using 2g = 6f+6h, show that 2f+2g+2h = 0.

The supplement below is a Type 2 resource in which a fictional cast of characters
uses the thinkadot activities as a Type 1 resource.

Supplement: A Fictional Account of Using the Activities

At present this supplement is not Available.

Re0a:

000 00 000

h ®

001 01 010

h ®

000 01 011

f ®

100 01 111

g ®

010 11 011

g ®

100 10 010

Re0b: Since each marble drop must change exactly 1 gate in the top level and exactly 1 gate in the lower level, the Z₂ sum of these 6 bits remains 0 no matter how many marble drops are used. This gives a necessary condition for patterns in P:

If xÎP then the bit sum in the top and lower levels is 0 in Z₂.

There are 8 gates, giving 2⁸ = 256 imaginable patterns. Since exactly half of these imaginable patterns have 0 for the Z₂ sum of the top and bottom levels, P has at most 128 elements. Ac00 gave an example of a pattern in P for which the Z₂ sum of all 8 gates is not 0.

Activity 2a: Decode the following triples as bit patterns: [0, 0], [5, 2], [2, 3]

Re2a: [0, 0]: 000 00 000 [5, 2]: 100 01 100 [2, 3]: 001 11 010

Activity 2b: Find a Z₈ formula for f[a, c]. Hint, look at f[0, c], f[5, c], f[2, c], etc.
Also find a Z₈ for h[a, c].

Re2b: f[0, c] = [5, c], f[5, c] = [2, c], f[2, c] = [7, c], f[7, c] = [4, c], f[4, c] = [1, c], f[1, c] = [6, c],
f[6, c] = [3, c], f[3, c] = [0, c]. Observe that for each aÎZ₈ we have f[a, c] = [aÅ5, c]. Starting with [a, 0] and applying h, the second member of the pairs becomes 3, 6, 1, 4, 7, 2, 5, 0. Thus h[a, c] = [a, cÅ3]

Activity 2c: Show f+h = h+f

Re2c: (h+f)[a, c] = f[a, cÅ3] = [aÅ5, cÅ3] = h[aÅ5, c] = (f+h)[a, c], so f+h = h+f.

Activity 2d: Tell how you could make each of the patterns below using marble drops only f and h.

100 11 111 001 10 001 100 10 001 000 00 101

Activity 2e: Use (nf+mh)[0, 0] = [5n, 3m] to show that ((5a)f+(3c)h)[0, 0] = [a, c].

Activity 2f: Write a formula for (g+nf+mh)[0, 0, 0]

Activity 2g: Using 2g = 6f+6h, show that 2f+2g+2h = 0.

Re2d: 3f+2h, 2f+7h, 7f+5h, 4f+4h.

Re2e: nf+ mh[0, 0] = [a, c] Û [5n, 3m] = [a, c] Û a = 5n & c = 3m Û n = 5a & m = 3c

Re2f: (g+ nf+ mh+ g)[000] = g[6, 0, 0] = [5n Å 6, 1, 3m]

Re2g: Since 2g = 6f+6h, 2g+2f+2h = 6f+6h+2f+2h. Now use the fact that D is abelian and that 8f = 0 and 8h = 0.

Appendix Cyclic Rings

Rings: The laws below are satisfied not only by various numerical structures, such as the integers, but also by a variety of other algebraic structures have similar operations. Structures that satisfy such laws are called commutative rings. The ring of integers is denoted as Z.

1. a+b = b+a & a· b = b· a Commutative Laws

2. (a+b)+c = a+(b+c) & (a· b)c = a· (b· c) Associative Laws

3. 0+a = a & 1·a = a Identity Laws

4. -a+a = 0 Additive Inverse Law

5. a· (b+c) = (a· b)+(a· c) Distributive Law

A cyclic ring is a finite commutative ring whose elements can be generated from 1 by addition. This means that a finite list of the form 1, 1+ 1, 1+ 1+ 1, 1+ 1+ 1+ 1, … gives all elements of the ring.

The Cyclic Ring Z₆: The mod 6 operations {+ , · } for the set {0, 1, 2, 3, 4, 5} are indicated in the tables below. We will later show that this set with these operations is a ring, which we denote as Z₆. Z₆ is a cyclic ring, since 2 = 1+ 1, 3 = 1+ 1+ 1, 4 = 1+ 1+ 1+ 1, 5 = 1+ 1+ 1+ 1+ 1, 0 = 1+ 1+ 1+ 1+ 1+ 1.

One way to think of these operations is to imagine Z6 arranged as in a clock. To obtain x+ y mod 6, start at x and move y positions clockwise. To obtain x· y mod 6, start at 0 and move y positions clockwise x times.	0 5 1 4 2 3	+	0 1 2 3 4 5	·	0 1 2 3 4 5
		0 1 2 3 4 5	0 1 2 3 4 5 1 2 3 4 5 0 2 3 4 5 0 1 3 4 5 0 1 2 4 5 0 1 2 3 5 0 1 2 3 4	0 1 2 3 4 5	0 0 0 0 0 0 0 1 2 3 4 5 0 2 4 0 2 4 0 3 0 3 0 3 0 4 2 0 4 2 0 5 4 3 2 1

As a minor illustration using the cyclic Z₆ ring, we will solve the puzzle below. Most of this resource will focus on applications that are more significant.

Tea Party Puzzle: Ms Army, Ms Banjo, Ms Clay, Ms Dumont, Ms Far, Ms Grey had a tea party. They were seated at a circular table. One of these women was pretty, one realistic, one slim, one talkative, one unreliable, one quiet. Ms Banjo sat opposite the unreliable one. The pretty one sat opposite Ms Clay, who sat between the quiet one and the unreliable one. The slim one sat opposite Ms Army, next to the pretty one, to the left of the unreliable one. Ms Far sat between the realistic and the slim one. Ms Grey sat to the right of Jan who was opposite the talkative one. Who is Jan?

Solution Using Z₆: Let {a, b, c, d, f, g} be the positions occupied by the women whose last names start with those letter. Let j be the position of the woman whose first name is Jan. Let {p, q, r, s, t, u} be the positions occupied by the women whose characteristics start with those letter. Clues involving the relations ‘left of’ or ‘opposite’ are easily translated using mod 6 addition. That s is left of u translates as s = u+1, that b is opposite u as b = u+3, etc. The translation of ‘x is between y and z’ is more subtle. Check some instances to see that this implies y+ z = 2x. The tea party information gives the following equations, along with a multitude of inequalities such as g ¹ c.

b = u+ 3, p = c+3, q+ u = 2c, s = a+3, s = u+1, p = s+1, r+ s = 2f, j = g+1, j = t+3

Since s occurs in more equations than any other variable, it is convenient to label the seat occupied by s as 0. This gives s = 0, u = 5, p = 1, r = 2f, a = 3, b = 2, c = 4, q = 3. If t = 2 then g = 4. However c = 4, so t ¹ 2. This leaves t = 4 & r = 2. From this, j =1, f = 1, j = f. Thus Jan is Ms Far. You can check to see that using any other value for s also gives j = f.

Modular Operations: When dividing whole numbers, we can think 25 divided by 8 as having a quotient of 3 and a remainder of 1, and 24 divided by 8 as having a quotient of 3 and a remainder of 0. Etc. Altho many applications of whole number focus on quotients, there are also reasons to focus on remainders. We use the notation  ₈x for the remainder when x is divided by n. One way to calculate x· y mod 6 is to multiply as usual and then take the remainder, i.e. to obtain 5· 5 = 1 mod 6, use  ₆25 = 1. A similar comment applies to calculating x+ y mod 6. This generalizes easily to give a cyclic ring Z_n for each positive integer n. To focus attention on an operation being a mod n operation we use a subscript of n with the operation symbol. When it is clear from context that we are using a modular operation (and also which modular operation) we will not use a subscript. The convention of ordinary algebra for omitting the multiplication signs and parenthesis will be used for modular operations.

The mod n operation +_n and · _n are defined as follows: x+ _ny = Â_n(x+ y) & x· _ny = Â_n(x· y)

For example, the mod 7 operations {+ 7, · 7} for the set Z7 = {0, 1, 2, 3, 4, 5, 6} are given in the following tables. One way to think about remainders is think of how we check the results of dividing. For example, to check that 25 divided by 7 has a quotient of 3 and a remainder of 4, we take 3 times 7 and add 4. 25 = 3· 7+ 4	+ 7	0 1 2 3 4 5 6	· 7	0 1 2 3 4 5 6
	0 1 2 3 4 5 6	0 1 2 3 4 5 6 1 2 3 4 5 6 0 2 3 4 5 6 0 1 3 4 5 6 0 1 2 4 5 6 0 1 2 3 5 6 0 1 2 3 4 6 0 1 2 3 4 5	0 1 2 3 4 5 6	0 0 0 0 0 0 0 0 1 2 3 4 5 6 0 2 4 6 1 3 5 0 3 6 2 5 1 4 0 4 1 5 2 6 3 0 5 3 1 6 4 2 0 6 5 4 3 2 1

In general, to check the results of dividing m by n, take the quotient times n and add the remainder, checking to see that the result is m. Also make sure the remainder is less than n and greater than or equal to 0. This idea can be used to define the mod n remainder function for any positive integer n.

Â_nm = m- qn, where qn is the largest multiple of n that is less than or equal to m.

Solving Equations in Z₈: