An idea for the classroom - Adam's Move
This is an exploration that provides excellent opportunities for students to generalise, and express their generalisations concisely, possibly using conventional notation.
The starting point is a puzzle from Henry Ernest Dudeney.
The most effective way to introduce the puzzle is to challenge the class to solve it by acting it out.
Push all the tables to the edge of the classroom, and arrange chairs in rows to form a rectangle. For example, arrange them in four rows of five chairs. Students sit on the chairs, leaving the chair at one end of the front row empty. The student on the chair at the corner diagonally opposite to the empty chair is special, and is called ‘Adam’:
The aim is to get Adam home (into the initially empty chair in the diagonally opposite corner) in the least number of moves. A student may move into an empty chair that is next to the chair he is on, either to the left or right, or in front or behind. A student cannot move into an empty chair that is next to him diagonally:
Students are unlikely, at their first try, to get Adam home in the least number of moves. Therefore they will need to have several attempts, before some students begin to see a system that leads them to the minimum number of moves, which is 25.
It is essential to allow students to discover for themselves a sequence of moves constituting a solution.
They will eventually find that it can be viewed as a three-stage process, which is described in the four paragraphs below. You may prefer not to read this before exploring the puzzle yourself.
In the first stage students move, one at a time, until the empty chair is in one of the two positions that enable Adam to move. The least number of moves required to do this is six. There are 35 different ways of doing it – 20 valid routes to one of the two possible positions of the empty chair, and 15 routes to the other.
The second stage consists of the one move of Adam into the empty chair in one of the two possible positions.
In the third stage, Adam is moved along one of the shortest routes home. Each of the six steps requires three moves in which students rotate round a 2x2 square, either clockwise or anti-clockwise.
The minimum number of moves is therefore 6 + 1 + 3 x 6. It is helpful to record the number of moves in this way in order later to make generalisations, in attempts to express the minimum number of moves for an n by m rectangle algebraically.
Once students have solved the puzzle for four rows of five chairs, they should rearrange the chairs into a different rectangular array, and again endeavour to work out a solution physically by moving themselves around according to the rules. This will take some time.
For many rectangular arrangements of chairs, any minimum set of moves includes an extra last stage, in which Adam’s movement through the last few positions of a shortest route home is in steps of five student moves. This is necessary in order to move Adam to his left when the empty chair is on his right.
While the classroom is clear of desks, students should try to solve the problem for as many different rectangular arrays of chairs as time allows. Later, they can begin to get to grips with the exploration using counters or coins placed on square grids.
The challenge is to find a general statement of the minimum number of moves required for any rectangle in terms of the number of rows and columns of the rectangle.
Encourage students to express any generalisations at which they arrive, at first in words, and then, possibly, algebraically with the number of rows and the number of columns as the variables.
It is important that students keep careful records of their findings. Encourage them to make predictions, and then check them out.
It is relatively easy to arrive at a generalisation for square arrays.
For example, a student showed, in her writing about her findings, how she used her understanding of the common structure of solutions to arrive at an algebraic expression, which she then tested on new examples. She drew sketches showing the positions of ‘people’ (which were actually counters) after each move for 2-by-2, 3-by-3 and 4-by-4 grids. Then she wrote: “I predict that the minimum number of moves in a 5 by 5 puzzle will be 7 + 1 + 7 x 3 = 29. Correct! I think the minimum number of moves in an n by n puzzle is the sum of the n-1th odd number, 1, and the n-1th odd number times 3.”
Understanding, and expressing as generalisations, what is happening in non-square rectangular puzzles is more challenging. However, by being systematic, for example by investigating 2 by n puzzles, then 3 by n puzzles, then 4 by n puzzles, and so on, students will be able to make modest generalisations.
For example they should be able to deduce that:
- for n by 3 puzzles and n > 3, the minimum number of moves is 6n – 5
- for n by 4 puzzles and n > 4, the minimum number of moves is 6n – 3
- for n by 5 puzzles and n > 5, the minimum number of moves is 6n – 1.
Encourage students to write very detailed, illustrated and comprehensive, reports of all their findings.