Are all paths (for max) connected? Is there always an optimal path that is greedy (chooses at every step one of the squares that has the highest value from that point)? Searching greedy sequences only would seem to be reasonably fast and productive . . . On Mon, Apr 15, 2013 at 11:26 AM, Christian Boyer <cboyer@club-internet.fr> wrote:
Yes, 297136 seems to be the best score for 5x5. Interesting and "math-fun", there are 3 other solutions with the same score, using different paths and different intermediate numbers. One of them:
1 1 40 73 235 2 6 33 162 470 2 10 16 1313 632 148574 49530 16947 3906 1945 297136 99032 32555 11702 5851
If we sum the 25 numbers of this solution, we obtain 670174.
Sums of the four solutions scoring 297136 are: 670162, 670174 (above), 678236 (Fred), 689336. The last one is close to Fred's, only inverting the two last moves:
1 1 53181 106357 297136 2 4 16515 36661 154118 6 12 9046 7452 3648 18 54 156 1368 2280 18 90 300 456 456
Christian.
-----Message d'origine----- De : math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] De la part de Fred W. Helenius Envoyé : lundi 15 avril 2013 01:29 À : math-fun@mailman.xmission.com Objet : Re: [math-fun] A grid with MAX
On 4/14/2013 5:43 PM, Allan Wechsler wrote:
Conjecture: the highest achievable outcome can be achieved by a king's-move-connected path through the grid. This seems very obvious to me intuitively, but I'm too scatterbrained to prove it at the moment. If it's true, it should speed up searches considerably.
It's plausible--if only because the 3x3 and 4x4 solutions work that way--but I don't see a proof. But it would be a great thing to know because assuming the correctness of Allan's conjecture reduces the computation for 5x5 to under 10 minutes. The conjectural champion value is then 297136, from this grid:
1 1 53181 106357 143018
2 4 16515 36661 297136
6 12 9046 7452 3648
18 54 156 1368 2280
18 90 300 456 456
Even with this improvement, 6x6 still looks difficult; possibly on the order of CPU-weeks.
As ever, independent confirmation would be welcome.
-- Fred W. Helenius fredh@ix.netcom.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --