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

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 a₀ + a₁·x + ⋯ + a_m−1·x^m−1 où les a_i sont les largeurs des colonnes) et celui dont les coefficients sont les hauteurs des lignes (b₀ + b₁·x + ⋯ + b_m−1·x^m−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 a₀·b₀, c'est la surface du coin en haut à gauche, le suivant est a₁·b₀ + a₀·b₁, 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+x²+⋯+x^m−1)/m (au carré, donc, pour le produit). La question qui se pose est donc d'écrire le polynôme (1+x+x²+⋯+x^m−1)², c'est-à-dire ((1−x^m)/(1−x))² (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+x²+⋯+x^m−1 se factorise dans ℝ[x] comme produit des (1 − 2·cos(2iπ/m)·x + 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+x²+⋯+x¹¹ 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²)² × (1+x) = 1 + 0.26795·x + 1.53590·x² + 0.07180·x³ + 1.33975·x⁴ + 0.60770·x⁵ + 0.60770·x⁶ + 1.33975·x⁷ + 0.07180·x⁸ + 1.53590·x⁹ + 0.26795·x¹⁰ + x¹¹

et de

(1−√3·x+x²) × (1−x+x²) × (1+x²) × (1+√3·x+x²)² × (1+x) = 1 + 1.73205·x + x² + x³ + 1.73205·x⁴ + x⁵ + x⁶ + 1.73205·x⁷ + x⁸ + x⁹ + 1.73205·x¹⁰ + x¹¹

donne bien (1+x+x²+⋯+x¹¹)², 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+x²+⋯+x^m−1)² 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 3^⌊m/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 :

m	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
pos.	1	1	1	1	1	1	1	1	1	3	1	7	5	7	9	9	13	15	17	25	37
s.pos.	1	1	1	1	1	1	1	1	1	1	1	3	5	7	9	9	13	11	17	19	33

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.