Jump and fill my square
Hello Math Fun
The aim of this challenge is to fill a square with integers (square that has a 0 --zero-- in its upper-left corner). The best square is the one with the lowest sum of the said integers.
Here is my personal best for the 2 x 2 square (sum = 11):
0.1
6.4
... my best 3 x 3 has sum 63:
0.1.20
6.8.10
4.2.12
In order to fill a square, you have to start on the zero cell and jump:
a) over zero cell (you land on 1 of the 4 adjacent cells – diagonal jumps are forbidden)
b) from there, over 1 cell (you always have the choice to jump up, right, down or left if the landing cell is empty)
c) from there, over 2 cells (same rules as above)
d) from there, over 3 cells (same rules – at every step the size of the jump is increased by 1).
etc.
Here is my path two fill the 2 x 2 square, starting on 0 (R=right, D=down, U=up and L=left; the size of the jump is increased by 1 at every step, the 1st jump being of size zero):
Here is my path to fill the 3 x 3 square -- same convention:
0. 1.20.18
6. 8.10.16
4. 2.12.14
38.40.42.44
The total sum for this 4 x 4 square is 275.
Can you beat my personal records? And find records for bigger squares?
(forgive me if this is old hat)
Best, É.
____________________
May 20, 2019 update
Tom Karzes was quick to beat my attempts. Here is the mail he sent to Math Fun:
> I slapped together a quick-and-dirty search program, and was able to find optimal solutions up to 6x6. Note that for sizes 2x2, 4x4, 5x5, and 6x6, it was able to find solutions that remain within the square for the first n-1 moves, and thereafter bounce out of and into the square every other move, making it trivial to verify their optimality. No such solution exists for the 3x3 case, and I suspect it doesn't for 7x7 either (I started a search on 7x7 but eventually killed it). Anyway, here are optimal solutions for 2x2 through 6x6:
Size: 2x2 Sum: 9 Moves: RUDRL
0.1
5.3
Size: 3x3 Sum: 59 Moves: RDLRDURLRLUDLDRU
0.1.16
10.8. 6
12.2. 4
Size: 4x4 Sum: 198 Moves: RRDRLRLRLDUDULRUDLRLRDURLDU
0. 1.27. 2
13.15.25.23
11.17.19.21
9. 7. 5. 3
Size: 5x5 Sum: 510 Moves: RDRLDULRLRUDUDRLRLUDLRLRLRLRDU RLDUDULRDURLRL
0. 1.44.42.40
6. 8.10.36.38
4. 2.12.34. 3
18.16.14.32.30
20.22.24.26.28
Size: 6x6 Sum: 1095 Moves: RDRLRUDRLRLUDLRLRUDRLRLRLRLRLDDULRUDLRDUDULRDULRLRDURLRLRLU DRLRL
0. 1.59.57.55.53
65.63.61.47.49.51
4. 2.43.45. 3. 5
33.35.41.11. 9. 7
31.37.39.13.15.17
29.27.25.23.21.19
Bravo Tom!
I will submit this sequence to the OEIS – we will see if it is accepted.
____________________
The aim of this challenge is to fill a square with integers (square that has a 0 --zero-- in its upper-left corner). The best square is the one with the lowest sum of the said integers.
Here is my personal best for the 2 x 2 square (sum = 11):
0.1
6.4
... my best 3 x 3 has sum 63:
0.1.20
6.8.10
4.2.12
In order to fill a square, you have to start on the zero cell and jump:
a) over zero cell (you land on 1 of the 4 adjacent cells – diagonal jumps are forbidden)
b) from there, over 1 cell (you always have the choice to jump up, right, down or left if the landing cell is empty)
c) from there, over 2 cells (same rules as above)
d) from there, over 3 cells (same rules – at every step the size of the jump is increased by 1).
etc.
Here is my path two fill the 2 x 2 square, starting on 0 (R=right, D=down, U=up and L=left; the size of the jump is increased by 1 at every step, the 1st jump being of size zero):
R D D U R L
Here is my path to fill the 3 x 3 square -- same convention:
R D R L D U L R L R U D L R D U D U R L
(the above illustration also shows my attempt for a 4 x 4 square built on the 3 x 3)
0. 1.20.18
6. 8.10.16
4. 2.12.14
38.40.42.44
The total sum for this 4 x 4 square is 275.
Can you beat my personal records? And find records for bigger squares?
(forgive me if this is old hat)
Best, É.
____________________
May 20, 2019 update
Tom Karzes was quick to beat my attempts. Here is the mail he sent to Math Fun:
> I slapped together a quick-and-dirty search program, and was able to find optimal solutions up to 6x6. Note that for sizes 2x2, 4x4, 5x5, and 6x6, it was able to find solutions that remain within the square for the first n-1 moves, and thereafter bounce out of and into the square every other move, making it trivial to verify their optimality. No such solution exists for the 3x3 case, and I suspect it doesn't for 7x7 either (I started a search on 7x7 but eventually killed it). Anyway, here are optimal solutions for 2x2 through 6x6:
Size: 2x2 Sum: 9 Moves: RUDRL
0.1
5.3
Size: 3x3 Sum: 59 Moves: RDLRDURLRLUDLDRU
0.1.16
10.8. 6
12.2. 4
Size: 4x4 Sum: 198 Moves: RRDRLRLRLDUDULRUDLRLRDURLDU
0. 1.27. 2
13.15.25.23
11.17.19.21
9. 7. 5. 3
Size: 5x5 Sum: 510 Moves: RDRLDULRLRUDUDRLRLUDLRLRLRLRDU
0. 1.44.42.40
6. 8.10.36.38
4. 2.12.34. 3
18.16.14.32.30
20.22.24.26.28
Size: 6x6 Sum: 1095 Moves: RDRLRUDRLRLUDLRLRUDRLRLRLRLRLDDULRUDLRDUDULRDULRLRDURLRLRLU
0. 1.59.57.55.53
65.63.61.47.49.51
4. 2.43.45. 3. 5
33.35.41.11. 9. 7
31.37.39.13.15.17
29.27.25.23.21.19
Bravo Tom!
I will submit this sequence to the OEIS – we will see if it is accepted.
____________________


Commentaires
Enregistrer un commentaire