A224784 Maximum value achievable for n X n version of Le Monde grid problem.

1, 4, 44, 2473, 297136

Offset

1,2

Comments

This is a slightly simplified version of the problem as originally stated in the Le Monde video. For the original version, see A221866.

The problem is as follows (we state it for the 3 X 3 case).

Draw a 3 X 3 square and write "1" in the upper left corner-square. Fill in the other squares one by one according to these rules:

- select an empty square

- write in it the sum of its neighboring squares (a "corner-square" has 3 neighbors, an "edge-square" 5 and the "center-square" 8)

- when all squares are marked, record the highest written value.

Example:

+-----+-----+-----+

| 1 | | |

| | | |

+-----+-----+-----+

| | | |

| | | |

+-----+-----+-----+

| | | |

| | | |

+-----+-----+-----+

+-----+-----+-----+

| 1 | | |

| | | |

+-----+-----+-----+

| | | |

| | | |

+-----+-----+-----+

| | | 0 |

| | | |

+-----+-----+-----+

+-----+-----+-----+

| 1 | 1 | |

| | | |

+-----+-----+-----+

| | | |

| | | |

+-----+-----+-----+

| | | 0 |

| | | |

+-----+-----+-----+

+-----+-----+-----+

| 1 | 1 | |

| | | |

+-----+-----+-----+

| | 2 | |

| | | |

+-----+-----+-----+

| | | 0 |

| | | |

+-----+-----+-----+

+-----+-----+-----+

| 1 | 1 | 3 |

| | | |

+-----+-----+-----+

| | 2 | |

| | | |

+-----+-----+-----+

| | | 0 |

| | | |

+-----+-----+-----+

+-----+-----+-----+

| 1 | 1 | 3 |

| | | |

+-----+-----+-----+

| | 2 | 6 |

| | | |

+-----+-----+-----+

| | | 0 |

| | | |

+-----+-----+-----+

+-----+-----+-----+

| 1 | 1 | 3 |

| | | |

+-----+-----+-----+

| | 2 | 6 |

| | | |

+-----+-----+-----+

| | 8 | 0 |

| | | |

+-----+-----+-----+

+-----+-----+-----+

| 1 | 1 | 3 |

| | | |

+-----+-----+-----+

| | 2 | 6 |

| | | |

+-----+-----+-----+

| 10 | 8 | 0 |

| | | |

+-----+-----+-----+

+-----+-----+-----+

| 1 | 1 | 3 |

| | | |

+-----+-----+-----+

| 22 | 2 | 6 | <--- MAX value = 22 (but 44 is possible)

| | | |

+-----+-----+-----+

| 10 | 8 | 0 |

| | | |

+-----+-----+-----+

References

Eric Angelini and others, A Grid With MAX, Postings to the Math Fun Mailing List, April 14 2013 onwards.

Links

Table of n, a(n) for n=1..5.

Phil Carmody, Gridsplode [A sandbox for experimenting]

Le Monde, Les défis mathématiques du "Monde", épisode 3 : la grille de sommes

Example

From Hans Havermann, Apr 13 2013: (Start)
a(3) is 44.
If we label the 9 squares 1-9:
+-----+-----+-----+
|  1  |  2  |  3  |
|     |     |     |
+-----+-----+-----+
|  4  |  5  |  6  |
|     |     |     |
+-----+-----+-----+
|  7  |  8  |  9  |
|     |     |     |
+-----+-----+-----+
then one can obtain 44 by filling in the squares in the order:
{2, 4, 7, 5, 3, 6, 8, 9} or
{2, 4, 7, 5, 3, 6, 9, 8}
or their symmetrical counterparts
{4, 2, 3, 5, 7, 8, 6, 9} or
{4, 2, 3, 5, 7, 8, 9, 6}
(End)
***********************************************
From Fred W. Helenius, Apr 14 2013: (Start)
a(4) = 2473:
The filled-in grid looks like this:
   1     1  1239  2473
   2     4   419   815
   6    18   100   296
   6    30    48   148
It is easy to figure out the order in which the numbers are entered.
(End)
************************************************
From Fred W. Helenius, Apr 14 2013 and Christian Boyer, Apr 15 2013: (Start)
a(5) = 297136:
There are four solutions, one of which is
     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
(End)
************************************************
The current record for a(6) is 128493518 from Christian Boyer, Apr 16 2013.
************************************************
Further lower bounds from Christian Boyer, Apr 18 2013: (Start)
Here is a better 7 X 7 grid, with 139015458134, using a similar strategy to my 6 X 6:
        1           2           6           18            54     162    162
        1           4          12           36           108     486    810
213342341  1066711707  1706738772  72104324924  139015458134    1404   2700
213342336   640027013  3486463028  17151921630   49759201338    8208   4104
140356800    72985536  4232225497   7726494333   24880751139   24624  12312
42107040    25264224     5614272      1871424        320112  110808  36936
  8421408     8421408     2807136       935712        615600  184680  36936
************************************************
If I continue my "snail" strategy on 8 X 8, I obtain 541048181546137:
          1            2                6               18              54
162                486     486
          1            4               12               36             108
324               1458    2430
17280729221  86403646107     288012153716     437778473776   1313335421640
1313335452366     4212    8100
17280729216  51842187653     149766319904     875556947396   3940006295178
6566677271892    24624   12312
5760243072  11520486144  271062231376625   91645561810642  21888924401648
10506683887182   73872   36936
3789633600   1970609472  541048181546137  178326013015414  64791307846516
32395629305414  221616  110808
1136890080    682134048        151585344         50528448        16842816
2881008         997272  332424
  227378016    227378016         75792672         25264224         8421408
5540400        1662120  332424
It is easy to continue this on larger grids, but is this "snail" strategy the best one?
If so the game is less interesting.
(End)

Crossrefs

Cf. A221866.

Sequence in context: A134174 A296729 A157193 * A243221 A238816 A327196

Adjacent sequences: A224781 A224782 A224783 * A224785 A224786 A224787

Keyword

nonn,nice

Author

N. J. A. Sloane, Apr 17 2013

Status

approved