Apparemment la question sur un pavage de rectangles posée ici il y a quelques jours est stimulante. Après la solution par produit tensoriel, voici une autre qui repose sur une activité habituellement réservée aux enfants: le coloriage. (Les matheux ne sont que de grands enfants !) Merci à David Caisson qui m'a envoyé cette solution extraite du livre Solving Mathematical Problems de Terence Tao.

L'idée de T. Tao est aussi simple que belle: on colore en vert tous les rectangles ayant un côté horizontal entier, et en rouge tous les autres rectangles. Un argument topologique de connexité nous assure alors que dans le grand rectangle on peut relier les deux côtés verticaux par un chemin vert ou les deux côtés horizontaux par un chemin rouge. (Pour ceux qui ne connaissent pas encore la notion de connéxité : c'est une sorte de théorème des valeurs intermédiaires qui dit que deux lignes reliant les côtés opposés se coupent forcément). Or un chemin vert consiste en la juxtaposition de rectangles verts, donc sa longueur horizontale est entière; et de manière analogue pour un chemin rouge.

Vous pouvez lire la solution complète ici.

Cette "solution" m'a laissé perplexe car sur les trois premières pages l'auteur n'avance pas beaucoup, puis au tout dernier paragraphe il évoque, sans les traiter, quelques obstacles qui pourraient éventuellement se poser. Et avec un peu d'esprit critique on trouve que la démonstration est fausse! Voici un contre-exemple.

 

 
La largeur est 4 et la hauteur est 3,5. Pourtant il n'y a pas de chaîne verte mais seulement une chaîne rouge dont on ne peut rien déduire sur la hauteur (car elle possède des décalages) ni sur la largeur (car les rectangles rouges n'ont pas de largeurs entières).

Mais Terence Tao ne serait pas Terence Tao, porteur de la Médaille Fields 2006 (sorte de prix Nobel pour mathématiciens), si l'idée de sa preuve était entièrement fausse ! En effet, après une petite recherche sur internet, je me rends sur son blog personnel et j'y trouve une liste d'errata où il corrige, entre autres, cette preuve. Voici l'amélioration qu'il apporte:

On colore les rectangles comme avant, mais seulement leurs intérieurs. Ensuite on colore en vert les côtés verticaux ouverts, et le reste en rouge.

Maintenant mon contre-exemple ne résiste plus! On peut relier les deux côtés verticaux par un chemin vert.


 
Pourquoi cette démonstration améliorée fonctionne-elle ? Et bien, lorsqu'on parcourt un chemin vert disons, alors chaque fois qu'on quitte un rectangle vert pour passer dans un autre, ça se fait sur un segment vertical dont l'abscisse est un entier.

Voilà donc une jolie solution purement topologique, sans analyse. Je ne pense pas qu'elle s'adapte aux dimensions supérieures.

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 là.

L'exercice amusant sur les rectangles entiers possède apparemment beaucoup de solutions. François-Xavier Vialard m'a indiqué un article en anglais de Stan Wagon qui réunit les différentes démonstrations de 14 auteurs du monde entier ! L'une parmi elles, qui m'a été signalé aussi par Tahar Boulmezaoud, est particulièrement belle. En effet, elle utilise seulement des mathématiques élémentaires que même un élève de 6^e, voire de CM2, peut comprendre. L'idée de la preuve est de travailler avec un réseau en forme d'échiquier. Voici une description détaillé de cette démonstration, lisible par tous, indépendemment du niveau en maths :

Je rappelle que l'énoncé de l'exercice se trouve ici.

On considère un grand échiquier dont chaque case est de longueur 1/2. Nous allons l'utiliser pour poser nos rectangles dessus.

Lemme 1. Si un rectangle est entier alors il couvre autant de surface noire que blanche.

Preuve : Cela se verra plus facilement avec un dessin. Voici un rectangle dont le coté horizontal est 3.

On le découpe,

puis on déplace la partie gauche à droite, sans que cela ne change la superficie blanche ou noire couverte.

Il est maintenant évident que le rectangle couvre autant de superficie blanche que noire, ce qui achève la démonstration du lemme 1.

Remarque : La réciproque du lemme 1 n'est pas vraie. Comme contre-exemple il suffit de prendre un rectangle dont le milieu se trouve sur un point nœud de l'échiquier. Il couvre alors autant d'aire noire que blanche sans être pourtant nécessairement entier :

Mais si on rajoute une condition de plus les choses s'arrangent ! En effet, on a l'énoncé suivant.

Lemme 1. Si un rectangle dont au moins un sommet coïncide avec un point nœud de l'échiquier couvre autant de surface noire que blanche alors il est entier.

Preuve : Prenons le cas où le sommet en bas à gauche du rectangle coïncide avec un point nœud. Colorons ce nœud ainsi que les autres nœuds qui sont de coordonnées entières par rapport à lui. Nous supposons qu'aucun des autres trois sommets est sur un nœud coloré.

Pour examiner si le rectangle couvre autant de surface blanche que noire, nous le découpons ainsi :

Le rectangle bleu a un côté horizontal entier et couvre donc, d'après le lemme 1, autant de surface noire que blanche. De même pour le rectangle vert car son côté vertical est entier. Il reste alors à examiner le petit rectangle rouge.

Le petit rectangle jaune couvre autant d'aire blanche que noire, tandis que le marron couvre plus d'aire blanche que noire. Par conséquence le petit rectangle rouge couvre plus de surface noire que blanche.

Nous avons donc démontré qu'un rectangle dont un unique sommet coïncide avec un nœud coloré ne peut pas couvrir autant d'aire blanche que noire. Donc si un rectangle a au moins un sommet sur un nœud coloré et couvre la même aire blanche que noire alors il a forcément un deuxième sommet sur un nœud coloré, et cela implique qu'il s'agit d'un rectangle entier. Le lemme 2 est ainsi démontré.

Remarque : En réalité, il y a quatre types petits rectangles restants mais nous n'avons traité qu'un seul type car pour les trois autres on voit immédiatement que les aires blanches et noires ne sont pas les mêmes :

Maintenant nous sommes prêts à donner la preuve du problème posé.

Nous plaçons notre grand rectangle de manière qu'un de ses sommet est sur un point nœud de l'échiquier. Par hypothèse tous les petits rectangles le constituant sont entiers, donc chacun couvre, d'après le lemme 1, autant d'aire blanche et que noire. Il en est de même du grand rectangle. D'après le lemme 2 il est entier.

Dans les commentaires à la question sur un pavage de rectangles notre cher bloggeur PB disait d'avoir entendu de l'existence d'une solution qui utilise le produit tensoriel, mais malheureusement il ne la connaissait pas. D'abord ça m'intrigait — car où est le produit tensoriel dans tout ça? Or finalement un lien entre nos rectangles et cette structure algébrique est assez plausible; en effet, la loi de distributivité des tenseurs
 

devrait correspondre à la fusion de deux rectangles ayant le côté en commun.

Donc hier j'ai pris le temps d'y réfléchir pour retrouver cette fameuse solution! En fait elle est très simple, sans astuce, elle ne fait qu'utiliser la propriété de distributivité ci-dessus.

Notons (resp.) la largeur (resp. hauteur) du grand rectangle , et de même (resp. ) pour les petits rectangles , qui partitionnent . Alors on a

Pour prouver cette égalité il suffit de prolonger les côtés des petits rectangles comme indiqué sur la figure pour avoir une subdivision à laquelle on peut appliquer la propriété de distributivité:
 

 
Maintenant on regarde l'égalité (*) dans le produit tensoriel

c'est-à-dire on prend les longueurs modulo . D'après hypothèse on a donc et par conséquence ou . En autres mots, la largeur ou hauteur du grand rectangle est entière.

Update : Malheureusement cette preuve est erronée. Cherchez l'erreur... ou lisez mon commentaire no.13 ci-dessous.

Apparemment la question sur un pavage de rectangles posée ici il y a quelques jours est stimulante. Après la solution par produit tensoriel, voici une autre qui repose sur une activité habituellement réservée aux enfants: le coloriage. (Les matheux ne sont que de grands enfants !) Merci à David Caisson qui m'a envoyé cette solution extraite du livre Solving Mathematical Problems de Terence Tao.

L'idée de T. Tao est aussi simple que belle: on colore en vert tous les rectangles ayant un côté horizontal entier, et en rouge tous les autres rectangles. Un argument topologique de connexité nous assure alors que dans le grand rectangle on peut relier les deux côtés verticaux par un chemin vert ou les deux côtés horizontaux par un chemin rouge. (Pour ceux qui ne connaissent pas encore la notion de connéxité : c'est une sorte de théorème des valeurs intermédiaires qui dit que deux lignes reliant les côtés opposés se coupent forcément). Or un chemin vert consiste en la juxtaposition de rectangles verts, donc sa longueur horizontale est entière; et de manière analogue pour un chemin rouge.

Vous pouvez lire la solution complète ici.

Cette "solution" m'a laissé perplexe car sur les trois premières pages l'auteur n'avance pas beaucoup, puis au tout dernier paragraphe il évoque, sans les traiter, quelques obstacles qui pourraient éventuellement se poser. Et avec un peu d'esprit critique on trouve que la démonstration est fausse! Voici un contre-exemple.

 

 
La largeur est 4 et la hauteur est 3,5. Pourtant il n'y a pas de chaîne verte mais seulement une chaîne rouge dont on ne peut rien déduire sur la hauteur (car elle possède des décalages) ni sur la largeur (car les rectangles rouges n'ont pas de largeurs entières).

Mais Terence Tao ne serait pas Terence Tao, porteur de la Médaille Fields 2006 (sorte de prix Nobel pour mathématiciens), si l'idée de sa preuve était entièrement fausse ! En effet, après une petite recherche sur internet, je me rends sur son blog personnel et j'y trouve une liste d'errata où il corrige, entre autres, cette preuve. Voici l'amélioration qu'il apporte:

On colore les rectangles comme avant, mais seulement leurs intérieurs. Ensuite on colore en vert les côtés verticaux ouverts, et le reste en rouge.

Maintenant mon contre-exemple ne résiste plus! On peut relier les deux côtés verticaux par un chemin vert.


 
Pourquoi cette démonstration améliorée fonctionne-elle ? Et bien, lorsqu'on parcourt un chemin vert disons, alors chaque fois qu'on quitte un rectangle vert pour passer dans un autre, ça se fait sur un segment vertical dont l'abscisse est un entier.

Voilà donc une jolie solution purement topologique, sans analyse. Je ne pense pas qu'elle s'adapte aux dimensions supérieures.

Récemment en colle d'arithmétique j'ai posé la question suivante :

Soient x, y, z trois entiers vérifiant

Montrer qu’au moins un parmi eux est divisible par 3.

La solution que j'attendais de l'élève n'est pas compliquée (faire une preuve par l'absurde en étudiant l'équation modulo 9) mais depuis 1994 cette question classique semble devenue obsolète — enfin, je ne sais pas vraiment car je ne comprends pas la preuve du théorème de Wiles-Fermat... Qui peut donc m'éclaircir et me dire si la preuve de Wiles utilise ou non le résultat de cette innocente question de colle ?

Explication pour les non-matheux

Dans le 17ème siècle Pierre de Fermat écrivit sur la marge d'un livre que si n est un nombre entier strictement plus grand que 2 alors il n'existe pas de nombres entier non-nuls x, y, z vérifiant

.

