|
Pages: 1 2
Discussion fermée
#1 - 02-01-2011 22:16:32
- SaintPierre
- Banni
- Enigmes résolues : 42
- Messages : 2063
- Lieu: Annecy
Un poiint, c'est tout ?
On veut joindre 7 points (non alignés) d'un même plan par un nombre minimal de segments de telle sorte que pour trois points quelconques, deux au moins sont joints.
Combien de segments a une telle figure ?
C'est à l'intelligence d'achever l'oeuvre de l'intuition.
#2 - 02-01-2011 22:19:38
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,937E+3
Un opint, c'est tout ?
Facile , on aligne les 7 et 1 segment suffit .
Si ils ne sont pas alignés, c'est moins facile. Tes énigmes sont un niveau au dessus de mes capacités, je donne ma langue au chat.
#3 - 03-01-2011 00:05:22
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
un poont, c'est tout ?
Si la création d'un segment [AB] et d'un segment [BC] rend les points A et C joints, alors je dirai cinq, pour lier six points entre eux.
Sinon, je sèche pour l'instant...
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
#4 - 03-01-2011 03:23:08
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
Un poin, c'est tout ?
Vindiou... au moins une heure et demi pour résoudre le cas général avec une preuve pas trop pourrie :-) ... belle énigme vu sa concision.
Pour le cas n=7, on découvre plus ou moins vite qu'il faut 9 segments.
Pour le cas général, je suis passé par les graphes puisque ça n'est pas un problème de géométrie mais de pure combinatoire. Je suis preneur d'une preuve plus courte...
Disons que 3 points tels que deux soient reliés entre eux sont "copains". Soit [latex]G=(X,Y)[/latex] le graphe tel que : [latex]X[/latex] est l'ensemble des [latex]n[/latex] points, et [latex]U[/latex] est l'ensemble des arêtes les reliant : [TeX](x,y)\in U \Leftrightarrow[/latex] il y a un segment entre [latex]x[/latex] et [latex]y[/latex].
Un stable est un sous-ensemble de points non reliés deux à deux.
On s'aperçoit que pour toute partition en stables de [latex]G[/latex], chaque stable ne contient au plus que deux éléments (sinon il y aurait 3 points non copains), donc ne contient qu'un ou deux éléments.
Soit [latex]\Pi_{k,j}=(P_1,\ldots,P_k,Q_1,\ldots,Q_j)[/latex] une partition minimale de [latex]G[/latex] en [latex]k[/latex] stables de taille 2 et [latex]j[/latex] stables de taille 1 et je compte le nombre minimum d'arêtes nécessaire pour que G soit correct : - les deux éléments d'un [latex]P_i[/latex] doivent à eux deux relier ceux de [latex]P_{i'}[/latex] ([latex]i\neq i'[/latex]): deux arêtes pour chaque couple [latex]1\leq i<i'\leq k[/latex], soit un total de [latex] k.(k+1)[/latex] arêtes; - l'élément de chaque [latex]Q_i[/latex] doit être relié à celui de chaque [latex]Q_{i'}[/latex], sinon on pourrait les regrouper dans un même stable or [latex]\Pi[/latex] est minimale : soit [latex]j.(j-1)/2[/latex] arêtes; - enfin, l'élément de chaque [latex]Q_i[/latex] doit être relié à l'un des deux de chaque [latex]P_{i'}[/latex], sinon on a 3 "pas copains", soit [latex]k.j[/latex] arêtes.
En tenant compte du fait que [latex]2k+j=n[/latex], j'obtiens un total de : [latex]T(k)=n^2/2 + k^2 - nk - n/2[/latex] arêtes au minimum. Après dérivation par rapport à [latex]k[/latex], je constate que [latex]T(k)[/latex] est minimale pour [latex]k=n/2[/latex] dans les cas où [latex]n[/latex] est pair (et donc [latex]j=0[/latex]) ce qui s'étend facilement à [latex]k=(n-1)/2[/latex] et [latex]j=1[/latex] quand [latex]n[/latex] est impair.
Après un petit calcul je trouve : - si [latex]n[/latex] pair alors [latex]T(n)=(n^2-2n)/4[/TeX] - si [latex]n[/latex] impair alors [latex]T(n)=(n^2-2n+1)/4[/latex]
Pour 7 points je trouve : [latex]T(7)= (7^2-2*7+1)/4=9[/latex]
Ouf. Et merci je m'en resservirai
#5 - 03-01-2011 09:21:40
- Milou_le_viking
- Professionnel de Prise2Tete
- Enigmes résolues : 30
- Messages : 446
Un pooint, c'est tout ?
Il n'est pas précisé que les points sont des points quelconques du plan. Pour trouver le minimum, je dois donc choisir le cas particulier correspondant tout en respectant la seule contrainte selon laquelle les 7 points ne doivent pas être alignés.
Je prend donc 6 points alignés et un point quelconque non-aligné. Je trace un segment de droite reliant les 6 points alignés et ne relie pas le 7ème point. Ainsi, il y a toujours deux points joints parmi trois quelconques.
Réponse : un segment minimum
#6 - 03-01-2011 16:09:33
- SaintPierre
- Banni
- Enigmes résolues : 42
- Messages : 2063
- Lieu: Annecy
Un poit, c'est tout ?
Les points ne sont pas alignés...
C'est à l'intelligence d'achever l'oeuvre de l'intuition.
#7 - 03-01-2011 16:37:36
- Nicouj
- Professionnel de Prise2Tete
- Enigmes résolues : 27
- Messages : 330
Un pointt, c'est tout ?
Au plus 9. Je fais une clique de 3 points (3 segments) et une clique de 4 points (6 segments). Forcément tous sous ensemble de 3 points contient 2 points reliés.
#8 - 03-01-2011 16:44:27
- Milou_le_viking
- Professionnel de Prise2Tete
- Enigmes résolues : 30
- Messages : 446
un point, c'est toit ?
En effet, mes 7 points ne sont pas alignés.
Dois-je comprendre que trois points quelconques parmi les 7 doivent être non-alignés ?
Si c'est le cas, je propose rapidos la solution suivante:
Je laisse un point de coté et relie tous les autres. J'ai donc 5+4+3+2+1 liaisons. 15 segments de droites Y a peut-être moyen de faire mieux, mais là comme ça, j'en trouve pas.
Rectification: En ne mettant pas le septième de coté. Je fais un heptagone + 4 liaisons internes. 11 segments de droites
#9 - 03-01-2011 21:00:49
- Nnf13
- Habitué de Prise2Tete
- Enigmes résolues : 41
- Messages : 20
un point, c'zst tout ?
Bonsoir,
Ma figure est un pentagone avec une étoile à l'intérieur (qui correspond à 5 points tous reliés entre eux) et un segment de 2 points à côtés. Mais j'arrive pas à faire plus court !!
12 segments.
#10 - 03-01-2011 21:43:38
- SaintPierre
- Banni
- Enigmes résolues : 42
- Messages : 2063
- Lieu: Annecy
Un point, c'eest tout ?
C'est à l'intelligence d'achever l'oeuvre de l'intuition.
#11 - 03-01-2011 23:06:25
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
Un poin,t c'est tout ?
J'avais une autre piste que j'ai abandonnée : prouver par induction que le graphe optimal est [latex]G=K_p\cup K_q[/latex] (où [latex]K_i[/latex] désigne le graphe complet à [latex]i[/latex] sommets) avec [latex]p=\lfloor n/2 \rfloor[/latex] et [latex]q=\lceil n/2 \rceil[/latex]. Facile à vérifier pour [latex]n=3[/latex] mais l'induction... pas simple.
#12 - 03-01-2011 23:13:48
- SaintPierre
- Banni
- Enigmes résolues : 42
- Messages : 2063
- Lieu: Annecy
Un point, c'et tout ?
C'est à l'intelligence d'achever l'oeuvre de l'intuition.
#13 - 03-01-2011 23:24:36
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
un poibt, c'est tout ?
Merci mais j'ai déjà une Clio, muse de l'Histoire :-)
#14 - 04-01-2011 08:31:04
- Milou_le_viking
- Professionnel de Prise2Tete
- Enigmes résolues : 30
- Messages : 446
Un poinnt, c'est tout ?
Sans changer l'énoncé, la réponse est 1!
#15 - 04-01-2011 08:48:26
- Tromaril
- Habitué de Prise2Tete
- Enigmes résolues : 20
- Messages : 45
Un point,, c'est tout ?
Je dirais 9 (J'ai supposé que "deux au moins sont joints" sous entend qu'il y a un segment qui relie ces deux points)
* Il existe une solution à 9 segments. Pour la construire, on sépare les points en deux groupes : un groupe de trois points et un de quatre points et à l'intérieur de ces groupes on trace tous les segments possibles (autrement dit on crée les deux graphes complets K3 et K4)
* Toute solution a au moins 9 segments. Pour cela on 'appuie sur la propriété suivante : Si deux points i et j ne sont pas reliés entre eux alors chacun des autres points est relié à i ou à j. - Soit une solution au problème. Si toutes les paires de points sont reliées alors il y a 21 segments. Si une paire n'est pas reliée (on peut supposer qu'il s'agit des points 1 et 2) alors il y a au moins 5 segments partants de 1 ou 2. -Considérons maintenant les autres points (3 à 7) S'ils sont tous reliés entre eux alors il y a au moins 10 segments qui viennent s'ajouter aux 5 précédents. Si une paire n'est pas reliée (on peut supposer que c'est la paire 3,4) alors il y a au moins 5 segments qui partent de cette paire (dont deux qui vont vers 1 et 2). Il y a donc au moins 5+3 segments dans la solution. -On se restreint maintenant aux points 5, 6 et 7 S'ils sont tous reliés il y a au moins 8+3=11 segments. Si une paire n'est pas reliée (disons 5 et 6) cela ajoute au moins 1 segment à la solution (5 - 4 déjà comptés)
Il y a donc au moins 5 + 3 + 1 = 9 segments.
D'après ce que j'ai pu voir le raisonnement se généralise. S'il y a n=2k+1 points, il faut au moins [latex]k^2[/latex] segments. Je n'ai pas regardé pour un nombre pair de points.
#16 - 04-01-2011 13:32:24
- dhrm77
- L'exilé
- Enigmes résolues : 49
- Messages : 3004
- Lieu: Fanning Island-?-Lac Tele,Mali
Un opint, c'est tout ?
Je ne vois vraiment pas. Avec 9 segments je trouve toujours une seule combinaison de 3 points dont aucun n'est joint a un autre. Donc pour moi la solution est 10 segments.
Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt
#17 - 04-01-2011 14:10:37
- Tromaril
- Habitué de Prise2Tete
- Enigmes résolues : 20
- Messages : 45
un point, c'est yout ?
Après réflexion il y a une autre approche
Si on passe au problème dual, il faut trouver un graphe sans triangle ayant le maximum d'arêtes. Or d'après le théorème de Mantel, ce graphe a [latex]\lfloor n^2/4\rfloor[/latex] arêtes (merci wikipédia !!! http://en.wikipedia.org/wiki/Tur%C3%A1n's_theorem )
il faut donc au minimum [latex]1/2*n(n-1)-\lfloor n^2/4\rfloor[/latex] arêtes.
pour n=7, ça fait bien 21-12=9
#18 - 05-01-2011 01:01:24
- lelynxbelge
- Amateur de Prise2Tete
- Enigmes résolues : 26
- Messages : 2
Un point, c'est tou ?
il faut former un triangle et un carré (dont tout les point sont relier entre eux)
Par conséquent, si on prend comme premier point un point du triangle, on peut soi: -prendre 2 point du carré. Il seront relié, donc OK -prendre 1 point du carré et 1 du triangle, le point 1 sera relier a celui du triangle, donc OK -prendre 2 point du triangle, donc ok
On fait exactement le même raisonnement pour le carré !!!
Et ca marche
#19 - 05-01-2011 09:30:18
- gwen27
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 5,937E+3
un ooint, c'est tout ?
Un essai quand même :
4 points non alignés sont toujours reliés entre eux avec six segments ( côtés et diagonales d'un carré par exemple)
3 points les sont par trois segments ( triangle )
Donc en faisant un groupe de 4 points et un groupe de 3 points, ça marche. Seulement, de là à prouver qu'on ne peut pas faire mieux... je passe.
#20 - 05-01-2011 10:57:11
- Nicouj
- Professionnel de Prise2Tete
- Enigmes résolues : 27
- Messages : 330
Un point, c'et tout ?
Soit A un des points dont le nombre de liaison est minimum. Soit E l'ensemble des points non reliés à A. Pour satisfaire l'énoncé, soit E est vide soit tous les points de E sont connectés. - Si E est vide alors notre graphe est un graphe complet de 7 points et possède donc 7*6/2 = 21 arrêtes. - Sinon E possède au moins un élément B. Soit F l'ensemble des points non connectés à B. F contient au moins A. Donc l'ensemble des points de F doivent être connectés entre eux.
Soit n le cardinal de E et (7-n) le cardinal F. il y donc au moins n(n-1)/2+(7-n)(7-n-1)/2 segments qui atteint son minimum 9 pour n=3 ou n=4
En généralisant pour N points on a au moins n(n-1)/2+(N-n)(N-n-1)/2 segments. On trouve suivant le même procédé que le min est N'^2 pour N = 2N' et N'^2-N' pour N= 2N'+1
#21 - 06-01-2011 15:34:23
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
Un point, c'est tot ?
Bien vu Tromaril ! Je suis flatté de savoir que j'ai redémontré le théorème de Mantel quelque part... :-)
Et très jolie solution de Nicouj avec ton sommet de degré minimum et E et ton F, tu as trouvé ce qui me manquait dans ma première approche : prouver qu'il y a forcément exactement 2 composantes connexes.
#22 - 06-01-2011 21:23:55
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
un point, c'est tiut ?
:(Bon je n'irai pas par 4 chemins, je pas compris pourquoi la réponse est 9. PS : Je n'ai pas compris la dernière ligne de l'énoncé. Y a t-il quelqu'un qui puisse dans un moment de grâce m'expliquer? D'avance merci; Shadock
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
#23 - 06-01-2011 23:53:37
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
Un pointt, c'est tout ?
Shadock... Imagine qu'à la fin d'un tournoi de tennis de 7 joueurs, on te demande combien il y a eu de matchs au minimum pour que dans tout groupe de trois joueurs, au moins deux d'entre eux aient joué ensemble.
Spoiler : [Afficher le message] On peut expliquer ça avec une partouze si tu préfères :-)
#24 - 07-01-2011 11:52:44
- MthS-MlndN
- Hors d'u-Sage
- Enigmes résolues : 49
- Messages : 12,414E+3
- Lieu: Rouen
Un point, cc'est tout ?
Tromaril a écrit:Après réflexion il y a une autre approche
Si on passe au problème dual, il faut trouver un graphe sans triangle ayant le maximum d'arêtes. Or d'après le théorème de Mantel, ce graphe a [latex]\lfloor n^2/4\rfloor[/latex] arêtes (merci wikipédia !!! http://en.wikipedia.org/wiki/Tur%C3%A1n's_theorem )
il faut donc au minimum [latex]1/2*n(n-1)-\lfloor n^2/4\rfloor[/latex] arêtes.
pour n=7, ça fait bien 21-12=9
Ca, c'est ce que j'appelle une superbe solution. Mes félicitations, mon cher !
Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298
#25 - 07-01-2011 19:07:04
- shadock
- Elite de Prise2Tete
- Enigmes résolues : 39
- Messages : 3334
Un point,, c'est tout ?
"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
Discussion fermée
Pages: 1 2
Mots clés des moteurs de recherche
|
|