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:

  1. Démontrer que si chacun de ces rectangles est entier, alors le rectangle R l’est aussi.
  2. La réciproque est-elle vraie?
  3. 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 .

13 réponses
  1. PB
    PB dit :

    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).

    Répondre
  2. PB
    PB dit :

    @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…

    Répondre
  3. Mathoman
    Mathoman dit :

    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!

    Répondre
  4. Mathoman
    Mathoman dit :

    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.

    Répondre
  5. Tahar Boulmezaoud
    Tahar Boulmezaoud dit :

    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.

    Répondre
  6. Mathoman
    Mathoman dit :

    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 :

    Un rectangle est entier si et seulement si posé sur ce background il « couvre » autant de surface « noire » que « blanche ».

    Comment voit-on que la première condition est nécessaire à la deuxième ?

    Répondre
  7. Tahar Boulmezaoud
    Tahar Boulmezaoud dit :

    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…

    Répondre
  8. Mathoman
    Mathoman dit :

    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 rectangle entier ssi mêmes aires blanches et noires 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.

    Répondre
  9. Tahar Boulmezaoud
    Tahar Boulmezaoud dit :

    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.

    Répondre
  10. François-Xavier Vialard
    François-Xavier Vialard dit :

    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!

    Répondre
  11. Mathoman
    Mathoman dit :

    @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.

    Répondre

Laisser un commentaire

Rejoindre la discussion?
N’hésitez pas à contribuer !

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *