Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#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

#2 01-12-2013 18:34:12

nerosson
Membre actif
Inscription : 21-03-2009
Messages : 1 658

Re : Petit problème de pavage

Salut à tous,

Une réponse bàclée à la va-vite, parce que c'est bientôt l' heure de la soupe

Si on oriente semblablement tous les dominos, un des côtés est forcément multiple de l'entier en question,

b) si on ne les oriente pas semblablement, alors on n'arrivera à faire un rectangle que si le côté pas entier est multiple ou sous-multiple du côté entier.

Vous pigez ? Vous avez du mérite ! La réponse est plus difficile à saisir que la question !

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

#4 02-12-2013 11:15:26

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : Petit problème de pavage

Salut,

idée

Mine de rien, la réponse bâclée de l’ancêtre me parait plutôt bien parti.
Si bien que je le cite :"Si on oriente semblablement tous les dominos, un des côtés est forcément multiple de l'entier en question"

Deuxième cas, les dominos ne sont pas tous orienté dans le même sens.
Je pense que l'on peut montrer que l'on peut paver un rectangle si et seulement si la largeur du domino est rationnelle.

Dernière modification par tibo (02-12-2013 11:16:01)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

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

#6 03-12-2013 18:42:42

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Petit problème de pavage

Bonsoir,

proposition

Si aucun coté de la surface pavée rectangulaire n'était entier, il y aurait au minimum un rectangle du pavage dont deux cotés adjacents auraient des longueurs qui ne seraient pas des entiers.

Mais je ne suis pas certain de savoir bien montrer la validité de cette proposition...

Hors ligne

#7 03-12-2013 20:28:38

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Petit problème de pavage

@totom

Bonjour,
j'ai l'impression qu'il s'agit plutôt d'une reformulation du problème.
Le problème demande : Tous les dominos ont un côté entier ==> Pavage a un côté entier
Votre formulation Non(Pavage a un côté entier) ==> Non(Tous les dominos ont un côté entier), ce qui est équivalent.


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

#8 04-12-2013 00:18:39

totomm
Membre
Inscription : 25-08-2011
Messages : 1 093

Re : Petit problème de pavage

Bonsoir,

une heureuse conclusion

Je cherchais une preuve "rapide" par l'absurde…
mais j'ai trouvé sur la toile :
Pusieurs méthodes, cliquer ici

Je ne serais pas arrivé à une bonne démonstration, même si celles existantes sont nombreuses.
Ma préférence va à la première présentée utilisant une méthode graphique.

Merci pour ce problème. A+ : totomm

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

#14 05-12-2013 13:50:44

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : Petit problème de pavage

Effectivement, je vois le problème.


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
quatre-vingt moins quatre-vingt un
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums