________________
________________
Great
48
One group of students starts in the middle of the country, in Wichita, Kansas. To make the trip more interesting, they decide to visit each of the 48 contiguous states exactly once. That is, they plan their route so that once they have driven out of a state, they do not cross back into that state again (at least, not until they have completed their trip by visiting all of the states).
In which state does their planned route end?
Southern Circuit
Another group from the team plans a Southern tour, visiting Alabama, Arkansas, Florida, Georgia, Kentucky, Louisiana, Mississippi, Missouri, North Carolina, South Carolina, Tennessee, Virginia, and West Virginia. However, they choose a route that makes every possible crossing from one of these states into another one of these states, going in one direction or the other (but not both directions) across every border between two of these states, exactly once each. (This of course involves visiting some of the states more than once.) They start their trip on the coast.
In which state do these students end up?
| Spread the word: | Tweet |
Solutions to week 92
Sort of Hanoi-ing. First, it will be convenient to have a table of the number of moves it takes to solve the usual Tower of Hanoi puzzles with 1 to 4 disks. You can verify these numbers by trial and error, look them up, or just notice that to solve n disks, you have to move the top n-1 disks, move the nth disk, and then move the top n-1 disks back on top of the nth, so that it takes twice as many moves plus 1 to solve n disks as it does to solve n-1.
| disks | moves |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
Now we will consider the problem of converting an unsorted stack into a sorted one. We will use capital letters like P,Q,R,… to stand for piles of one or more disk, and lower case letters like x,y,… to stand for single disks. The letter l will always stand for the largest disk (5 in the particular case we are concerned with). Also, we will write the contents of a single stack with the top disk on the left, bottom disk on the right, and write positions of all three posts like P | Q | R where P, Q, and R are the stacks on each of the three posts. If a post is empty, then we will just use a – in place of the stack. So the goal is to get to the position 12345 | – | -.
Note that if there is a way to solve a starting position like Plx in k moves, then it is possible to solve Pxl in no more than k moves. Why? To solve Plx, the largest disk must move, since it covers a smaller disk. And in order for l to move, all of the disks in P must move to the same other post, leaving the third post empty; l can only move to an empty post. So the solution for Plx must consist of a phase in which you reach the position lx | Q | -, where Q contains the same disks as P but in sorted order. Then the next move must be to x | Q | l, and then there must be a final phase which converts this position to the solved state. Now, to solve Pxl in k moves, we just use the first phase of the solution for Plx to reach xl | Q | -. Then move x to yield l | Q | x. Then use the final phase of the Plx solution but with the roles of the first and last post reversed to finish the solution of Pxl. That may not be the optimal solution for Pxl, but it shows that Pxl can be solved in at most k moves.
The upshot of this is that to find the initial position that requires the most moves to sort, we do not need to look at any positions in which the largest disk is on tbe bottom. Also, if the largest disk is on top, we can solve the position in no more than the number of moves required for the worst starting position with one fewer disk or to solve the usual starting position with n-1 disks: just move the largest disk off the top and then solve what remains. So if we find any position with n disks that takes more than the worst for n-1 disks or the usual puzzle for n-1 disks, we do not need to consider any positions with the largest disk on top.
Now we’re ready to start figuring out the maximum number of moves needed for smaller numbers of disks. For one disk there’s nothing to do, so the worst starting position is 1 and it takes zero moves. For two disks there’s only one unsorted starting position, 21, and it takes two moves. For three disks, start by considering 132. It takes four moves, which is one more than to solve ordinary two disks, so we don’t need to consider any positions with 3 on top. Therefore, the only other position we need to worry about is 231, which also takes four moves. Therefore one worst position with three disks is 132, and it takes four moves.
That brings us to four disks. Let’s check 1243. That takes three moves to move the 12, then 1 move for the 4, another move to put the 3 on the 4, and then three more moves to put the 12 on top of the 3, for 8 moves in all. As that’s one more than the number it takes to solve the ordinary Hanoi puzzle with three disks, we don’t need to consider any positions with the 4 on top to find the worst. So we only need to check 1423, 1432, 2413, 2431, 3412, 3421, 2143, 1342, 3142, 2341, and 3241. Of these, the greatest number of moves required is eleven, for example with 2341. (Three moves to 41 | 23 | -, two more to – | 23 | 14, two more to 12 | 3 | 4, one more to 12 | – | 34, and then three to finish.)
We’re finally ready to attack five disks. Note that the position 23451 takes 22 moves to solve (seven to reach 51 | 234 | -, one more to reach 1 | 234 | 5, and 14 more moves to complete the transfer of 1, 2, 3, and 4 to be on top of the 5). Since 22 is well more than 15, we don’t need to consider starting positions with 5 on the top. Similarly, any position like x5P can’t take more 19 moves to solve (two to reach P | 5 | x and then at most one more than the worst for the four-disk stack xP, in case the disk x is in the wrong position in P | 5 | x for the shortest solution to move xP onto the top of the 5, namely 17 more moves). Therefore, we don’t need to consider any positions with a 5 in the second position. So that leaves only the stacks with the 5 in the third or fourth positions from the top.
Moreover, since in all of the smaller cases the number of moves needed for the ordinary Tower of Hanoi puzzle exceeds the worst needed for this sorting version, we only need to look at positions like PlQ in which P is already sorted, since the solution must begin by reaching lQ | S | – where S is the sorted version of P so that it’s possible to move the largest disk. And moving P in that way takes the most moves when it’s already sorted. In addition, if stacks P and Q of height two are both sorted, then PlQ and QlP take the same number of moves to solve, since they go through equivalent positions Q | l | P and P | l | Q, respectively.
All of this means that we are left only with positions 12534, 12543, 13524, 13542, 14523, 14532, 34521, 24531, 23541, 12354, 12453, 13452, and 23451 to check. These take 19, 9, 15, 10, 13, 10, 18, 10, 12, 16, 19, 22, and 22 moves to solve, respectively, so we conclude that the hardest possible 5-disk positions take 22 moves to solve and are 13452 and 23451.
Amphibian Marathon. Each toad or frog has to move six spaces, and there are six of them, so that makes 36 ordinary moves. However, there must be nine jumps, since every pair of toad and frog have to change order from left to right (the toad might jump the frog or vice versa). Each jump takes the jumping piece a distance equivalent to two ordinary moves, so the nine jumps reduce the total number of moves in a winning game to 27. Technically, one should also verify that there is at least one way to win the game (there is).
Recent Weeks
Week 92: Sort of Hanoi-ing & Amphibian Marathon, solutions to Hard States & Great Star
Week 91: Hard States & Great Star, solutions to Thirds Squared & 3-4-5 Square
Week 90: Thirds Squared & 3-4-5 Square, solutions to World Turns & Water Slide
Week 89: World Turns & Water Slide, solutions to Soccer or Math? & Belt, Suspenders, and Braces
Week 88: Soccer or Math? & Belt, Suspenders, and Braces, solutions to Queen Bee & Coco-Not
Links to all of the puzzles and solutions are on the Complete Varsity Math page.
Come back next week for answers and more puzzles.
