Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 19-04-2011 00:26:20

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

gâteay 37

Heureusement , les problèmes de mon patissier brûlent largement toutes les calories des gâteaux dont il me gave smile

Je vous passe les derniers événement de sa famille ( et de la mienne ) . Bref depuis un moment il fait des gâteaux en double , à l'identique . Il découpe chacun des deux gâteaux en un même nombre de parts de même volume mais de formes quelconques et pourtant il arrive toujours à poser de la même façon une bougie sur chaque part .

http://img846.imageshack.us/img846/2769/memesbougies2.jpg

Pour résumer , deux gâteaux identiques sont découpés en "n" parts de même surface ( pas nécessairement de même forme ) , peut-on disposer de la même façon "n" bougies sur chaque gâteau , une bougie par part ? 

Amusez-vous bien smile

Vasimolo

PS : j'ai corrigé mon exemple car c'était un contre-exemple comme l'a fait remarquer Gasole smile

Indice : Spoiler : [Afficher le message] jeter un coup d’œil du côté du théorème ( ou lemme ) des mariages de Hall 



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 19-04-2011 07:25:34

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,472E+3

Gâteau 377

Non.

Déjà, avec deux parts, on peut toujours trouver une manière de garder les deux bougies sur la même part.

 #3 - 19-04-2011 09:48:07

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Gâeau 37

Ton exemple montre ce qu'il ne faut pas faire ? Mais bon, en décalant vers la droite les deux bougies d'en bas, on y arrive.

De tête, je dirais oui, question de nombres de parts et de surfaces égales : on doit pouvoir trouver une bijection f des parts de G1 (gâteau 1) vers celles de G2 telle que l'intersection de p1 avec f(p1) soit non-vide, il suffit alors de placer les bougies dans ces intersections.

Si cette bijection n'existait pas on aurait un problème de surface de parts, car une part de G1 ne peut couvrir deux parts de G2 et réciproquement.

 #4 - 19-04-2011 17:11:04

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

gâtzau 37

Oui Gasole , tout le problème est de justifier l'existence de cette bijection ou de trouver un exemple où elle n'existe pas smile

Vasimolo

 #5 - 19-04-2011 22:40:00

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

hâteau 37

Alors là je suis surpris, oui je sais ce ne serait pas la première fois avec les énigmes de Vasimolo où je tombe trop souvent dans le premier piège. Je suis surpris car j'allais dire que c'est toujours possible !

Prenons deux gâteaux découpés en n parts chacun, puis superposons les. Appelons A l'aire du gâteau et A/n l'aire d'une part. Alors quelque soit le nombre de part que l'on choisi (k entre 1 et n) ces k parts forment une aire de kA/n. Afin de recouvrir cette surface, il faut au minimum k parts de l'autre gâteau. Il y a donc toujours une correspondance de k parts du premier gâteau vers le second (donc une injection). La réciproque étant supportée par la même démonstration on a également une surjection ce qui nous donne la bijection d'un gâteau vers l'autre smile

Allez, j'attends de lire la démonstration inverse big_smile


The proof of the pudding is in the eating.

 #6 - 20-04-2011 14:08:03

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

gâteai 37

Soit [latex]P=\{p_1,...,p_n\}[/latex] l'ensemble des parts de [latex]G_1[/latex] et [latex]P'=\{p'_1,...,p'_n\}[/latex] l'ensemble des parts de [latex]G_2[/latex].

On dira que [latex]p_i[/latex] chevauche [latex]p'_j[/latex] si et seulement si leur intersection est non-vide.

Pour chaque [latex]p_i[/latex], soit [latex]f(p_i)[/latex] l'ensemble des [latex]p'_j[/latex] que [latex]p_i[/latex] chevauche.

Soit [latex]A[/latex] l'ensemble des couples : [latex]A=\{(p_i,p'_j)/ p'_j\in f(p_i)\} [/latex] (NB : [latex]f(p_i)[/latex] n'est jamais vide de même que [latex]f^{-1}(p'_j)[/latex], donc tous les [latex]p_i[/latex] apparaissent au moins une fois, de même que les [latex]p'_j[/latex]).

