Problems & Puzzles: Puzzles

Puzzle 310. DPT's on a knight's tour. Anurag Sahay poses the following puzzle: 1) What is the greatest possible number of pairs of diagonally touching primes on a knight's tour (see also Puzzle 30) 2) I have constructed one tour with 17 pairs of DTP's. Can someone get a higher score? (Incidentally, the earliest known knight's tour (about 1000 years old) also has 17 DTPs). Can you find one of the same rank?

 

---

Jacques Tramu sent the following solution:

23 pairs of diagonal primes :

 

 

01  34  63  40  55  52  45  42
64  39  56  35  44  41* 54  51
57  02* 33  62  53* 46  43* 12
32  27  38  59* 36  13* 50  47*
03* 58  61* 28  23* 48  11* 14
26  31* 22  37* 60  17* 08  49
21  04  29* 24  19* 06  15  10
30  25  20  05* 16  09  18  07*

 

[1]  41 43
[2]  41 53
[3]  53 59
[4]  43 47
[5]  59 61
[6]  13 23
[7]  13 43
[8]  13 53
[9]  3 31
[10]  23 37
[11]  23 59
[12]  11 17
[13]  11 47
[14]  11 13
[15]  31 61
[16]  37 61
[17]  17 19
[18]  17 23
[19]  29 37
[20]  29 31
[21]  19 37
[22]  5 19
[23]  5 29

***

More questions:

3) Jacques Tramu added:

One could also ask the question of the maximum

number of pairs of orthogonally touching primes (OTP).

 

my best answer for a 8x8 board is : ....  4

43* 46  17* 50  57  62  15  12
18  49  44  63  16  13* 54  61*
45  42  47* 58  51  56  11* 14
48  19* 64  01  38  53* 60  55
23* 02* 41* 52  59* 36  29* 10
20  05* 22  37* 26  39  32  35
03* 24  07* 40  33  30  09  28
06  21  04  25  08  27  34  31*

 

[1]  2 41
[2]  2 23
[3]  2 5
[4]  2 19

4)  The minimal quantity of DTP's in a 8x8 array? (Anurag Sahay)? He sent one with 6.

48 23 60 31 50 13 36 33
59 30 49 12 35 32 51 14
22 47 24 61 44 11 34 37
29 58 45 42 25 62 15 52
46 21 28 3 10 43 38 63
7 4 57 26 41 2 53 16
20 27 6 9 18 55 64 39
5 8 19 56 1 40 17 54

Mr Tramu shortly after sent one with 5:

33  20  31* 54  35  18  61* 64
30  53* 34  19* 62  43* 36  17*
21  32  55  44  51  60  63  10
56  29* 52  59* 42  11* 16  37*
01  22  57  50  45  38  09  12
28  47* 26  41* 58  13* 06  15
23* 02* 49  46  25  04  39  08
48  27  24  03* 40  07* 14  05*

 

[1]  31 53
[2]  19 31
[3]  43 61
[4]  17 61
[5]  23 47

***

Based only in geometrical considerations I (CR) think that  answer for 1) is 25 (discarding the prime number 2, because it can never be diagonally adjacent to the rest of the primes), but I have not a solution as big as that. So Mr. Tramu is just one inch away from the 'optimal' solution; if 25 is really affordable.

 

***

Anurag's contribution to the Jacques follow-up is this:

4 OTPs is the max possible (2 primes form an OTP only if 2 is one of them). Following tours have 4 OTPs:

[2 41,2 73, 2 83, 2 53]

39 70 57 86 89 36 59 16 91 18
56 87 38 69 58 67 90 19 60 15
71 40 85 88 37 44 35 14 17 92
84 55 72 45 68 13 66 63 20 61
1 46 41 10 3 34 43 12 93 64
54 83 2 73 42 11 4 65 62 21
47100 53 78 9 74 33 22 5 94
82 79 50 75 26 77 28 7 30 23
99 48 81 52 97 8 25 32 95 6
80 51 98 49 76 27 96 29 24 31


[2 43,2 19, 2 37, 2 13]

38 3 40 19 36 17 44 47
41 20 37 2 43 46 35 16
4 39 42 13 18 63 48 45
21 56 9 28 1 34 15 62
10 5 12 57 14 61 64 49
55 22 29 8 27 50 33 60
6 11 24 53 58 31 26 51
23 54 7 30 25 52 59 32

[29 2, 31 2, 59 2, 5 2]

19 44 23 28 1 60 3 30
24 27 18 43 22 29 6 61
45 20 25 64 59 2 31 4
26 17 40 21 42 5 62 7
39 46 35 58 63 50 11 32
16 57 38 41 34 53 8 51
47 36 55 14 49 10 33 12
56 15 48 37 54 13 52 9

[37 2, 13 2, 47 2, 11 2]

50 39 16 29 52 21 58 19
15 30 51 40 57 18 53 22
38 49 28 17 26 41 20 59
31 14 25 56 33 60 23 54
48 37*32 27 24 55 42 61
13* 2*11* 34 45 4 9 6
36 47*64 3 10 7 62 43
1 12 35 46 63 44 5 8

[7 2, 29 2, 11 2, 17 2]

8 33 30 17 6 3 12 19
31 28 7 2 11 18 15 4
34 9 32 29 16 5 20 13
27 58 35 10 1 14 61 46
36 39 64 59 62 45 50 21
57 26 55 38 53 60 47 44
40 37 24 63 42 49 22 51
25 56 41 54 23 52 43 48

***

Gunter Stertenbrink solved (May 1, 2005) Q1, getting the maximal possible count of DTP's: 25

4	1	8	11	6	21	32	35
9	12	5	2	31	34	25	22
18	3	10	7	20	23	36	33
13	46	19	30	37	26	61	24
54	17	42	47	60	29	38	27
45	14	53	50	41	48	59	62
52	55	16	43	64	57	28	39
15	44	51	56	49	40	63	58

Game over!

Congratulations to Gunter!

***

George Jelliss wrote (May 25, 2005):

G. Stertenbrink claims 25 diagonal touching primes to be the maximum.

 

However, 27 were achieved by T. R. Dawson and S. H. Hall in Problemist Fairy Chess Supplement, April 1936, p.182, with this closed tour:

 

50 15 62 27 60 17 42 39

63 28 49 16 41 38 59 18

14 51 26 61 48 19 40 43

25 64 29 12 37 44 31 58

52 13 24 07 30 47 20 45

01 08 03 36 11 34 57 32

04 53 10 23 06 55 46 21

09 02 05 54 35 22 33 56

 

The odd primes occur on the dark squares in the rectangle a3-c1-h6-f8.

 

The same source also gives an open tour by T. R. Dawson with the same property. I included these tours in the booklet on Figured Tours that I published in 1996.

The Jelliss claims is not valid (not now!) because '01' is not prime.

Nevertheless this is a second/distinct solution with 25 diagonal touching pair of primes, using an inscribed 6x3 rectangle while the Gunter's solution used an inscribed 4x4 rectangle.

 

***

 

 

---