David Madore's WebLog: Petite devinette mathématique : un damier irrégulier

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #2085 [older|newer] / Entrée #2085 [précédente|suivante]:

(samedi)

Petite devinette mathématique : un damier irrégulier

Carré divisé en 12×12 rectanglesÀ part mon choix lamentable de couleurs, qu'est-ce que l'image ci-contre a de (mathématiquement) remarquable ?

Les couleurs sont juste censées être une indication. La question porte sur la manière dont le carré est divisé en 12×12 rectangles.

Si on veut des valeurs plus précises, à cinq chiffres significatifs, les largeurs des colonnes en fraction du tout sont :

0.10367, 0.02778, 0.15922, 0.00744, 0.13889, 0.06300, 0.06300, 0.13889, 0.00744, 0.15922, 0.02778, 0.10367

et les hauteurs des lignes sont :

0.06699, 0.11603, 0.06699, 0.06699, 0.11603, 0.06699, 0.06699, 0.11603, 0.06699, 0.06699, 0.11603, 0.06699

Voici quelques faits supplémentaires (peut-être trompeurs, mais vrais) :

Je donnerai la solution — qui ne fait pas appel à des choses compliquées — en éditant ce post.

(Les gens qui ont déjà eu la réponse — et notamment les lecteurs de forum maths à l'ENS — n'ont pas le droit de participer ! ☺)

La réponse () (je ne la cache pas, parce que c'est vraiment trop long) :

Chacune des diagonales du damier irrégulier a la même aire qu'elle aurait dans un damier 12×12 régulier : le rectangle (rouge) du coin en haut à gauche a une surface égale à (1/12)² = 1/144 du carré tout entier, les deux (orange) à sa droite et en-dessous ont, ensemble, une aire de 2/144 = 1/72 du carré entier, les trois rectangles adjacents ont une aire totale de 3/144 et ainsi de suite — n'importe quelle suite de n rectangles consécutivement arrangés en diagonale de bord en bord a une surface totale égale à n/144 du carré. (Ainsi, dans les nombres donnés ci-dessus, 0.10367×0.06699=(1/144), 0.02778×0.06699+0.10367×0.11603=(2/144), et ainsi de suite.) En particulier, avec mon choix de couleurs, chaque couleur couvre une surface égale de l'image (mais la propriété que j'énonce est plus forte).

Ce qui rend la chose remarquable, c'est qu'il n'y a pas moyen de faire ça (en écartant bien sûr le damier régulier) pour une taille moindre que 12×12 si on impose aux largeurs des colonnes et hauteurs des lignes d'être strictement positives (en taille 10×10 il y a une solution ou certaines lignes/colonnes sont réduites à 0). Et en 12×12 c'est, à symétrie près, la seule solution (autre que le damier régulier et les deux qui ont des lignes/colonnes réduites à 0).

Le problème peut aussi se poser avec des dés : on se demande si on peut construire deux dés à m faces, c'est-à-dire deux distributions de probabilités sur m entiers consécutifs (de 0 à m−1 ou de 1 à m, ça ne change rien) de manière que si on tire ces deux dés simultanément et qu'on considère leur somme, on obtienne bien la distribution de probabilité attendue pour la somme sur un tirage de deux dés à m faces non pipés. Pour m<10 la seule façon d'y arriver est d'avoir deux dés non pipés. Pour m=12, les deux distributions de probabilité données par les deux suites de 12 nombres ci-dessus définissent deux dés pipés dont la somme est non pipée.