Alors le graphe [latex]G=(P,P';A)[/latex] est un graphe biparti. L'existence d'une bijection [latex]b[/latex] entre [latex]P[/latex] et [latex]P'[/latex] telle que [latex]p_i\cap b(p_i)\neq \emptyset[/latex], revient à l'existence d'un couplage parfait du graphe [latex]G[/latex].

Le théorème de Hall pour les graphes précise une condition nécessaire et suffisante pour l'existence de ce couplage parfait :

Théorème de Hall pour les graphes - Un graphe biparti [latex]G=(P,P';A)[/latex] admet un couplage parfait si et seulement si pour tout sous-ensemble [latex]X[/latex] de [latex]P[/latex] (de [latex]P'[/latex], respectivement), le nombre de sommets de [latex]P'[/latex] (de [latex]P[/latex], respectivement) adjacents à un sommet de [latex]X[/latex] est supérieur ou égal à la cardinalité de [latex]X[/latex].

On vérifie que notre graphe vérifie cette condition : c'est immédiat dans la mesure où [latex]k[/latex] parts de [latex]G_1[/latex] chevauchent nécessairement au moins [latex]k[/latex] parts de [latex]G_2[/latex] et réciproquement (sinon la surface couverte par les premières serait strictement supérieure à celle couverte par les secondes ce qui n'est évidemment pas possible vu qu'elles sont de surfaces égales).

 #7 - 20-04-2011 18:18:44

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Gâtaeu 37

Deux bonnes réponses smile

Franck : Je ne suis pas convaincu par la dernière phrase de ta démo smile
Gasole : Je te fais confiance pour la théorie , mon approche étais un peu plus "soft" smile

Je donnerai bientôt un indice pour les autres !

Vasimolo

 #8 - 21-04-2011 18:44:36

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

gâreau 37

@Vasimolo : j'avoue avoir eu la flemme de redémontrer ce théorème dans ce cas particulier (hou hou !) car je pressens que c'est à ça qu'une approche plus soft va revenir... mais qui sait ?

 #9 - 22-04-2011 00:51:03

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

gâtzau 37

J'ai ajouté un indice smile

Vasimolo

 #10 - 22-04-2011 01:34:55

irmo322
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 198

Gâteaau 37

Intéressant ce théorème de Hall (et ton énigme aussi évidemment).

Comme le découpage se fait en parts de même volume, on peut affirmer que chaque groupe de parts du 1er gâteau intersecte au moins autant de parts du 2ème.  Par le théorème de Hall, on peut donc associé à chaque part du 1er gâteau une part du 2ème gâteau qui l'intersecte. On pose alors les bougies sur ces intersections.

 #11 - 22-04-2011 18:33:22

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Gâteau 7

C'est ça Irmo smile

Vasimolo

 #12 - 29-04-2011 17:40:49

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Gâtea 37

Il s'agît d'une des multiples utilisations du théorème des mariages , à déguster sans modération .

http://books.google.fr/books?id=1L0Ydxj … mp;f=false

Je vous laisse lire la démo de Gazole ou celle d'Irmo ( un peu moins technique smile ) .

Merci pour la participation smile

Vasimolo

 #13 - 29-04-2011 19:52:28

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3319

Gâteua 37

Même si, je ne comprends pas toujours les réponses, c'est toujours avec plaisir que je lis les sujets de tes énigmes et les réponses des joueurs, parce que les énoncés sont toujours clairs et "simples" à comprendre.
Alors moi je dis merci et bravo pour toutes ces énigmes originales, et j'espère que ton pâtissier t'embêtera encore tongue

Shadock wink


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #14 - 29-04-2011 21:08:31

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4734

Gâtaeu 37

Merci Shadock ,

je crois aussi , à mon corps défendant et sûrement au grand dam de certains , qu'il ne me lâchera pas de sitôt ce bougre de pâtissier mad

Vasimolo

 #15 - 29-04-2011 21:23:57

kosmogol
Banni
Enigmes résolues : 49
Messages : 11,928E+3

Gâteu 37

Vasimolo a écrit:

Je vous laisse lire la démo de Gazole ou celle d'Irmo ( un peu moins technique smile ) .

Ce serait compréhensible si je connaissais le verbe intersecter qui m'a l'air d'être du jargon métier.


http://enigmusique.blogspot.com/

 #16 - 29-04-2011 21:36:49

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3319

gâyeau 37

Intersecter ne donne t-il point intersection en y réfléchissant un peu wink


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Riri, Fifi et ?

Sujets similaires

Sujet Date Forum
P2T
Gâteau 116 par Vasimolo
27-12-2015 Enigmes Mathématiques
P2T
Partage d'un gâteau par titoufred
29-04-2013 Enigmes Mathématiques
P2T
Gâteau 77 par Vasimolo
01-05-2014 Enigmes Mathématiques
P2T
Gâteau 82 par Vasimolo
24-10-2014 Enigmes Mathématiques
P2T
Gâteau 68 par Vasimolo
24-01-2014 Enigmes Mathématiques
P2T
Gâteau 17 par Vasimolo
28-07-2010 Enigmes Mathématiques
P2T
Gâteau 110 par Vasimolo
01-11-2015 Enigmes Mathématiques
P2T
Gâteau 98 par Vasimolo
07-05-2015 Enigmes Mathématiques
P2T
Gâteau 106 par Vasimolo
20-09-2015 Enigmes Mathématiques
P2T
Gâteau 123 par Vasimolo
24-07-2016 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete