Structures

(English translation after the French version)

Vous disposez d’une quantité infinie de carrés de taille identique, portant chacun un chiffre allant de 0 à 9. Vous posez un carré 0 sur la table — c’est le début de la « structure ».

.....

..0..

..... 

Le but du jeu est de poser à chaque étape un nombre N qui soit en contact avec la structure existante (par le côté d’un carré au moins – donc pas par un sommet).

N doit toujours être le plus petit nombre qui ne figure pas dans la structure, même sous forme de substring. De même, son placement ne peut-il faire apparaître un nombre déjà présent dans ladite structure.

On pose donc le 1 à gauche (ou au-dessus) du 0 pour former 10 (on ne peut pas former de nombre qui commence par 0).

.....

.10..

..... 

Où placer 2 ?

Important : il faut toujours placer N de manière à minimiser la somme des nouveaux nombres qui apparaissent dans la structure (c’est la règle verte).

Puisque 2 doit se coller à la structure par un côté au moins, les seules cases qui lui sont disponibles sont celles marquées ci-dessous en rouge. Voyons la somme qui en résulte à chaque fois :

.ab..

c10d.

.ef.. 

2 en a —> 23 (= 2 + 21)

2 en b —> 22 (= 2 + 20)

2 en c —> 233 (= 2 + 21 + 210)

2 en d —> 104 (= 2 + 102)

2 en e —> 14 (= 2 + 12)

2 en f —> interdit (car 02 commence par 0).

La structure devient donc :

.....

.10..

.2...

..... 

(Les nombres et les substrings de la structure se lisent de gauche à droite et de haut en bas uniquement).

La suite des totaux successifs minimaux est T :

T = 0, 11, 14, …

La suite des termes cumulés de T est Q :

Q = 0, 11, 25, …

Les nombres visibles dans la structure sont :

N = 0, 1, 2, 10, 12, …

Où mettre 3 ?

Les cases où 3 peut se poser sont toujours en rouge :

.ab..

c10d.

e2f..

.g... 

Le plus petit total s’atteint avec le 3 posé en b : 3 + 30 = 33

.....

..3..

.10..

.2...

.....

Totaux T = 0, 11, 14, 33, …

Cumul Q des T = 0, 11, 25, 58, …

Nombres N visibles dans la structure = 0, 1, 2, 3, 10, 12, 30, …

Voici la « structure minimale » résultant du placement des nombres de 0 à 9 :

........

.....78.

....34..

...10...

..52....

.96.....

........ 

Totaux T = 0, 11, 14, 33, 38, 57, 62, 81, 86, 105, …

Cumul Q des T = 0, 11, 25, 58, 96, 153, 215, 296, 382, 487, …

Nombres N visibles dans la structure = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 30, 34, 52, 56, 74, 78, 96, …

Le nombre à placer maintenant n’est pas 10 (il est déjà présent au milieu de la structure) mais 11 (même si ce 11 est la répétition du nombre 1, déjà présent : on ne peut faire réapparaître une substring de longueur k que si toutes les substrings de longueur k-1 figurent déjà dans la structure – c’est la règle bleue. Elle a l’air compliquée mais elle est logique et « naturelle », il ne faut pas trop s’en soucier pour l’instant).

Le placement de N ne peut pas faire apparaître deux nombres identiques dans la structure, même sous forme de substring (c’est la règle noire).

Voici la structure à laquelle nous sommes parvenus après avoir posé les nombres allant de 0 à 25 ; est-elle minimale ? Si oui, regardons bien, car il se produit quelque chose d’intéressant :

.......................

...........2...........

...........5...........

..........201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........

............10.........

...........52..........

..........96...........

.........13............

....................... 

... On peut poser le terme suivant, 26, de deux manières différentes (emplacement rouge ou bleu) – pour le même total minimal de 88 :

.......................

..........2............

..........62...........

...........5...........

......26..201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........

............10.........

...........52..........

..........96...........

.........13............

....................... 

On voit ci-dessous que les deux branches peuvent, au choix, être étendues avec les termes 27, 28 et 29 :

.......................

.......2...............

.......92..............

........82.............

...29....72............

....28....62...........

.....27....5...........

......26..201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........

............10.........