Il ne donna pas de preuve et écrivit seulement J’ai trouvé une merveilleuse démonstration de cette proposition, mais la marge est trop étroite pour la contenir.
Pendant 300 ans les mathématiciens ont cherché une preuve de cette conjecture de Fermat, mais en vain. C'est seulement en 1994 qu'Andrew Wiles a réussi de la prouver ! Désormais la conjecture de Fermat est devenu le théorème de Fermat-Wiles. Sa preuve utilise des techniques très avancées. On est convaincu aujourd'hui que la preuve mentionnée par Fermat, celle qui était trop longue pour la marge, était eronnée.

Si on utilise le théorème de Fermat-Wiles la question de colle devient trivial. En effet, si trois entiers vérifient l'équation, alors au moins un parmi eux est nul et donc divisible par 3.

Pour revenir à l'histoire de ce théorème : à mon avis elle est typique à plusieurs titres pour la recherche en mathématiques :

• D'abord l'équation de Fermat est une généralisation d'une autre que tout le monde connaît, à savoir l'équation de Pythagore a²+b²=c². Il existe des entiers non-nuls qui la vérifient, par exemple 3²+4²=5² ; c'est-à-dire on peut construire un triangle rectangle de côtés entiers.
• L'énoncé du théorème de Fermat-Wiles est tellement simple que tout collégien peut le comprendre mais sa démonstration est tellement difficile que seulement quelques spécialistes la comprennent.
• L'énoncé n'a aucune application dans les sciences et ne possède, à ma connaissance, même pas de conséquences importantes en mathématiques. Son seul intérêt est sa beauté.
• Des générations de mathématiciens ont cherché à prouver cette conjecture. Ils l'ont fait pour l'honneur de l'esprit humain, sans penser à des applications, mais les outils mathématiques qu'ils ont développés ont fait avancer toute la science.
• Les ordinateurs ne peuvent jamais démontrer une telle conjecture car il faudrait tester l'équation sur une infinité de nombres ; ils peuvent seulement la rendre plausible.

Voilà, après une plutôt longue pause (exactement un mois) je suis de retour sur le blog et je commence doucement avec un petit exercice de géométrie plane ;-)

Soit D une droite dans le plan euclidien et n un entier positif. Montrer qu'il existe un point P₀ en dehors de la droite D et des points P₁,...,P_n sur D tels que la distance entre tous deux de ces n+1 points est un entier strictement positif.

Noël est le temps des casse-noisettes, non des casse-têtes pour mes amis les matheux. Voici une égalité :

Le but est de démontrer qu'elle est vraie pour tout entier n strictement positif. Comme d'habitude en maths c'est la dévise short is beautiful, c'est-à-dire il faut trouver une solution courte et élégante, sans avoir beaucoup de calcul à faire. On pourra s'inspirer de l'image d'un père noël ayant des cadeaux à distribuer dans des chaussettes...

Je collectionne constamment des exercices de maths intéressants et accéssibles aux élèves niveau prépa ou licence. On en trouve beaucoup dans les livres, sur internet, sur les vieilles feuilles d'exercices de ses propres professeurs... et quelques fois en invente soi-même ! Voici une question intéressante qui m'est venue le week-end dernier. La solution que j'ai trouvée ne nécessite pas de grand théorème, il faut seulement bien maîtriser ses connaissances élémentaires en algèbre linéaire :

Quel est le plus grand entier k tel que tout sous-espace affine de codimension k dans l'espace des matrices n x n contient une matrice inversible ?

Rappel : la codimension d'un sous-espace est la différence entre la dimension de l'espace ambiant et la dimension du sous-espace. Autrement dit, c'est le nombre d'équations nécessaires pour décrire le sous-espace (car chaque équation enlève un degré de liberté). Par exemple, dans l'espace habituel à trois dimensions la codimension d'une droite est 2, celle d'un plan est 1.

Tout étudiant apprend les formules

