Ok, Tom, I'll do that asap! (will keep you informed -- and the list too) Many thanks again and again! à+ É. Catapulté de mon aPhone
Le 21 mai 2019 à 08:35, Tom Karzes <karzes@sonic.net> a écrit :
I think I'll leave the OEIS to you Éric. It's your puzzle. I just found a few terms in the sequence...
Tom
Éric Angelini writes:
Many thanks, Tom, well done! The seq of optimal solutions for the n x n squares is definitely worth entering the OEIS, I think. Sums are:
S = 0, 9, 59, 198, 510, 1095, ...
Would you submit that to Neil? Again, bravo! à+ É. Catapulté de mon aPhone
Le 21 mai 2019 à 05:57, Tom Karzes <karzes@sonic.net> a écrit :
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 Cells: 0 1 5 3
Size: 3x3 Sum: 59 Moves: RDLRDURLRLUDLDRU Cells: 0 1 16 10 8 6 12 2 4
Size: 4x4 Sum: 198 Moves: RRDRLRLRLDUDULRUDLRLRDURLDU Cells: 0 1 27 2 13 15 25 23 11 17 19 21 9 7 5 3
Size: 5x5 Sum: 510 Moves: RDRLDULRLRUDUDRLRLUDLRLRLRLRDURLDUDULRDURLRL Cells: 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: RDRLRUDRLRLUDLRLRUDRLRLRLRLRLDUDULRUDLRDUDULRDULRLRDURLRLRLUDRLRL Cells: 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
Tom
Tom Karzes writes:
More generally:
For an nxn square, the simplest solution is to use a simple zig-zag pattern (or a simple spiral pattern), with each even number appearing in the square (and the odd numbers appearing outside of the square):
0 2 6 4
or:
0 2 4 10 8 6 12 14 16
The sum for this pattern is n^4 - n^2.
The only possible way to improve on this is for two consecutive numbers to appear in the square, which can only be done within the first n-1 moves.
The simplest such pattern is to make the first move within the square, then continue with the previous pattern:
0 1 5 3
or:
0 1 3 9 7 5 11 13 15
The sum for this pattern is n^4 - 2*n^2 + 1.
This is optimal for 2x2, but not for 3x3 and higher, since for those cases the first *two* (or more) moves can remain within the square.
The trick to these cases is efficiently filling in the remaining squares once the distance has reached n. My solution relied on the fact that a simple 4-move spiral will move you diagonally by 2 in each direction. But as n increases, finding an optimal fill pattern becomes much more complex.
I may look at the 4x4 case a bit, but even if I find a decent solution, there will probably be no guarantee that it's optimal.
Tom
Éric Angelini writes:
Waow! I had found the same 2 x 2 as yours, my idea was that the 3 x 3 built on that one was leading to 64 (insread of my 63). But your 59 is beautiful! Could you find the smallest 4 x 4 and submit to Neil's OEIS this (starting) sequence? I'm unable to find anything above the 2 x 2 square!-) à+ É. Catapulté de mon aPhone
Le 21 mai 2019 à 00:19, Tom Karzes <karzes@sonic.net> a écrit :
Ok, sure. For a 3x3 square:
R D L R D U R L R L U D D L U R
0 1 16 10 8 6 12 2 4
(sum = 59)
Tom
Éric Angelini writes: > Yes, well done, Tom! > Next square? > ;-) > à+ > É. > Catapulté de mon aPhone > > >> Le 20 mai 2019 à 23:31, Tom Karzes <karzes@sonic.net> a écrit : >> >> Wouldn't the followiung work for a 2x2 square? >> >> R U D R L >> >> 0.1 >> 5.3 >> >> (sum = 9) >> >> Tom >> >> Éric Angelini writes: >>> Hello MathFun >>> The aim of this challenge is to fill a square (that has a 0 --zero-- in its upper-left corner) with integers. 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 >>> >>> Can you beat my personal records? And find records for bigger squares? >>> >>> (forgive me if this is old hat) >>> (some illustrations here, on my personal weblog): >>> https://cinquantesignes.blogspot.com/2019/05/jump-and-fill-my-square.html >>> >>> Best, >>> É. >>>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun