________________
________________
Sort of Hanoi-ing
Cameron has a Tower of Hanoi set with five disks of different sizes that can slide onto any one of three different posts. In the usual game, the disks start in a stack in size order (with the largest on the bottom) on one post, and the player must move the disks one by one so the stack ends up on another post in the same order. Any disk can be moved from the top of the pile on any post to any other post, so long as it is smaller than the top disk on the destination post. After playing with it for a bit, the team comes up with a new variant: The disks all start on one post but in an arbitrary order, and the goal is to get them into the usual sorted order (on any post). The usual starting position is already sorted and so takes zero moves to solve; and if the disks start in the opposite order it only takes five moves to solve (piling the disks one at a time onto another post).
What initial stacking order of the five disks takes the most moves to solve?
Amphibian
Marathon
Drew has a “Toads and Frogs” set which consists of three playing pieces shaped like toads, three shaped like frogs, and a playing board that consists of nine spaces arranged in a line. The three toads start on the leftmost three spaces and the three frogs start on the rightmost three spaces. Toads can either move one space to the right (if the adjacent space is empty) or jump over a single adjacent frog to the right to land on the next space (if that space is empty). Similarly, frogs can either move one space to the left or jump over one toad to the left. Toads and frogs move alternately, with toads going first. The game is won if the frogs and toads manage to exactly swap the positions they occupied at the beginning of the game.
How many moves occur in a winning game of Frogs and Toads?
| Spread the word: | Tweet |
Solutions to week 91
Hard States. The easiest way to attack this problem is just to make a table of “easy” arrangements for each number of states consecutively from one on up, and then examine the first entry that there doesn’t seem to be a way to fill in to make sure it’s really not possible. Here’s the table:
| States | Rows in easy arrangement |
|---|---|
| 1 | 1 |
| 2 | 1,1 |
| 3 | 2,1 |
| 4 | 2,2 |
| 5 | 2,1,2 |
| 6 | 2,2,2 |
| 7 | 2,3,2 |
| 8 | 3,2,3 |
| 9 | 3,3,3 |
| 10 | 3,4,3 |
| 11 | 4,3,4 |
| 12 | 3,3,3,3 |
| 13 | 3,2,3,2,3 |
| 14 | 4,3,4,3 |
| 15 | 3,3,3,3,3 |
| 16 | 4,4,4,4 |
| 17 | 3,4,3,4,3 |
| 18 | 4,5,4,5 |
| 19 | ? |
So there doesn’t seem to be any easy arrangement for 19 stars. Let’s verify that. If the arrangement had seven (or more) rows, then each row would have either one or two stars, and hence the number of rows divided by the number of stars in each row would always be larger than two. If it had six rows, there would have to be five rows of three stars and one row of four stars, and so there would be no way to alternate row lengths. If it had five rows, there would be one row of three stars and four rows of four stars, so again no way to alternate row lengths. If it had four rows, it would be one row of four stars and three rows of five stars, so again alternating row lengths would be impossible. And if it had three rows, they would be two rows of six and one row of seven stars, so the number of rows divided by row length would always be less than one. And clearly that situation is worse with one or two rows. So the smallest number of states that is not easy is 19. (But as fortune would have it, there was never a year in which the US had 19 states; you can investigate when there was first an actual number of states that occurred that did not have an easy configuration, and see what flag designs were used in that case.)
Great Star. 
We of course need the five stars at the vertices of the pentagram. We also need at least one more star on each edge of the pentagram. By placing a star whose center lies at the intersection of edges, we can satisfy more than one edge at once; since at most two of the edges of the pentagram intersect in a single point, each star will serve at most two edges at once. So to get one star on each of the five edges, we will need at least three more stars, and indeed, the arrangement shown works for eight stars with three stars on each edge.
Recent Weeks
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
Week 87: Queen Bee & Coco-Not, solutions to Uneven Odds & Stable Selection
Links to all of the puzzles and solutions are on the Complete Varsity Math page.
Come back next week for answers and more puzzles.
[asciimathsf]