Soit p un entier positif. Montrer que, plus généralement, la somme des premiers n termes de la suite avec est un polynôme rationnel en n de degré p+1.

Dans ce qui suit tous les nombres sont des nombres naturels :  0, 1, 2, 3, 4, ...

Définition.  Les multiples d'un nombre n sont les nombres 0, n, 2n, 3n, 4n, ...

Exemples :

• Les multiples de 2 sont 0, 2, 4, 6, 8, ...
• Les multiples de 3 sont 0, 3, 6, 9, 12, ...
• Les multiples de 4 sont 0, 4, 8, 12, 16, ...

On appelle les multiples de 2 aussi nombres pairs. Les non-multiples de 2 sont 1, 3, 5, 7, ... et sont appelés nombres impairs.

Notre définition donne les multiples en forme d'une liste. Mais qu'est-ce qui signifient vraiment les trois petits points dans la liste 0, n, 2n, 3n, 4n, ... ? En fait, on peut écrire les trois points car tout le monde comprend comment on doit continuer la liste : après 4n, il y a 5n, puis 6n, et de suite. Autrement dit, on a la règle suivante.

Règle 1.  Un nombre m est un multiple de n si et seulement s'il existe un k tel que m = kn.

Par exemple, le nombre m=24 est multiple du nombre n=4 car 24=k×4 avec k=6.

Il est important que ce k soit aussi un nombre naturel, comme m et n. En effet, on n'a pas le droit de dire la phrase suivante : Le nombre 3 est multiple 4 car 3=k×4 avec k=¾.

Règle 2.  Zéro est multiple de tout nombre. Tout nombre est multiple de soi-même.

Preuve : Soit n un nombre choisi. Le nombre 0 est le premier élément de la liste de multiples de n — on l'obtient en prenant k=0. Et n est le deuxième élément dans cette liste — on l'obtient en prenant k=1.

Cas particuliers :

• Les multiples de 1 sont 0, 1, 2, 3, 4, ..., c'est-à-dire, tout nombre est multiple de 1.
• Les multiples de 0 sont 0, 0, 0, 0, 0, ..., c'est-à-dire, zéro n'a que lui-même comme multiple.

Dans les exemples on voit que la liste des multiples de 4, à savoir 0, 4, 8, 12, ..., est contenue dans la liste des multiples de 2. Si on y réfléchit un peu ce n'est pas très étonnant et nous allons le formuler comme une règle général :

Règle 3.  Si m est multiple de n et si n est multiple de p alors m est aussi multiple de p.

Preuve :  Si m est multiple de n on peut l'écrire comme m = kn ;  et si n est multiple de p on peut l'écrire comme n = k'p. Alors on a m = kn = kk'p ce qui prouve que m est multiple de p.

Exemples :

• 6 est multiple de 3, donc tout multiple de 6 est aussi multiple de 3.
  La réciproque n'est pas vraie, par exemple, 9 est multiple de 3 mais pas de 6.
• Tout multiple de 12 est aussi un multiple de 3 et de 4 et de 2.
  C'est vrai car 12 est multiple de 3 et de 4 et de 2.

Beaucoup d'affirmations que nous disons dans notre langage de tous les jours, dépendent de notre point de vu. Par exemple, les deux phrases

Zoé est la fille d'Alexandre  et  Alexandre est le père de Zoé

signifient la même chose, mais de points de vue différents. C'est cette diversité qui donne de la richesse à notre langue ! En mathématiques aussi il y a des manières différentes pour exprimer une même chose ; c'est utile, pas pour une question de style, mais car en maths le changement du point de vue est souvent un outil très puissant (voir un exemple dans cet article).

Définition.  Si m est un multiple de n on dit aussi que m est divisible par n ou que n divise m ou que n est un diviseur de m.

Autrement dit, n divise m si et seulement s'il existe k entier tel que m = kn.
L'équation m = kn équivaut à k = m/n. Ainsi n divise m si et seulement si la fraction m/n est un entier (si n est non-nul).