...........52..........

..........96...........

.........13............

....................... 

Il y a même moyen de panacher !

C’est ce que nous avons fait quand nous avons vu que procéder ainsi permettait de construire une structure accueillant 35 avec un total des plus petits, soit 433 = 35 + 36 +362 :

.......................

.......................

..........2............

....29...362...........

.....28..5.5...........

......27..201..........

.......24.2.91.........

........231..71........

.........3....61.......

.........2.....51......

................4......

...............11......

..............78.......

.............34........

............10.........

...........52..........

..........96...........

.........13............

....................... 

Les termes à greffer maintenant sont, 37, 38, 39 et 40 – avec la même question lancinante : la structure atteinte ci-dessous fut-elle minimale à chaque étape ? Il fallait qu’elle le soit selon la règle verte des totaux minimums.

Autre question, évidente (soulevée lors du panachage 26, 27)  : faut-il calculer systématiquement toutes les branches possibles ? Il semble que oui, car certaines structures pourraient se bloquer... en étant incapables d’accueillir le plus petit absent suivant.

.......................

..........2............

....29...362...........

.....28..5.5...........

......27..201..........

.......24.2.91.........

........231..71........

.........3....61.......

.........2.....51......

................437....

...............11.38...

..............78...39..

.............34.....40.

............10.........

...........52..........

..........96...........

.........13............

....................... 

Voici le film, image par image, qui mène à la structure ci-dessus (le N à droite de chaque image est l’ensemble des nombres visibles dans la structure ; T est la somme que produit la greffe du plus petit terme absent – absent voulant dire que ce entier est invisible dans la structure – même en tant que substring d’un entier plus grand – c’est toujours la règle noire] :

.......................

.......................

.......................

.......................

.............0......... N : 0, …

.......................

.......................

.......................

....................... T = 0

.......................

.......................

.......................

.......................

............10......... N : 0,1,10, …

.......................

.......................

.......................

....................... T = 11 = 1 + 10

.......................

.......................

.......................

.......................

............10......... N : 0,1,2,10,12, …

............2..........

.......................

.......................

....................... T = 14 = 2 + 12

.......................

.......................

.......................

.............3.........

............10......... N : 0,1,2,3,10,12, 30, …

............2..........

.......................

.......................

....................... T = 33 = 3 + 30

.......................

.......................

.......................

.............34........

............10......... N : 0,1,2,3,4,10,12, 30,34, …

............2..........

.......................

.......................

....................... T = 38 = 4 + 34

 

.......................

.......................

.......................

.............34........

............10......... N : 0,1,2,3,4,5,10,12, 30,34,52, …

...........52..........

.......................

.......................

....................... T = 57 = 5 + 52

.......................

.......................

.......................

.............34........

............10......... N : 0,1,2,3,4,5,6,10,12, 30,34,52,56, …

...........52..........

...........6...........

.......................

.......................T = 62 = 6 + 56

 

.......................

.......................

..............7........

.............34........

............10......... N : 0,1,2,3,4,5,6,7,10,12, 30,34,52,56,74, …

...........52..........

...........6...........

.......................

.......................T = 81 = 7 + 74

.......................

.......................

..............78.......

.............34........

............10......... N : 0,1,2,3,4,5,6,7,8,10,12, 30,34,52,56,74,78, …

...........52..........

...........6...........

.......................

.......................T = 86 = 8 + 78

.......................

.......................

..............78.......

.............34........

............10......... N : 0,1,2,3,4,5,6,7,8,9,10,12, 30,34,52,56,74,78,96, …

...........52..........

..........96...........

.......................

.......................T = 105 = 9 + 96

.......................

...............11......

..............78.......

.............34........

............10......... N : 0,1,2,3,4,5,6,7,8,9,10,11,12,18, 30,34,52,56,74,78,96, …

...........52..........

..........96...........

.......................

.......................T = 29 = 11 + 18

.......................

...............11......

..............78.......

.............34........

............10......... N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,18, 30,34,52,56,74,78,93, 96, …

...........52..........

..........96...........

.........13............

.......................T = 106 = 13 + 93

.......................

................1......

................4......

...............11......

..............78.......

.............34........

