Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 01-12-2013 16:33:54
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Petit problème de pavage
Bonjour à tous,
Ci-dessous un petit problème que j'ai trouvé intéressant.
On vous donne des dominos dont un des côtés à une longueur qui est un entier naturel.
Montrer que si on arrive à paver une surface rectangulaire avec ces dominos, alors le rectangle obtenu possède un côté dont la longueur est un entier.
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#3 02-12-2013 10:50:53
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Petit problème de pavage
Bonjour,
Sans avoir eu le temps de réfléchir à ce problème, j'ai l'impression qu'on peur découper tous les rectangles de coté Entier en rectangles de coté UN afin de généraliser toute démonstration éventuelle...
A+
Hors ligne
#5 02-12-2013 20:11:36
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : Petit problème de pavage
@nerosson,tibo
J'avais suivi cette voie, je n'avais pas réussi à la mener jusqu'au bout. ça serait intéressant si vous arrivez à aboutir.
@totom
Tel que posé, le problème peut en effet se ramener à un côté de longueur 1. Un indice néanmoins, la propriété reste valable même si les dominos sont de dimensions différentes, dès lors que chaque domino a un côté entier.
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#9 04-12-2013 21:46:20
- Yassine
- Membre
- Inscription : 09-04-2013
- Messages : 1 090
Re : Petit problème de pavage
Je ne connaissais que deux solutions et on se retrouve avec 14 !
Ma préférence va également à la preuve géométrique même si la preuve analytique tient en deux lignes !
L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel
Hors ligne
#10 04-12-2013 23:16:23
- tibo
- Membre expert
- Inscription : 23-01-2008
- Messages : 1 097
Re : Petit problème de pavage
Re,
Dans la première preuve du lien donné par totomm (celle avec les graphe), il y a un truc qui m'échappe.
J'ai bien compris le principe ; si on a un chemin qui relie des coins du rectangle, alors l'un des cotés du rectangle est entier, et on voit bien que ça marche dans exemple. Mais je ne vois pas de preuve de l'existence d'un tel chemin dans le cas général.
Le chemin utilise donc toujours un nombre pair d’arêtes incidentes à u. Par conséquent, un chemin maximal (i.e. qu’on ne peut pas prolonger ni d’un côté, ni de l’autre) relie forcement des sommets de degré impair. Dans le cas présent, un chemin maximal relie deux sommets u et v placés aux coins du rectangles.
Comment sait-on qu'il existe ce chemin maximal? D'ailleurs si je prend u et v des coins à l'extrémité d'un coté non entier, ça ne marche pas.
Dernière modification par tibo (04-12-2013 23:16:52)
A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !
Hors ligne
#11 05-12-2013 10:18:48
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Petit problème de pavage
Bonjour,
Soit un graphe (non orienté). on décide de la parcourir "en ne passant qu'une seule fois par un arc" (on marque les arcs parcourus au fur et à mesure) :
En partant d'un sommet possédant un nombre impair d'arcs on aboutira forcément sur un sommet ayant un nombre impair d'arcs, sans pouvoir poursuivre.
C'est bien ce qui est dit car ce sont seuls les 4 sommets de la surface pavée qui ne possèdent qu'un seul arc : On va donc par un chemin entier d'un sommet à un autre. Le mot maximal n'est pas employé pour envisager "le chemin maximal du graphe".
Il est d'ailleurs immédiat de voir que la réciproque du théorème est fausse : il suffit de couper un rectangle dont un seul coté est entier pour en faire 2 ou plusieurs dont aucun coté n'est entier...
La solution algébrique ( la deuxième ) me parait plus discutable,
car il peut y avoir des déplacements internes qui globalement n'auront aucun effet sur le pourtour de la surface rectangulaire pavée
(c'est l'effet des plus ou moins c-a ) et dans ce cas de figure, rien n'est prouvé...
A+ : totomm
Hors ligne
#12 05-12-2013 11:53:08
- tibo
- Membre expert
- Inscription : 23-01-2008
- Messages : 1 097
Re : Petit problème de pavage
Re,
Certes j'avais mal lu. A part les coins tout les sommets sont de degré pair....
Pour la deuxième solution, je vois les choses comme ça :
Pour un pavé donné, soit deux cotés opposés ont été déplacé de [tex]\epsilon[/tex], et donc sa surface ne change pas ;
soit un seul de ses cotés a été déplacé de [tex]\epsilon[/tex], donc sa surface diminue de [tex]\lambda_i\epsilon[/tex] avec [tex]\lambda_i[/tex] qui dépend de la taille du pavé.
La surface du rectangle étant la somme des surface des pavés, la diminution de la surface du rectangle est de [tex](\sum\lambda_i)\epsilon[/tex]. Or si les deux cotés du rectangle bougeaient de [tex]\epsilon[/tex], la diminution serait de [tex](L+l)\epsilon-\epsilon^2[/tex]. Ces deux résultats ne peuvent être égals pour tout [tex]\epsilon[/tex] donc un seul coté bouge.
Dernière modification par tibo (05-12-2013 11:53:26)
A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !
Hors ligne
#13 05-12-2013 12:13:06
- totomm
- Membre
- Inscription : 25-08-2011
- Messages : 1 093
Re : Petit problème de pavage
ReBonjour,
Vous avez bien vu qu'il y a des plus et des moins dans les surfaces :
Soit un rectangle horizontal de hauteur 1 et de longueur 1,2 par exemple. Accolé à un rectangle de hauteur 1 et de longueur 1,8.
Si on bouge un peu le côté commun, la surface augmentée d'une part est diminuée de l'autre. Sans aucune incidence sur le tout.
C'est ce que je voulais dire : 'il peut y avoir des figures globales pour lesquelles la dynamique ne " prouve rien"
Et pour lesquelles il suffit de constater que les côtés du pavage ont déjà des longueurs entières.
Mais en en rediscutant, je ne dirais plus que la solution algébrique "paraît discutable". :-)
Hors ligne