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 - 04-09-2009 21:10:14

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

les rouges zt les noirs

Un problème dont la solution est d'une simplicité étonnante big_smile

Dans un plan on dispose cent points rouges et cent points noirs de façons à ce que trois points de ces points ne soient jamais alignés . Est-il toujours possible de joindre deux à deux les points rouges avec les points noirs de manière à ce que les segments qui les relient ne se croisent jamais .

En effet on m'a toujours dit que c'était mal de croiser les flux lol

Un exemple avec quatre rouges et quatre noirs :

http://img405.imageshack.us/img405/1039/mikado.jpg

Bon courage hmm

Vasimolo

  • |
  • Répondre

#0 Pub

 #2 - 05-09-2009 10:33:58

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 964

Les rouges et les noirrs

Je me lance, bien conscient de ne pouvoir étonner que par la complexité yikes

S'il y a 1 rouge et 1 noir, l'unique segment existe trivialement big_smile
Je suppose donc le problème résolu jusqu'à un certain nombre n de paires de points.

Considérons (n+1) paires de points et traçons le frontière de l'enveloppe convexe* de l'ensemble.
Dans la majorité des cas, les points colorés de cette ligne ne sont pas tous rouges ni tous noirs. Cela me permet de trouver un segment rouge-noir que je trace. Comme il ne reste que n paires de points, toutes du même côté du segment déjà tracé, je sais terminer comme je l'affirme dans mon hypothèse de récurrence.

Reste le cas d'un pourtour 100% rouge ou 100% noir. Disons qu'il est rouge.
Je me positionne sur l'un des points rouges du pourtour et je fais pivoter une droite autour de ce point pour balayer l'enveloppe convexe dans le sens des aiguilles d'une montre. Au départ, les rouges sont majoritaires parmi les points rencontrés mais ils sont minoritaires à la fin. Comme le nombre de points noirs rencontrés n'augmente que de 1 en 1 (jamais 3 points alignés), j'ai forcément obtenu au moins une fois une droite D passant par un noir et partageant équitablement le reste. Je retiens donc le segment rouge-noir correspondant et je termine par mes deux petits groupes équitables, chacun comportant moins de n paires et donc pour lequel je sais faire.

J'espère que mon galimatias est quand même lisible et j'attends impatiemment la solution en deux lignes roll

*enveloppe convexe : Dans un plan, l'enveloppe convexe peut être comparée à la région limitée par un élastique qui englobe tous les points qu'on relâche jusqu'à ce qu'il se contracte au maximum. (dixit Wikipedia)


Celui qui fuit les casse-tête ne vaut pas un clou.

 #3 - 06-09-2009 13:21:29

EfCeBa
Administrateur
Enigmes résolues : ∞+1
Messages : 11×569

Les rouges et le noirs

Mon idée premiere est de passer en revue tous les couples de 2 points (rouge noir) et de tracer la droite associée.
Si, pour chaque section du plan engendrés par cette droite, il y a un nombre identique de points rouge et de points noirs alors repasser en revue les points dans la section et recommencer à l'infini.

Le but est de prouver qu'il existe toujours le cas ou je trouverais une droite.

Il me parait parfaitement possible que celà existe à coup sur mais je suis incapable de le prouver.

 #4 - 07-09-2009 23:18:17

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,382E+3

Les rougees et les noirs

Bonne et jolie réponse de scrablor big_smile

Il y a encore plus joli mais il faut vraiment y penser ( la solution n'est pas de moi ) . On relie deux à deux et au hasard les points rouges et noirs et on note S la somme des longueurs de tous ces segments . S'il n'y a pas de segments croisés , c'est fini et on a gagné . Sinon on prend au hasard deux segments croisés que l'on décroise comme sur l'illustration ci-dessous .
http://img137.imageshack.us/img137/3537/mikado2.jpg
Bien sûr cette opération peut générer de nouveaux croisements mais par l'inégalité triangulaire on diminue strictement S . Les points étant en nombre fini , S ne peut pas décroitre indéfiniment donc en renouvelant la manoeuvre un nombre de fois suffisant on n'arrive à une situation où on ne peut plus réduire S : il n'y a donc plus de segments croisés .

Amusant , non ?

Vasimolo

 #5 - 09-09-2009 09:50:04

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Les rouges et le noirs

waouh tres jolie solution !
Je file coller mes camarades ^^

 #6 - 06-10-2009 16:27:44

Enelya IV
Visiteur

kes rouges et les noirs

Vraiment très jolie...
Ca fait beaucoup de calcul, et il faudrait évité les redondances, mais c'est exactes !

 

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 : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
Balade sur un carré par McFlambi
28-06-2010 Enigmes Mathématiques
P2T
Polyomino puzzles par Clydevil
13-07-2012 Enigmes Mathématiques
27-03-2012 Enigmes Mathématiques
P2T
Numérobis 6 par Jackv
03-01-2013 Enigmes Mathématiques
P2T
Tableau maudit par carole085
18-08-2010 Enigmes Mathématiques
P2T
Les Mégaterrestres 10 par Promath-
18-07-2013 Enigmes Mathématiques
P2T
01-11-2011 Enigmes Mathématiques
P2T
Echecs 3 par Vasimolo
16-08-2010 Enigmes Mathématiques
02-03-2012 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