On the 3 by 3 board: a1c2, c3a2, b1c3, b3a1, c1b3, a3b1, b2a3, a2c1. Why is this not a solution for n=3? I think I remember seeing this in a Martin Gardner column: it uses the fact that knights moves link up the outer eight cells in a cyclic graph. On Fri, Oct 15, 2010 at 3:53 PM, Richard Guy <rkg@cpsc.ucalgary.ca> wrote:

I don't believe that the following sequence is in OEIS.

The (least) number of moves needed to swap n pairs of knights on a 3 by n chessboard.

I.e., the number of chess knight moves needed to get from

S S S ... S s s s ... s - - - - to - - - - s s s ... s S S S S

where s, S are chess knights of opposite colors. Not possible for n = 1, 2, 3.

n = 4: 32 moves are necessary and sufficient.

n = 5, 6, 7, ... are Rikki-Tikki-Tavi questions on p.250 (R187) of The Inquisitive Problem Solver.

R.

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

In Penney's game, http://en.wikipedia.org/wiki/Penney's_game  , I have HHT, and you have HHH.  We start flipping a coin, and the winner is the first to get their sequence of heads and tails. In HHH beats HHT, the number of wins on turn 3, 4, 5, 6 ... form the Fibonacci sequence.  All of the below famous sequences are linked by Penney's game, which doesn't seem to be well known. { {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597}        (*HHH beats HHT   A000045 - Fibonacci*), {1,1,1,2,4,6,9,15,25,40,64,104,169,273,441,714,1156}         (*HHH beats HTH   A006498*), {1,1,2,3,4,6,8,11,15,20,27,36,48,64,85,113,150}              (*HHH beats HTT   A023434 - Dying rabbits*), {1,1,2,3,4,6,9,13,19,28,41,60,88,129,189,277,406}            (*HHH beats THT   A000930*), {1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65}                   (*HHH beats TTH   A000931 - Padovan*), {1,2,3,5,8,12,18,27,40,59,87,128,188,276,405,594,871}        (*HHT beats HTH   A077868*), {1,2,4,6,9,12,16,20,25,30,36,42,49,56,64,72,81}              (*HHT beats HTT   A002620 - Quarter squares*), {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}                          (*HHT beats THH   A000012 - All 1's*), {1,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32}              (*HHT beats THT   A004277*), {1,2,4,6,9,13,18,25,34,46,62,83,111,148,197,262,348}         (*HHT beats TTT   Not in OEIS*), {1,2,2,3,6,10,15,24,40,65,104,168,273,442,714,1155,1870}     (*HTH beats HHH   A070550*), {1,1,1,2,3,4,6,9,13,19,28,41,60,88,129,189,277}              (*HTH beats HHT   A000930*), {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}                  (*HTH beats HTT   A000027 - Natural numbers*), {1,2,2,3,5,7,10,15,22,32,47,69,101,148,217,318,466}          (*HTH beats THH   A097333*), {1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2}                          (*HTH beats TTH   A040000*), {1,2,3,4,6,9,13,19,28,41,60,88,129,189,277,406,595}          (*HTH beats TTT   A068921 - Tatami mats*), {1,2,3,5,7,10,14,19,26,35,47,63,84,112,149,198,263}          (*HTT beats HHH   A054405*), {1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9}                          (*HTT beats HHT   A008619*), {1,1,2,4,6,9,14,21,31,46,68,100,147,216,317,465,682}         (*HTT beats THT   A038718*), {1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584}     (*HTT beats TTH   A000045*), {1,2,4,6,10,16,26,42,68,110,178,288,466,754,1220,1974,3194}  (*HTT beats TTT   A128588*)} Ed Pegg Jr mathpuzzle.com