Paver des rectangles

Vous vous souvenez du puzzle impossible de la dernière vidéo ? Non ? Il est encore temps de vous rattraper en allant la regarder alors !

Dans notre cas, pour prouver que notre puzzle n’était pas réalisable, on utilisait un argument de parité : en coloriant une case sur deux du rectangle à remplir, on en déduisait que les pièces fournies ne pouvait le recouvrir entièrement.

Voilà pourtant un nouveau problème : cette fois-ci, vous devez paver un rectangle de taille 14 x 10 cases avec des pièces rectangulaires de 1 x 4 cases. Si on colorie nos rectangles en noir et blanc, on remarquera que chacun présentera autant de cases noires que de cases blanches… Et pourtant, là encore, le puzzle s’avère impossible !

Pour montrer notre résultat, nous pouvons de nouveau procéder à un coloriage du rectangle, mais cette fois, en utilisant 4 couleurs disposées ainsi.

Nous remarquons alors que chaque couleur est représentée 35 fois. Or, en posant une pièce de taille 1×4 sur notre grand rectangle, il est facile de constater que cette pièce couvrira deux cases d’une couleur et deux cases d’une autre couleur… ce qui implique que le nombres de cases de la même couleur est forcément pair ! Ca ne colle pas, puzzle impossible, terminé.

Bon, les cas particuliers, c’est bien marrant, mais il serait sympathique de trouver une méthode générale pour ne pas devoir, à chaque fois, ressortir nos crayons de couleur et s’arranger pour trouver une situation qui ne nous convient pas… D’autant plus que cette méthode ne fonctionne que pour montrer qu’un puzzle est impossible, mais ne donne aucune piste pour déterminer les cas possibles !

Rassurez-vous, car un tel théorème existe bel et bien…

Le théorème

Énonçons d’abord ce résultat que nous devons à De Bruijn et Klarner.

Nous souhaitons remplir un grand rectangle de dimension L x M avec des pièces rectangulaires de taille a x b. Ce résultat est possible si et seulement si les trois conditions suivantes sont satisfaites :

  1. LM est un multiple de ab
  2. L et M peuvent tous les deux s’écrire comme une somme de a et de b – si vous n’avez pas encore trop de lettres, cela signifie qu’il existe quatre entiers positifs w, x, y et z tels que L = wa + xb et M = ya + zb… Bref…
  3. a et b ont tous les deux un multiple parmi L et M (éventuellement le même).

Rassurez-vous, nous allons expliquer tout cela, mais commençons par des cas particuliers :

Est-il possible de paver un rectangle de taille 9 x 14 en utilisant des pièces de taille 2 x 3 ?

  1. 9 x 14 = 126, qui est bien un multiple de 2 x 3 = 6 – en l’occurrence, 126 = 6  x 22
  2. 9 = 3 + 3 + 3 et 14 = 3 + 3 + 3 + 3 + 2. On a donc écrit 9 et 14 comme des sommes de 2 et de 3
  3. 14 est un multiple de 2, 9 est un multiple de 3

Les trois conditions sont vérifiées, pas de souci ! Le pavage est d’ailleurs très simple à obtenir, n’hésitez pas à le chercher !

Repassons alors au cas du rectangle 14 x 10 à remplir avec des pièces de taille 1 x 4 :

  1. 14 x 10 = 140 est bien un multiple de 1 x 4  =4
  2. 14 = 4 + 4 + 4 + 1 + 1 et 10 = 4 + 4 + 1 + 1, on a écrit 14 et 10 comme sommes de 4 et de 1
  3. En revanche, ni 14, ni 10 ne sont des multiples de 4 ! La condition 3 n’est pas vérifiée, il est impossible de réaliser un tel pavage.

Conditions nécessaires et suffisantes

L’énoncé de notre théorème comporte une formulation importante : « si et seulement si« . Cela signifie que les conditions évoquées sont à la fois nécessaires pour paver les rectangles, mais aussi que les vérifier suffit à affirmer que notre rectangle est pavable.

Montrons pour commencer qu’elles sont nécessaires, et nous allons donc supposer qu’un pavage du grand rectangle existe :

D’abord, il faut remplir le grand rectangle (composé de LM cases) avec un certain nombre de petits rectangles (qui ont chacun ab cases) : il faut donc bel et bien que le nombre de cases du plus grand rectangle soit un multiple du nombre de cases du petit rectangle.

Par ailleurs, puisque notre rectangle est pavé, nous pouvons regarder ce qu’il se passe sur un de ses bords : les petits rectangles y sont accolés, dans un sens ou dans l’autre. La longueur du bord se décompose donc selon les mesures de notre petit rectangle.

Si mon grand rectangle est pavé de petits rectangles de taille 2 x 3, alors chaque longueur du grand rectangle doit s’écrire comme somme de 2 et de 3

Pour la troisième propriété, nous allons diviser toutes nos longueurs par a, c’est-à-dire, la longueur d’un côté du petit rectangle. Nous avons donc pavé un rectangle de dimension L/a x M/a avec des pièces de taille 1 x b/a

Attention, fermez les yeux car nous allons admettre un théorème : si un rectangle est pavé avec d’autres rectangles ayant tous au moins une longueur entière, alors le rectangle ainsi obtenu a lui également une longueur entière. En l’occurrence, tous nos petits rectangles ont une longueur qui vaut 1, un entier. Du coup, le grand rectangle de taille L/a x M/a aussi : il y a au moins une grandeur parmi L/a et M/a qui est entière. En d’autres termes, a divise L ou a divise M. Et on utilise le même raisonnement avec b, bien entendu.

Voilà, nos trois conditions sont nécessaires, reste à montrer qu’elles sont suffisantes.

Notons alors deux cas de figure :

– soit a et b divisent deux nombres différents. Dans ce cas, le pavage est très simple à obtenir : voyez plutôt sur l’exemple suivant pour vous en convaincre.

– soit a et b divisent tous les deux le même nombre, disons L. Alors, d’après notre deuxième propriété, l’autre grandeur, M, peut s’écrire comme somme de a et de b. Autrement dit, il existe y et z, des entiers positifs, tels que M = ya + zb.

Prenons un exemple pour mieux nous représenter la suite : on souhaite paver un rectangle 22 x 20 avec des pièces  de taille 4 x 10. 4 et 10 divisent 20 mais pas 22.
Or, 22 = 4 + 4 + 4 + 10 = 3 x 4 + 1 x 10.

Nous allons donc diviser le côté de longueur 22 en 4 parties : 3 de longueurs 4 et 1 de longueur 10. A partir de là, il suffit de compléter avec nos rectangles en les posant dans le bon sens. Ce raisonnement pourra alors être copié pour n’importe quels petits et grands rectangles.

22 = 4 + 4 + 4 + 10, on subdivise donc le côté de longueur 22 en 3 parties de longueurs 4, 4, 4 et 10

Voilà notre preuve terminée !

Bon pavage !

Pour compléter

  • Jean-Paul Delahaye, Les plaisirs du rectangle,  Pour la Science Avril-Juin 2016
  • stan Wagon, Fourteen proofs of a result about tilling a rectangle, The American Mathematical Monthly, Vol 94, N°7, Août-Sept 1987, p 601-617
Cet article, publié dans Conjectures et théorèmes, Curiosités et récréation, est tagué , , , , , . Ajoutez ce permalien à vos favoris.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

w

Connexion à %s