Monday, August 8, 2011

Un-Locking Prior Knowledge

I enjoy mathematics in the morning. It wakes my brain up, and makes my coffee that much more comforting. Much of the deliberate mathematics learning that I do takes place in the morning. I say deliberate, because mathematics always finds ways to sneak itself into all parts of my day. Morning is just when I open the door and embrace the learning with open arms. 

Today's dose came courtesy of @republicofmath via @jamesgrime. The problem took longer than I expected, but the result was quite eloquent. I ended up using a method that I had no intention of ever using again. It was the use of this prior knowledge that made the experience valuable. 

The problem is paraphrased as follows:

A lock consists of three reels. Each one is numbered 1-3. You can move reels 1 and 2 together, and you can move reels 2 and 3 together. No reel can move independently. If the combination begins at 333, what series of moves will result in the code 221?

For example, if you chose to move the left-hand reels one spot forward, the combination would then read 113, because both reel 1 and 2 would reset to 1. 

Initially, this is how I began to familiarize myself with the problem. I tried a couple of moves just to see if the solution was obvious. After the trial-and-error approach failed, I took to a more systematized approach. Sticking to Polya's iconic approach, I had to first understand the problem before I could devise a plan. The trial and error allowed me to understand the patterns and environment involved. 

I then had to devise a plan. I did so, but it did not work straight away. I thought that I could work backwards to the solution. If I began with the goal in mind (221) and then performed all of the possible moves (Turn Left or Turn Right), I would eventually land on 333. I would then re-trace my steps back up the path I created. Because of the cyclical nature of the lock, I assumed all moves were forwards. So if I turned right, 213 would become 221. This strategy is shown in the picture below.


I soon found that values were repeating, so I pruned their branches so not to become redundant. After about 10 minutes, I began to get more redundancies than new pathways, and I abandoned the approach. The next attempt was very similar, but with a subtle twist.

I placed 221 in the middle and recognized all four moves (Left +, Left -, Right +, and Right -) as valid. The only change was that I allowed forward and backward turns to be valid. It only took one iteration to realize that this new approach was going to be as unfruitful as the last, and it was abandoned. The first step is shown below:


At this point, I was seriously doubting if there was a solution, and knew the only way to prove the absence of a solution would be the abstract case. I labeled each reel A, B, and C, and began to list a set of possible moves that one could turn A, B, and C.

In invented a notation to go along with this procedure. If a reel moved forward 1 spot (like from 2 to 3) it was given a +1. If it moved 2 spots forward, it was given a +2. Etc.

From this I began a list of moves:

(1) +1A +1B  C -->Was moving the left reel one spot
(2) A +1B +1C --> Was moving the right reel one spot

From here I created the only 5 viable moves:

(3) +1A +2B +1C --> Moving left and right
(4) +1A B +2C --> Moving right forward and left backward
(5) +2A B +1C --> Moving left forward and right backward


Because of the cyclical nature of the lock, a -1 would be equal to a 2. Because if you started at a neutral position and moved -1, you would land at the same position as if you moved +2. Essentially, the moves were all taken modulus 3. This notation was far too complicated to continue. I had to eliminate the letters to create this list of 5 possible combinations of moves:

(1) 110
(2) 011
(3) 121
(4) 102
(5) 201

 
I then investigated all possible combinations of the moves and the solution came to life. I began by applying every move twice in succession. So applying (1) twice resulted in:

110 + 110 = (6) 220

This was a new result, and had to be added as number (6) to the list. After the original 5 were tested, 3 more created unique entries.

(7) 022
(8) 212


The next part took the most time. I tested every two move combination to see whether it created a unique move. As evidenced by the diagram, each one failed to create a unique pattern. (the attempt is marked with an ‘x’ if is was a repeat.)



It was then when the prior knowledge became unlocked:

I had created a mathematical group of 9 elements. There was no way of applying the elements in sequence that would break the group.

I honestly never thought I would use Abstract Algebra again, but it was a pleasant surprise to have to utilize it. The new group, G, consisted of 9 elements. The aforementioned (8) and an identity element (000) which represented not moving the reels at all. I quickly tested the requirements of a group:

There must be an identity
Operations have to be associative
There must be closure
Each element must have an identity

The operation is piecewise addition modulo 3. This is associative. The identity was mentioned earlier, and the combination calculations showed closure. This was a group whose members represented turns of a wheel.

So the question became, if you start at 333, can you get to 221? 333 is our neutral position. In order to get to 221, we need to turn reel 1, two places, reel 2, two places, and reel 3, one place. I am looking for the element 221 to be included in the group in order to unlock the lock. It, however, is not, and so this problem is impossible.

The only possible combinations that are viable are those included in the group. (pictured above).

Now the point of the problem was not the solution. (although I enjoyed the finality after about an hour of work). The joy came when I unlocked prior knowledge to solve the problem. It encouraged me to know that along my mathematical journey, I have encountered various methods. The real powerful math comes when I can apply a method because of a deep understanding of it. The repetitive, one-dimensional problems given to me in university did not result in satisfaction; I had to use it flexibly in order for Groups to become mathematically potent. I think all teachers of mathematics should have to struggle with a problem for a while. It gives valuable insight to the students’ viewpoint. Sometimes teachers forget how difficult it is to struggle.

NatBanting

2 comments:

  1. My challenge is, can you explain it in a tweet.

    Given the restrictions, this was mine:

    "D1 turns (2 + 3m). D3 turns (1 + 3n). So D2 turns (2 + 3m) + (1 + 3n) - which is a multiple of 3 and so can't be 2."

    ReplyDelete
  2. jim: Well done. As I am sure you can tell from my post, it took me a lot more effort to get there. You must know how excited I am to see the problem solved in another way. As is usually the case with mathematics: solutions come and go, but notation is king! Since I joined Twitter I have found that most of my conversations occur in 140 characters or less; this is a fact that my wife is probably not all pleased about! Thanks for reading; it is greatly appreciated.

    ReplyDelete