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 - 02-01-2011 22:16:32

SaintPierre
Banni
Enigmes résolues : 42
Messages : 2063
Lieu: Annecy

un point, c'est toyt ?

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 ?



Annonces sponsorisées :

C'est à l'intelligence d'achever l'oeuvre de l'intuition.

#0 Pub

 #2 - 02-01-2011 22:19:38

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

Un point, c'est tut ?

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 point, c'est totu ?

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 point, c'est toout ?

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 wink

 

 #5 - 03-01-2011 09:21:40

Milou_le_viking
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 434

Un point, 'cest 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 poont, 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 point, c'estt 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 : 434

un point, c'est tiut ?

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 poibt, c'est 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 poiint, c'est tout ?

La réponse est 9. Ceux qui veulent le démontrer ont encore 2 jours. winkwinkwink


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 poitn, 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'zst tout ?

@gasole: je te vends mon Touran ?  big_smiletonguewink


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 point, c'estt 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 : 434

Un point, 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'esy 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 : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Un point, 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, 'cest tout ?

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 poit, c'est tout ?

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,466E+3

Unn point, 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'ets 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 piint, c'est tout ?

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

un point, c'esr tout ?

:(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? smile 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 point, c'est toutt ?

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, c'est toout ?

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

un point, c'est touy ?

gasole a écrit:

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

Ouai hmm c'est un peut capilotracté tout ça!! Sinon ce qu'il y a dans le spoiler n'aurai pas plus arrangé les choses, et sans commentaire tongue

A si c'est bon j'ai compris :

On aurai donc pu faire comme ça :

A ; B ; C ; D ; E ; F ; G
Il y a donc 7 possibilités de groupe de trois :

ABC soit : AB / BC / AC
BCD soit : BC / CD / BD
CDE soit : CD / DE / CE
DEF soit : DE / EF / DF
EFG soit : EF / FG / EG
FGA soit : FG / GA / FA
GAB soit : GA / AB / GB

On voit que sur les 21 couples de deux possibles, il y a 6 paires de deux fois les mêmes soit 12 et 21-12=9 big_smile

Merci Gasole wink
Shadock


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

Mots clés des moteurs de recherche

Mot clé (occurences)
Figures avec 7 points et 6 droites de 3 points alignes (4) — 9 points 10 lignes (4) — Nombre de segments relies par n points (2) — Les points a et b ne doivent pas etre alignes avec f et f doit etre alignes avec cde (2) — Enigme facile deux piece font 30 sous ma premiere n est pas un 5 sous (4) .. (2) — Comment faire un triangle de 220 degres (2) — Un graphe qui relie 9 points chacun par 3 arretes (2) — Combien de segments avec 10 points (1) — Chemin plus court entre 3 points non alignes (1) — 3 segment passant par 9 point (1) — Point non alignes nombre de segment (1) — Graphe (1) — 7 points quelconques (1) — Points relies ou non par un segment montrer qu il existe un point (1) — Relie des point av?c quatre segment (1) — Nombre de segments maximum pour une figure a 5 points (1) — Relier les point aligne (1) — Il ya combien de segments sur une figure qui a 6 point (1) — Combien de segment peut-ont trace avec 15 point de telle sorte quil ne sont jamais alignees (1) — Relier tout les points en 6 segments enigme (1) — Combien peut on faire de segment avec 9 points (1) — Combiek de segments relient quatres poinst non alignes (1) — Donner moi une figure d un seigment avec 6 point (1) — Enigme etoile triangle (1) — Triangle qui contient uniquement 4 points non alignes a l interieur (1) — Avec 4 ligne tout les points doivent etre relier (1) — Pour relier deux points entre eux il faut un segment pour relier trois points il faut 3 segments pour relier 4 points il faut 6 segments (1) — Combien j obtiens de segments avec 4 points ? (1) — 3 points relies deux a deux (1) — Combien de segment peut on faire passer par 3 points non alignee (1) — 6 segments de 3 points (1) — Dix points pour 5 groupes de 4 points alignes (1) — 6 points tous relies entre eux (1) — Enigme 4 segment pour 9 point (1) — Figures 6 points combien de segments (1) — Le tournoi de tennis (1) — 30 points non alignes combien y a til de segments? (1) — Enigme 30 sous (1) — Reponse au probleme 12 points 5 segments (1) — Enigme un est tout et tout est un (1) — Devinette qu on en commun un terrains de tenis (1) — Il ya combien de segments sur une figure qui a 6 point sans le compter (1) — 10 segment (1) — Nombre de segments dans 5 triangles (1) — Relier des points non alignes (1) — Avec 9 points former 10 ligne de 3 points (1) — Enigme des 9 points relies par 3 droites (1) — 12 point combien de segments (1) —

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