............10......... N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,18, 30,34,41,52,56,74,78,93,96,141, …

...........52..........

..........96...........

.........13............

.......................T = 196 = 14 + 41 + 141

.......................

.......................

...............1.......

...............51......

................4......

...............11......

..............78.......

.............34........

............10......... N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,18, 30,34,41,51,52,56,74,78,93,96,141, …

...........52..........

..........96...........

.........13............

.......................T = 66 = 15 + 51

.......................

..............1........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18, 30,34,41,51,52,56,61,74,78,93,96,

............10.........  141, …

...........52..........

..........96...........

.........13............

.......................T = 77 = 16 + 61

.......................

.............1.........

.............71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18, 30,34,41,51,52,56,61,71,74,78,

............10.........  93,96,141, …

...........52..........

..........96...........

.........13............

.......................T = 88 = 17 + 71

.......................

............1..........

............91.........

.............71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,30,34,41,51,52,56,61,71,74,

............10.........  78,91,93,96,141, …

...........52..........

..........96...........

.........13............

.......................T = 110 = 19 + 91

.......................

..........201..........

............91.........

.............71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,30,34,41,51,52,56,61,71,

............10.........  74,78,91,93,96,141,201, …

...........52..........

..........96...........

.........13............

.......................T = 221 = 20 + 201

.......................

..........201..........

..........2.91.........

..........1..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,30,34,41,51,52,56,

............10.........  61,71,74,78,91,93,96,141,221, …

...........52..........

..........96...........

.........13............

.......................T = 264 = 21 + 22 + 221 

.......................

..........201..........

..........2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,30,31,34,41,51,

............10.........  52,56,61,71,74,78,91,93,96,141,221,231, …

...........52..........

..........96...........

.........13............

.......................T = 285 = 23 + 31 + 231

.......................

..........201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,30,31,34,

............10.........  41,42,51,52,56,61,71,74,78,91,93,96,141,221,231, …

...........52..........

..........96...........

.........13............

.......................T = 66 = 24 + 42

.......................

...........2...........

...........5...........

..........201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,30,31,

............10.........  34,41,42,50,51,52,56,61,71,74,78,91,93,96,141,221,231,250, …

...........52..........

..........96...........

.........13............

.......................T = 302 = 25 + 50 + 250

.......................

..........2............

..........62...........

...........5...........

..........201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,30,

............10.........  31,34,41,42,50,51,52,56,61,62,71,74,78,91,93,96,141,221,231,250, …

...........52..........

..........96...........

.........13............

.......................T = 88 = 26 + 62

.......................

..........2............

..........62...........

...........5...........

......27..201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,

............10.........  30,31,34,41,42,50,51,52,56,61,62,71,72,74,78,91,93,96,141,221,231,250, …

...........52..........

..........96...........

.........13............

.......................T = 99 = 27 + 72

 

.......................

..........2............

..........62...........

.....28....5...........

......27..201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,

............10.........  28,30,31,34,41,42,50,51,52,56,61,62,71,72,74,78,82,91,93,96,141,221,231,

...........52..........  250, ...

..........96...........

.........13............

.......................T = 110 = 28 + 82

 

.......................

..........2............

....29....62...........

.....28....5...........

......27..201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,

............10.........  28,29,30,31,34,41,42,50,51,52,56,61,62,71,72,74,78,82,91,92,93,96,141,

...........52..........  221,231,250, ... 

..........96...........

.........13............

.......................T = 121 = 29 + 92

 

.......................

..........2............

....29....62...........

.....28....5...........

......27..201..........

.......24.2.91.........

........231..71........

.........3....61.......

.........2.....51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,

............10.........  28,29,30,31,32,33,34,41,42,50,51,52,56,61,62,71,72,74,78,82,91,92,93,96,

...........52..........  141,221,250,332, ... 

..........96...........

.........13............

.......................T = 397 = 32 + 33 + 332

.......................

..........2............

....29...362...........

.....28..5.5...........

......27..201..........

.......24.2.91.........

........231..71........

.........3....61.......

.........2.....51......

................4......

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,

............10.........  28,29,30,31,32,33,34,35,36,41,42,50,51,52,56,61,62,71,72,74,78,82,91,92,

...........52..........  93,96,141,221,250,332,362, ... 

..........96...........

.........13............

.......................T = 433 = 35 + 36 + 362

.......................

..........2............

....29...362...........

.....28..5.5...........

......27..201..........

.......24.2.91.........

........231..71........

.........3....61.......

.........2.....51......

................437....

...............11......

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,

............10.........  28,29,30,31,32,33,34,35,36,37,41,42,43,50,51,52,56,61,62,71,72,74,78,82,

...........52..........  91,92,93,96,141,221,250,332,362,437, ... 

..........96...........

.........13............

.......................T = 517 = 37 + 43 + 437

.......................

..........2............

....29...362...........

.....28..5.5...........

......27..201..........

.......24.2.91.........

........231..71........

.........3....61.......

.........2.....51......

................437....

...............11.38...

..............78.......

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,

............10.........  28,29,30,31,32,33,34,35,36,37,38,41,42,43,50,51,52,56,61,62,71,72,73,74,

...........52..........  78,82,91,92,93,96,141,221,250,332,362,437, ... 

..........96...........

.........13............

.......................T = 111 = 38 + 73

.......................

..........2............

....29...362...........

.....28..5.5...........

......27..201..........

.......24.2.91.........

........231..71........

.........3....61.......

.........2.....51......

................437....

...............11.38...

..............78...39..

.............34........ N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,

............10.........  28,29,30,31,32,33,34,35,36,37,38,39,41,42,43,50,51,52,56,61,62,71,72,73,

...........52..........  74,78,82,83,91,92,93,96,141,221,250,332,362,437, ... 

..........96...........

.........13............

.......................T = 122 = 39 + 83

.......................

..........2............

....29...362...........

.....28..5.5...........

......27..201..........

.......24.2.91.........

........231..71........

.........3....61.......

.........2.....51......

................437....

...............11.38...

..............78...39..

.............34.....40. N : 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,

............10.........  28,29,30,31,32,33,34,35,36,37,38,39,41,42,43,50,51,52,56,61,62,71,72,73,

...........52..........  74,78,82,83,91,92,93,96,141,221,250,332,362,437, ... 

..........96...........

.........13............

.......................T = 134 = 40 + 94

Le prochain terme à placer est 44 : lui voyez-vous un emplacement ? Minimal ? (il y a un nouvel embranchement qui naît derrière le 40 rouge ci-dessus ! On peut placer un 4 à la fin de 40 pour former 404 ; on a ensuite le choix pour le deuxième 4 de 44 : en a ou en b ?-)...

...............11.38... 

..............78...39.a 

.............34.....404 

............10........b 

...........52..........  

Voilà, j’espère ne pas avoir laissé trop d’erreurs !

Voici les deux suites T et Q en rapport avec ce puzzle (susceptibles d’entrer dans l’OEIS ?) Pour mémoire :

T est la suite des sommes minimales produites par le placement d’un nouvel N.

Q est la suite cumulée des termes de T.

T = 0, 11, 14, 33, 38, 57, 62, 81, 86, 105, 29, 106, 196, 66, 77, 88, 110, 221, 264, 285, 66, 302, 88, 99, 110, 121, 397, 433, 517, 111, 122, 134,  ...

Q = 0, 11, 25, 58, 96, 153, 215, 296, 382, 487, 516, 622,  818, 884, 961, 1049, 1159, 1380, 1644, 1929, 1995, 2297, 2385, 2484, 2594, 2991, 3424, 3941, 4052, 4174, 4308, …

____________________________

(Short Google-Translated English version)

You have an infinite number of squares of the same size, each bearing a number from 0 to 9. You put a square 0 on the table - this is the beginning of the "structure".

.....

..0..

..... 

The object of the game is to put a number N at each step which is in contact with the existing structure (by the side of at least one square – therefore not by a vertex).

N must always be the smallest number that is not in the structure, even as a substring. Similarly, its placement cannot reveal a number already present in said structure.

We therefore put the 1 to the left (or above) of the 0 to form 10 (we cannot form a number that begins with 0).

.....

.10..

..... 

Where to place 2?

Important: you must always place N in such a way as to minimize the sum of the new numbers that appear in the structure (this is the green rule).

Since 2 must stick to the structure on at least one side, the only squares available to it are those marked below in red. Let’s see the resulting sum each time:

.ab..

c10d.

.ef.. 

2 in a —> 23 (= 2 + 21)

2 in b —> 22 (= 2 + 20)

2 in c —> 233 (= 2 + 21 + 210)

2 in d —> 104 (= 2 + 102)

2 in e —> 14 (= 2 + 12)

2 in f —> forbidden (as 02 has a leading 0).

The structure becomes:

.....

.10..

.2...

..... 

(Numbers and substrings in the structure read left to right and top to bottom only).

The sequence of minimal successive totals is T:

T = 0, 11, 14, …

The sequence of cumulative terms of T is Q:

Q = 0, 11, 25, …

The numbers visible in the structure are:

N = 0, 1, 2, 10, 12, …

Where to put 3?

The squares where 3 can land are in red as before:

.ab..

c10d.

e2f..

.g... 

The smallest total is reached with the 3 placed in b: 3 + 30 = 33

.....

..3..

.10..

.2...

..... 

Totals T = 0, 11, 14, 33, …

Cumulative terms Q = 0, 11, 25, 58, …

Visible numbers N = 0, 1, 2, 3, 10, 12, 30, …

Here is the "minimal structure" resulting from the placement of the numbers from 0 to 9:

........

.....78.

....34..

...10...

..52....

.96.....

........ 

Totals T = 0, 11, 14, 33, 38, 57, 62, 81, 86, 105, …

Cumulative terms Q = 0, 11, 25, 58, 96, 153, 215, 296, 382, 487, …

Visible numbers N = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 30, 34, 52, 56, 74, 78, 96, …

The number to place now is not 10 (it is already present in the middle of the structure) but 11 (even if this 11 is the repetition of the number 1, already present: a substring of length k can only reappear if all substrings of length k-1 are already in the structure – this is the blue rule. It looks complicated but is logical and "natural", so don't worry too much about it for now) .

Placing N cannot cause two identical numbers to appear in the structure, even as a substring (this is the black rule).

Here is the structure we arrived at after laying down the numbers from 0 to 25; is it minimal? If so, let's take a good look, because something interesting happens:

.......................

...........2...........

...........5...........

..........201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........

............10.........

...........52..........

..........96...........

.........13............

....................... 

... We can put the next term, 26, in two different ways (red or blue space) – for the same minimum total of 88:

.......................

..........2............

..........62...........

...........5...........

......26..201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........

............10.........

...........52..........

..........96...........

.........13............

....................... 

We see below that the two branches can optionally be extended with the terms 27, 28 and 29:

.......................

.......2...............

.......92..............

........82.............

...29....72............

....28....62...........

.....27....5...........

......26..201..........

.......24.2.91.........

........231..71........

..............61.......

...............51......

................4......

...............11......

..............78.......

.............34........

............10.........

...........52..........

..........96...........

.........13............

....................... 

There is even a way to mix it up!

This is what we did when we saw that proceeding in this way allowed us to build a structure accommodating 35 with a total of the smallest, i.e. 433 = 35 + 36 +362:

.......................

.......................

..........2............

....29...362...........

.....28..5.5...........

......27..201..........

.......24.2.91.........

........231..71........

.........3....61.......

.........2.....51......

................4......

...............11......

..............78.......

.............34........

............10.........

...........52..........

..........96...........

.........13............

.......................

The terms to be grafted on now are, 37, 38, 39 and 40 – with the same nagging question: was the structure reached below minimal at each stage? It had to be according to the green rule of minimum totals.

Another question, obvious (raised during the mixing 26, 27): should we systematically calculate all the possible branches? It seems so, because some structures could become blocked... by being unable to accommodate the next smallest absentee.

.......................

..........2............

....29...362...........

.....28..5.5...........

......27..201..........

.......24.2.91.........

........231..71........

.........3....61.......

.........2.....51......

................437....

...............11.38...

..............78...39..

.............34.....40.

............10.........

...........52..........

..........96...........

.........13............

....................... 

(The French version shows, step by step, how to reach the above structure – modulo errors by the author; the N's on the right of each image are the numbers visible in the said structure, and T is the minimal sum achieved.)