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 : 4773

Gâtaeu 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,566E+3

Gâteauu 37

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âteau 337

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 : 4773

Gâteauu 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 : 1926
Lieu: UK

Gâetau 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âteau 3

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 : 4773

gâtrau 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âteau 3

@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 : 4773

hâteau 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âteau 3

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 : 4773

Gteau 37

C'est ça Irmo smile

Vasimolo

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

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

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 : 3327

gâtrau 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 : 4773

gâteay 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âteay 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 : 3327

Gâteauu 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 (numériquement) à la petite énigme suivante : 

Si il y a 88 pommes et que vous en prenez 44, combien vous en avez ?

Sujets similaires

Sujet Date Forum
P2T
Gâteau 122 par Vasimolo
21-07-2016 Enigmes Mathématiques
P2T
Gâteau 69 par Vasimolo
02-02-2014 Enigmes Mathématiques
P2T
Gâteau 59 par Vasimolo
05-05-2013 Enigmes Mathématiques
P2T
Gâteau 107 par Vasimolo
03-10-2015 Enigmes Mathématiques
P2T
Gâteau 82 par Vasimolo
24-10-2014 Enigmes Mathématiques
P2T
Gâteau 116 par Vasimolo
27-12-2015 Enigmes Mathématiques
P2T
Gâteau 2 par Vasimolo
09-04-2010 Enigmes Mathématiques
P2T
Gâteau 74 par Vasimolo
03-04-2014 Enigmes Mathématiques
P2T
Gâteau 51 par Vasimolo
28-12-2011 Enigmes Mathématiques
P2T
Gâteau 12 par Vasimolo
07-07-2010 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