I solved this puzzle in 25 moves. Using r for the R in Martin and b for blank... The letters before each move are (locations of other coins/blocked locations) (GDER) (GDE/ATI) R-b-N-r (GEr/AIN) D-T (GrT/AND) E-I-R-b (Grb/ANR) T-D-I-E (GrE/ANI) b-R (GER/AIb) r-N (ERN/Ibr) G-A-M (ERM/IbA) N-r (EMr/IAN) R-b (Mrb/ANR) E-I-D-T (MrT/AND) b-R-I-E (MTE/ADI) r-N-b (MTb/ADNR) E-I (MTIb) Joseph DeVincentis ------------------------------------------ I found it easier to rearrange the graph like this: E | T - D - I - r | / | | M - A - R - N - X | G where r is the lower-row R and R is the middle-row R, and X is the empty circle. solution: D-T r-X-N-R E-I-r-X T-D-I-E X-r R-N G-A-M N-R r-X E-I-D-T X-r-I-E R-N-X E-I Thanks, ___ X- Trygve Flathen ------------------------------------------ 1 — R 0 2 — 0 N 3 — N R 4 — D T 5 — E I 6 — I R 7 — R 0 8 — T D 9 — D I 10 — I E 11 — 0 R 12 — R N 13 — G A 14 — A M 15 — N R 16 — R 0 17 — E I 18 — I D 19 — D T 20 — 0 R 21 — R I 22 — I E 23 — R N 24 — N 0 25 — E I Greetings from Barcelona, two days before our book's day. Jordi Domθnech ------------------------------------------ Hi, I've never written in before, but I browsed by the site earlier and saw this puzzle, looked interesting so I graphed it with less tangled nodes and solved in a few minutes, figured I'd send in my solution. The crux was figuring out what the board needed to look like to move M through A to G, after that, it almost solves itself. Great puzzle. :) Keep 'em coming! Sincerely, Michael Ferry I'll call the left R, R1, and the right R, R2, and the blank spot I'll call _. Coin moves: (one row means you keep moving the same coin) D -> T R2 -> _ -> N -> R1 E -> I -> R2 -> _ T -> D -> I -> E _ -> R2 R1 -> N G -> A -> M N -> R1 R2 -> _ E -> I -> D -> T _ -> R2 -> I -> E R1 -> N -> _ E -> I Less tangled nodes looked something like this: G M \ / A - D |\ /| R T | | | N - I - E | | () - R ------------------------------------------ use * for the empty circle although there are two R's, it is clear which is used D-T R-*-N-R E-I-R-N T-D-I-E *-R R-N G-A-M N-R R-* E-I-D-T *-R-I-E R-N-* E-I Rolan Christofferson ------------------------------------------ Debashish Majumdar sent a solution. ------------------------------------------ Ed I think the shortest solution to R.A. Hearns MARTIN GARDNER puzzle is 14 steps as follows: Let X represent the Blank cell; then the sequence is R - X - N - R, D - T , E - I - R - X , T - D - I - E , X - R , R - N , G - A - M , N - R , R - X , E - I - D , R - T , X - R - I - E , R - N - X , E - I Although there are two 'R's in the puzzle, the above sequence should be fairly easy to follow Rgdz Pete Kogel ------------------------------------------ Hi Ed, I solved the Robert Hearn's puzzle in 27 moves. 'B' stands for "blank" and although there are two R's, the moves should be unambiguous given the edges. R - B B - N D - T N - R E - I I - R T - D R - B D - I I - E B - R R - N G - A A - M N - R R - B E - I I - D D - T B - R R - I I - E T - D R - N D - T N - B E - I -- Nathan Stohler ------------------------------------------ R1 is the R on the left of the puzzle, R2 is on the right. R2-Blank D-T Blank-N-R1 E-I-R2 T-D R2-Blank D-I-E Blank-R2 R1-N G-A-M N-R1 R2-Blank E-I-D Blank-R2 R1-N D-T N-R1 R2-I-E R1-N-Blank E-I Warren Phillips ------------------------------------------ let empty space = S R - S - N - R D - T E - I - R - S T - D - I - E S - R R - N G - A - M N - R R - S E - I - D - T S - R - I - E R - N - S E - I Hope that works! :) Yours, Shahrul Mt.Isa ------------------------------------------ Call the bottom right circle " R ", to distinguish it from the r on the left. Also, the blank space is " - " The first character in each line is the starting position of the move, the subsequent characters are destinations. Moves are as follows: dt R-nr eir- die -R rn ga (We now have coins at a,n,e, and R) am nr R- eidt -Rie rn- ei - Matt Elder ------------------------------------------ I couldn't work this out in my head, so I did the next best thing and wrote a program to solve it ;-) I replaced the second "R" (the one on the far right) with "Z", and used "O" for the blank node, so that each node would have a unique letter to identify it. At each step, I list the positions of the four coins (with the order preserved), followed by the next move. 1. GDEZ D->T 2. GTEZ Z->O 3. GTEO O->N 4. GTEN N->R 5. GTER E->I 6. GTIR I->Z 7. GTZR Z->O 8. GTOR T->D 9. GDOR D->I 10. GIOR I->E 11. GEOR O->Z 12. GEZR R->N 13. GEZN G->A 14. AEZN A->M 15. MEZN N->R 16. MEZR Z->O 17. MEOR E->I 18. MIOR I->D 19. MDOR D->T 20. MTOR O->Z 21. MTZR Z->I 22. MTIR I->E 23. MTER R->N 24. MTEN N->O 25. MTEO E->I MTIO Interestingly, this is almost palindromic. The 3rd through 12th moves are the mirror image of the 15th through 24th moves. Bill Daly ------------------------------------------ R2-O-N-R1 D-T E-I-R2-O T-D-I-E O-R2 R1-N G-A-M N-R1 R2-O E-I-D-T O-R2-I-E R1-N-O E-I Jim Hawkins ------------------------------------------ Note: "RL" is "R" on the left, "RR" is "R" on the right, "SP" is space. Solution: RR - SP, SP - N, N - RL, D - T, E - I, I - RR,RR - SP,T - D,D - I,I - E, SP - RR, RL - N, G - A, A - M,N - RL, RR - SP, E - I, I - D, D - T, SP - RR, RR - I, I - E, RL - N, N - SP, E - I Regards J.HAYES. ------------------------------------------ My students love it when I find little puzzles (usually suggested by you) for them to try. Well, some of them do -- the rest think I'm just a weird math teacher. A few of us solved it. I asked one of my students to write out his solution and this is what he gave me: D-T R2-0-N-R1 E-I-R2-0 T-D-I-E 0-R2 R1-N G-A-M N-R1 R2-0 E-I-D-T 0-R2-I-E R1-N-0 E-I R1 is the lefthand R R2 is the righthand R 0 is the blank space This is either 13 moves or 25 moves, depending on how you count them. I'm not sure if it is the shortest solution. -Jeremy Galvagni ps. How much extra credit should this be ;-) ------------------------------------------ R2 : R on bottom R1 : R in middle R2 > Empty Empty > N N > R1 D > T E > I I > R2 T > D R2 > Empty D > I I > E Empty > R2 R1 > N G > A A > M N > R1 R2 > Empty E > I I > D D > T Empty > R2 R2 > I I > E R1 > N N > Empty E > I Clark Cooper ------------------------------------------ Shortest possible answer seems to be 25 moves, and there are 16 shortest paths. To ease possible complications, we refer to the R on the middle row by lower case, that on the bottom row by upper case. The blank is referred to by an underscore. Let us consider a sequence S of moves from GDER to MTI_ which takes the shortest possible time. We will use (without proving) the obvious fact that it is not possible that at two different stages in S the coins are on the same spots. Theorem 1: At some point in S, the coins are on GNER and the G coin moves through A immediately to M. Proof: There is some last stage when there is a coin on G. Immediately after this stage there must be a coin on A. If there is a coin on A, there cannot be a coin on M,T,r,G or D. Thus the other 3 coins must be on I,N,E,R or _. I is next to three of the others, and thus cannot contain a coin. _ is next to 2 of the others, and can also not contain a coin. Therefore the other 3 coins are on NER. Therefore the move goes from GNER->ANER. Similarly at the first stage when there is a coin on M, the move has gone ANER->MNER. Since S only goes through 1 ANER stage, S has a sequence GNER->ANER->MNER. QED Corollary 2: S consists of the shortest possible sequence to GNER, then the transfer GNER->ANER->MNER, then the shortest possible sequence from MNER. Before GNER, the G coin does not move. After MNER, the M coin (the same coin, as it happens) does not move. Proof: QED So we split into finding the shortest sequence to GNER (S_1) and the shortest sequence from MNER (S_2), noting that the G-coin or M-coin does not move, and hence the spots G,A,M are out of bounds for moves in either sequence. (A as there will be something in the [ahem] G-spot or M-spot and G,M as the only moves go to A). Theorem 3: S_1 contains the sequence GTrE, GTrI, GTrR. Proof: When the E coin first moves, it moves to I. Therefore the spots N,D,R are empty, and the other 2 coins (ignoring the G coin for this theorem) must be in 2 of T,R,_. Note that none of these spots is adjacent to any spot (other than the forbidden A) which is not adjacent to I. Therefore the other coins cannot be next to move. Therefore the I-coin must move. It won't move back to E, so it must move to either D,N or R. The coin that started off at D MUST be at T: Without going through the forbidden spots A (because of G) and I (because of E), it cannot move anywhere else, and we have already seen that it cannot still be at T. Therefore the I-coin cannot move to D. It also cannot move to N, as this is adjacent to both of r and _, one of which must have the original R-coin in it. Therefore it must move to R, and the original R-coin must be at r. QED Corollary 4: S_1 (and hence S) starts in an equivalent way to GDER,GTER,GTE_,GTEN,GTEr. (Equivalent means that the shifting of the D-coin to T can happen at any stage during the R-coin's path to r - giving 4 solutions this far) Proof: We've seen in the proof of theorem 3, that the D-coin moves to T and the R-coin moves to R before either of the other coins move. This takes a minimum of 4 moves. QED Theorem 5: S_1 ends with the sequence GrI_,GrE_,GrER,GNER Proof: Similar to Proof of Theorem 3. Within S_1, consider when there is last no coin on the E-spot. It must be on the I-spot. The other 2 must therefore be on 2 of T,r,_. If one is on T, it can never get to N or R without moving G or E, both of which are forbidden. The other 2 must therefore be on r and _. Therefore within S_1, it will go GrI_ -> GEI_. Then we must still get to GNER as soon as possible. Clearly it will take at least 2 moves, as 2 coins are on spots they shouldn't be on. Furthermore the only way to do it in 2 moves is to go via GrER. QED Theorem 6: The shortest routes from GTrR to GrI_ are 3 moves long, and there are 2 options: GTrR,GTr_,GDr_,GIr_ or GTrR,GDrR,GDr_,GIr_. Proof: If either G or r move, then the solution will take at least 4 moves (1 to initially move each coin that moves, and 1 to push a coin into the G or r spot). Therefore G and r are fixed, and the only valid squares are TI_DER. T is 3 squares from _ and therefore T must go to I (2 moves away), and R must go to _ (1 move away). R must move to _ before T finally arrives at I. QED. Corollary 7: S_1 is 12 moves long, and there are 8 versions. 1 such version is GDER,GTER,GTE_,GTEN,GTEr,GTrI,GTrR,GTr_,GDr_,GIr_,GRe_,GrER,GNER Proof: Follows from Corollary 4, Theorem 3, Theorem 6 and Theorem 5 (in that order along the route). QED Now we look at S_2 (from MNER to MTI_ not moving the M and not using M,A or G) Theorem 8: S_2 starts MNER, MrER, MrE_, MrI_, MrD_. Proof: As in theorem 5, before E moves, spaces T,D cannot be used, and therefore the other 2 coins must get to positions r and _. This will take at least 2 moves and can be done so in precisely 1 way, as N must be cleared before _ is filled. This gets you to MrE_. This was in order for E to move, bringing you to MrI_. Now r and _ are not adjacent to anything that is not adjacent to either I or M, and so I must be the next coin to move, and it must move to D. QED Theorem 9: S_2 ends MTIr, MTEr, MTEn, MTE_, MTI_ Proof: In order for the r-coin to leave the r-spot, it must go to N. Therefore I,R,_ must be empty. At most 1 coin can be in the T or D spots, and therefore the other coin must be in the E-spot. It must have moved there from the I spot, and the other coin cannot have been in the D spot, it must have been in the D-spot. Therefore, the situation must have been MTIr,MTEr. The r coin is then 2 squares away from any finishing square, and the E coin is 1 square away. Therefore at least 3 moves are needed to complete the sequence. E's move to I must be the final one, as the N and I squares cannot be simultaneously full. QED Theorem 10: There are 2 paths of shortest length from MD_r to MTIr: MD_r,MT_r,MTRr,MTIr or MD_r,MDRr,MTRr,MTIr. Proof: D is 1 move away from a destination and _ is 2 moves away from its nearest destination. Therefore 3 moves are needed, and you can only move _ or D. Furthermore the only destination within 2 moves of _ is I. Therefore it must go to I. Also it must go via R, as N is a forbidden neighbour of r. D must go to T, and it must do so before the later part of _'s path to I. QED Corollary 11: There are 2 possible S_2 paths: MNER,MrER,MrE_,MrI_,MrD_,MrT_,MrTR,MrTI,MrTE,MnTE,M_TE,M_TI and MNER,MrER,MrE_,MrI_,MrD_,MrDR,MrTR,MrTI,MrTE,MnTE,M_TE,M_TI. Proof: Theorem 8, Theorem 10 and Theorem 9 in that order. QED Corollary 12: There are 16 possible S paths, and one such is: GDER,GTER,GTE_,GTEN,GTEr,GTIr,GTRr,GT_r,GD_r,GI_r,GE_r,GERr,GERN,AERN,MERN,M ERr,ME_r,MI_r,MD_r,MT_r,MTRr,MTIr,MTEr,MTEn,MTE_,MTI_ Proof: Corollary 7 and 11 QED Luke Pebody ------------------------------------------ I think I have a solution. In the following description I won't distinguish the two R's since their moves are different. Moves on the same line belong to a single coin. 4 : R -> _, _ -> N, N -> R, 2 : D -> T, 3 : E -> I, I -> R, R -> _, 2 : T -> D, D -> I, I -> E, 3 : _ -> R, 4 : R -> N, 1 : G -> A, A -> M, 4 : N -> R, 3 : R -> _, 2 : E -> I, I -> D, D -> T, 3 : _ -> R, R -> I, I -> E, 4 : R -> N, N -> _, 3 : E -> I. Wang Zirui ------------------------------------------ Phew! 25 moves! Excellent puzzle. Solution: R-0-N-R D-T E-I-R-0 T-D-I-E 0-R R-N G-A-M N-R R-0 E-I-D-T 0-R-I-E R-N-0 E-I Thanks and keep up the good work! ttfn, Mark Ingram ---------------------------------------------- Since the two Rs do not have any edges to a common vertex, the following is unambiguous: D->T R-> ->N->R E->I->R-> T->D->I->E ->R R->N G->A->M N->R R-> E->I->D->T ->R->I->E R->N-> E->I -- Trevor Green