Exercice sur un pavage de rectangles
Pas si évident que ça!
Appelons un rectangle entier si sa largeur ou sa longueur est un entier.
Soit R un rectangle constitué d’autres rectangles (leur union est R et ils se touchent seulement sur leurs bords).
Questions:
- Démontrer que si chacun de ces rectangles est entier, alors le rectangle R l’est aussi.
- La réciproque est-elle vraie?
- Cet énoncé en dimension deux peut-on le généraliser à des dimensions plus grandes, par exemple aux cubes?
Réponses:
Cliquez ici pour la solution. Voir aussi les discussions ici et là.
Héhé, je connais. La solution est très surprenante :
vagétenyrf qbhoyrf rg rkcbaragvryyrf pbzcyrkrf
(j’ai fait une petite 13-rotation des lettres pour ne pas dévoiler à ceux qui ne le souhaitent pas).
@PB : connaissez-vous une solution qui n’utilise pas tout cet attirail analytique ?
@Anne : non. Un prof. m’avait laissé entendre qu’il avait une preuve algébrique à base de produit tensoriel au dessus de Q ou de Z, mais je n’ai jamais réussi à la trouver…
Pour une preuve de 1) qui ne soit pas analytique, il y a cet article de François-Xavier Vialard dans la RMS. Téléchargement en format pdf ici.
Merci, j’ai survolé la solution de l’article de la RMS. Intéressante mais moins élégante et difficile à adapter à des dimensions plus grandes.
Je viens de mettre en ligne la solution avec l’exponentielle complexe. Une preuve algébrique à base de produit tensoriel m’intéresserait aussi bien évidemment!
Terence Tao présente une preuve passant par un coloriage, voir ici.
Entretemps j’ai cherché (et trouvé !) la fameuse démonstration par produit tensoriel, voir ici.
Je vous donne ici une solution élémentaire. Imaginons que vous placez "ce grand rectangle" sur un plan colorié en cases noires et blanches comme un échiquier infini dans toutes les directions (On va dire que ce plan est un background). Ces cases carrées sont supposées de coté 1/2. Ainsi, un rectangle est entier si et seulement si posé sur ce background il "couvre" autant de surface "noire" que "blanche". Si c’est vrai pour les petits rectangles constituant le grand, alors c’est forcément vrai pour le grand rectangle lui même. CQFD.
Ca devrait passer aux dimension supérieures sans difficulté majeure.
Merci d’avoir posté cette cette idée élégante. Mais ça va un peu trop vite pour ma lente tête. Vous affirmez l’équivalence suivante :
Comment voit-on que la première condition est nécessaire à la deuxième ?
Il suffit que ce soit vrai pour un rectangle de longueur 1 et de largeur quelconque. Si vous prenez un tel rectangle et vous le placez sur un échiquier dont les cases sont de coté 1/2, vous verrez que peu importe sa largeur, il couvrait toujours la meme aire blanche et d’aire noire.
En fait, j’ai un peu la fleme de faire un dessin ici…
Vous m’avez mal lu, car c’est la direction « condition suffisante » que vous décrivez
ici — or elle est évidente, pas besoin d’un dessin. Mais c’est la direction « condition nécessaire » qui me pose
problème et que je vous prie, encore une fois, de m’expliquer.
Rajout (après reflexion) :
En fait, l’équivalence que vous énoncez
est fausse. Comme contre-exemple il suffit de placer un rectangle de côtés non-entiers de manière que son centre se trouve sur un point du réseau de l’échiquier.Mais heureusement, malgré ce contre-exemple on peut sauver votre preuve. En fait, rien n’empêche de placer le grand rectangle de manière que l’un des sommets se trouve sur le réseau. Il suffit maintenant de prouver que s’il couvre, ainsi placé, autant d’aire blanche que noire, alors il est entier. Et ça c’est faisable avec un petit calcul.
La preuve est juste. Bien évidemment je sous entendais, et je ne l’ai pas écrit, que le rectangle doit avoir un sommet placé aux noeuds. De plus, je ne l’ai pas dit non plus, les cotés du rectangle doivent être parallèles aux lignes de l’échequier.
Lorsque j’ai écrit l’article pour la RMS cité par Simon, je me doutais que ma preuve n’était pas originale. En tout cas, la preuve que je présente est intéressante pour un élève en prépa ou en premières années de fac, puisqu’elle utilise quelques notions simples sur les groupes.
Par la suite, j’ai trouvé un article de Stan Wagon qui compile et discute l’intérêt des différentes preuves dont il a eu connaissance: "fourteen proofs of a result about tiling a rectangle."
Il se trouve que la preuve que je présente suit l’idée "Eulerian path".
La généralisation des preuves (épineuse question: "quelle est la preuve la plus puissante…") est discutée. Enfin la preuve par l’Eulerian path attribuée à Michael Patterson est selon certains critères une des plus puissantes.
A Mathoman donc (et à tous ceux qui se sont intéressés au sujet), jette un coup d’oeil sur cet article pour les généralisations!
@François-Xavier : Merci beaucoup pour cette indication ! L’article dont vous parlez se trouve ici.
Evidemment si j’avais été au courant de cet article, je n’aurais pas commencé à parler de ce problème ici 😉
@Tahar : Merci pour cette preuve, je vais bientôt lui consacrer un billet.