Notation.  Pour dire n divise m on écrit souvent n | m.

Exemples

• 5 | 15.
  On dit 5 divise 15 ou 5 est un diviseur de 15 ou 15 est divisible par 5 ou 15 est un multiple de 5.
• 3 | 15.

Les affirmations suivantes se déduisent directement de ce que nous avons déjà compris sur les multiples.

• Tout nombre divise 0 car 0 est multiple de tout nombre.
  En écriture mathématique, n|0 car 0 = 0 × n.
• Tout nombre divise soi-même car tout nombre est multiple de soi-même.
  Ou encore, n|n car n = 1 × n.
• 1 divise tout nombre car tout nombre est multiple de 1.
  Ou encore, 1|n car n = n × 1.

Règle 4.  Si p|n et si n|m alors p|m. Par exemple, 15|30 et 30|3000 donc 15|3000.

Preuve :  C'est une traduction directe de la règle 3.

Question :  Qu'est-ce qui est plus grand, multiple ou diviseur ?

Réponse :  Mise à part le multiple 0, les multiples d'un nombre sont plus grands que ses diviseurs.
Par exemple, les multiples non-nuls de 12 sont 12, 24, 36, .... Les diviseurs de 12 sont 1, 2, 3, 4, 6, 12.

Question :  Qui sont plus nombreux, les multiples d'un nombre donné ou ses diviseurs ?

Réponse :  Un nombre non-nul possède une infinité des multiples mais seulement un nombre fini de diviseurs.
En effet, pour n non-nul, la liste des multiples de n est 0, n, 2n, 3n, ... C'est une liste infinie avec des nombres de plus en plus grands. En revanche, le plus grand diviseur de n est n lui-même, donc n possède un nombre fini de diviseurs qui se trouvent parmi les nombres 1, 2, 3, ..., n.

Trouver tous les diviseurs d'un nombre donnée n'est pas facile si ce nombre est grand. Donc il est pratique de disposer de quelques critères de divisibiltés. Ca sera l'objet du prochain billet. Finissons ce billet avec un énoncé simple et sa preuve. Ca sera l'occasion de voir le formalisme des multiples en action.

Théorème.  Un nombre entier est pair si et seulement si son carré est pair.

Preuve du théorème.  Fixons un nombre entier n au hasard et prouvons le théorème pour ce nombre. (Le mathématicien dit pour cela soit n un entier.) Alors il y a deux cas possibles : soit n est pair, soit n est impair.
Supposons d'abord que n est pair. Alors il existe un entier k tel que n=2k. Ainsi n²=4k² ce qui prouve que n² est un multiple de 4, et donc en particulier un nombre pair. On vient de prouver que si un nombre est pair alors son carré aussi.
Supposons maintenant que n est impair. Alors il existe un entier k tel que n=2k+1. Donc n²=(2k+1)²=4k²+4k+1, et comme les deux premiers termes de cette somme sont pairs on en déduit que n² est impair. On vient de prouver que si un nombre est impair alors son carré aussi.
Or un nombre entier est soit pair soit impair ; donc en fait on a prouvé lé théorème.

Remarque.  Le théorème peut aussi s'énoncer comme suit : un entier est impair si et seulement si son carré est impair.

Exercices.  Les quatre exercices suivants sont faciles. Il faut simplement imiter la démonstration du théorème.

1. Montrer qu'un entier est multiple de 3 si et seulement si son carré l'est.
2. Montrer qu'un entier est pair si et seulement si son cube l'est.
3. Est-il vrai qu'un entier est multiple de 4 si et seulement si son carré l'est ?
4. Est-il vrai qu'un entier est multiple de 3 si et seulement si son cube l'est ?

Voilà un beau petit problème de colle : quels sont les groupes possédant un automorphisme non-trivial ?

Il y a une solution élégante, pas très longue...