Maintenant, comment (p/t)rouve-t-on ça ? L'idée initiale est très séduisante : on considère le polynôme de degré m−1 dont les coefficients sont les largeurs des colonnes (soit a0 + a1·x + ⋯ + am−1·xm−1 où les ai sont les largeurs des colonnes) et celui dont les coefficients sont les hauteurs des lignes (b0 + b1·x + ⋯ + bm−1·xm−1) : en les multipliant, on obtient le polynôme (de degré 2m−2) dont les coefficients sont les aires des diagonales (le coefficient constant est a0·b0, c'est la surface du coin en haut à gauche, le suivant est a1·b0 + a0·b1, c'est la surface de la diagonale adjacente, et ainsi de suite). La contrainte demande donc que ce produit soit le même que le produit des deux polynômes représentant une distribution uniforme, autrement dit (1+x+x2+⋯+xm−1)/m (au carré, donc, pour le produit). La question qui se pose est donc d'écrire le polynôme (1+x+x2+⋯+xm−1)2, c'est-à-dire ((1−xm)/(1−x))2 (j'ai retiré le coefficient multiplicatif 1/m de normalisation globale, sachant qu'on peut toujours renormaliser) comme produit de deux polynômes de degré m−1 à coefficients positifs (voire strictement positifs).

Malheureusement, la suite est plus décevante. Le polynôme 1+x+x2+⋯+xm−1 se factorise dans ℝ[x] comme produit des (1 − 2·cos(2iπ/mx + x²) pour i allant de 1 à ⌊(m−1)/2⌋ ainsi que (1+x) lorsque m est pair. On va donc chercher à répartir les exposants (le total devant être 2) sur chacun de ces facteurs de manière à avoir le bon degré de part et d'autre, et n'avoir que des coefficients positifs (ou strictement positifs), et je ne vois pas de façon plus intelligente pour ça que d'essayer toutes les combinaisons possibles, typiquement par ordinateur. S'agissant de m=12, les facteurs de 1+x+x2+⋯+x11 sont (1−√3·x+x²), (1−x+x²), (1+x²), (1+x+x²), (1+√3·x+x²) et (1+x). Et le produit de

(1−√3·x+x²) × (1−x+x²) × (1+x²) × (1+x+x²)2 × (1+x) = 1 + 0.26795·x + 1.53590·x2 + 0.07180·x3 + 1.33975·x4 + 0.60770·x5 + 0.60770·x6 + 1.33975·x7 + 0.07180·x8 + 1.53590·x9 + 0.26795·x10 + x11

et de

(1−√3·x+x²) × (1−x+x²) × (1+x²) × (1+√3·x+x²)2 × (1+x) = 1 + 1.73205·x + x2 + x3 + 1.73205·x4 + x5 + x6 + 1.73205·x7 + x8 + x9 + 1.73205·x10 + x11

donne bien (1+x+x2+⋯+x11)2, les deux ayant des coefficients positifs ; en les renormalisant (pour que la somme des coefficients, c'est-à-dire la valeur en 1, soit 1), on obtient les deux suites de nombres annoncées.

On peut aussi faire varier m et chercher le nombre de manières dont le polynôme (1+x+x2+⋯+xm−1)2 s'écrit comme produit de deux polynômes unitaires de degré m−1 à coefficients positifs, ou strictement positifs : ceci revient à compter le nombre de façons dont on peut fabriquer un damier m×m à diagonales régulières (sans ou avec la contrainte de non-nullité des lignes et colonnes ; et en comptant une fois le damier régulier et deux fois chaque damier régulier à cause de la possibilité d'échanger lignes et colonnes). Ces suites sont majorées par 3m/2⌋ (qui est le nombre total de manières d'écrire le polynôme comme produit de deux polynômes unitaires à coefficients réels, sans autre contrainte). Je trouve :

m12345678 910111213141516 1718192021
pos.11111111 13175799 1315172537
s.pos.11111111 11135799 1311171933

La seconde suite est sans doute plus naturelle (parce que si on va autoriser des coefficients égaux à 0, autant supprimer la contrainte que le degré des polynômes soit exactement m−1 parce que ça correspond à demander la non-nullité du dernier coefficient). Je l'ai soumise à l'OEIS.

↑Entry #2085 [older|newer] / ↑Entrée #2085 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées