Dépôt numérique de UQTR

Dugré, David

Laconjecture 2⁄3
David Dugué
UQTR
Département mathématiques et d’informatique
Introduction
Une conjecture est une hypothèse formulée
suite à des observations expérimentales. La
conjecture 2/3 fût introduite pour mieux com-
prendre les objets combinatoires que sont les
polyominos.
Plan discret
Définition. Le plan discret est l’ensemble des
points p ∈ Z2. On dira que deux points sont
connexes si leur distance euclidienne est de 1.
Ces points sont également appelés des cellules
et on dénommera le degré d’une cellule comme
le nombre de cellules connexes à celle-ci.
Exemple d’une partie du plan discret
On peut visionner le plan discret comme une
grille quadrillée avec ses points, les cases de la-
dite grille.
Polyominos
Définition. Un polyomino est un ensemble
de cellules connexes dans le plan discret. Un
polyomino serpent est un polyomino de taille
n composé de deux cellules de degré 1 et de n−2
cellules de degré 2.
Exemple de polyominos serpents de taille 4
Problématique
Un des problèmes ouverts des polyominos ser-
pents est celui du polyomino serpent maximal
inscrit dans un rectangle b× h.
Polyomino serpent maximal inscrit dans un
rectangle 5× 4
Le manque de symétrie rendant l’objet diffi-
cile à comprendre mathématiquement, la con-
jecture 2/3 a pour objectif d’établir une borne
supérieure à cette question.
Exploration
Puisqu’un polyomino serpent est composé de
cellules de degré 2, on peut établir une borne
supérieure en déterminant le nombre maximal
de cellules d’au plus degré 2 dans un rectangle
inscrit.
Nombre maximal de cellules d’au plus degré 2
dans un rectangle 6× 6
Via un programme conçu spécialement pour ce
problème, on énumère les solutions pour des
rectangles de plus en plus gros.
Conjecture
Soit un rectangle de taille b× h avec b ≥ 3,
alors le nombre maximal de cellules de degré
d’au plus 2 inscrit dans ce rectangle, dénoté
m≤2(b, h) est égal à:
2bh/3 +

2 , si b = 3 ou si h ≡3 0 et b ≡3 0
4/3 , si b ≥ 4, si h ̸≡3 0 et b ≡3 w
1 , si b ≥ 4, h ≡3 0 et h ̸≡3 w
2/3 , sinon
où x ≡3 y signifie que x÷ 3 = c+ y3 .
Contre-exemple minimal
Définition. Une preuve par contre-
exemple minimal (PCM) est une forme de
preuve par contradiction. On assume qu’une
proposition est fausse et qu’il existe donc un
contre-exemple minimal à celle-ci. On démon-
tre alors que ce contre-exemple ne peut exister
et que la proposition doit donc être vraie.
Preuve
La preuve combinatoire de la conjecture 2/3 est
une preuve par cas qui se résume ainsi:
■ On établit le maximum pour les cas de b = 1
à 6 et h = 1 à 6 et le cas b = h = 7
■ Par PCM, on prouve la conjecture pour les
cas où b = 4, puis b = 5, puis b = 6.
■ Grâce aux deux étapes précédentes, on
établit une borne supérieure pour b > 6
■ Par construction, on arrive à démontrer cette
borne supérieure atteignable, faisant d’elle
un maximum.
Algèbre tropicale
L’algèbre tropicale linéaire opère sur un
semi-anneau où l’addition est le maximum de
deux éléments et la multiplication est l’addition
au sens classique:
x⊕ y = max{x, y} x⊙ y = x+ y
La résolution d’équations matricielles dans
cette algèbre revient à résoudre des systèmes
d’inéquations linéaires sophistiqués.
Modélisation
Dans la théorie des langages formels, on
peut modéliser la problématique de la conjec-
ture 2/3 comme un problème de mot maximal
en deux dimensions composé d’un alphabet bi-
naire {□,■}.
L’algèbre tropicale linéaire permet possible-
ment de modéliser ce problème et de le prouver
algébriquement.
Borne inférieure
Un résultat intéressant de cette conjecture est
qu’en plus d’établir une borne supérieure pour
un polyomino serpent inscrit maximal, on peut,
par construction, établir une borne inférieure
pour ce maximum.
En déplaçant 3 cellules et en enlevant 2, on
assure que le polyomino serpent maximal dans
un rectangle 6× 6 est entre
m≤2(6, 6)− 2 = 24 et m≤2(6, 6) = 26
Autres perspectives
■ Investiguer les cellules d’au plus degré n dans
un espace discret de dimension m
■ Faire le rapprochement entre cette probléma-
tique et certains problèmes d’empaquetage
en optimisation.
Références
[1] Alain Goupil, Marie-Eve Pellerin, and Jérôme de Wouters d’oplinter.
Partially directed snake polyominoes. Discrete Applied Mathemat-
ics, 236:223–234, 2018.
[2] Raphael L’Heureux Alexandre Blondin Massé, Alain Goupil and
Louis Marin. Maximal 2-dimensional binary words of bounded de-
gree. UQAM LACIM, UQTR LACIM, Université Gustave Eiffel
LICM, 2025.
[3] Peter Butkovic. Max-linear Systems: Theory and Algorithms.
Springer, January 2010.


Université du Québec à Trois-Rivières

Not a member yet

La conjecture 2⁄3

8,332

8,581