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-11-2011 17:52:59

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1106
Lieu: Jacou

les abti-segments

La question (de cours?) assez classique: 22 régions avec 6 droites m'a fait repenser à cette variante amusante posée lors de la finale du 25ème championnat de la FFJM cet année à Paris:

Un anti-segment AB est la partie de la droite (AB) qui se trouve
à l'extérieur d’un segment [AB] de longueur non nulle. (Un
anti-segment est donc composé de deux demi-droites "alignées".)
Si on trace 3 anti-segments dans un plan on peut le
partager en au maximum 4 régions.
En combien de régions au maximum peut-on partager un
plan avec 2011 anti-segments ?

Ca me permet de contribuer aussi aux énigmes.
Bon amusement.


 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 03-11-2011 11:23:14

nicolas647
Passionné de Prise2Tete
Enigmes résolues : 24
Messages : 96

Les anti-segmets

Considérons d'abord le cas avec des droites.
Pour n droites, on sait déjà que le maximum de régions est [latex]\dfrac{n(n+1)}2+1[/latex]

Maintenant on va essayer de passer de droites à anti-segments en minimisant la perte de régions :
chaque passage provoque un trou qui va dans le meilleur des cas fusionner 2 régions en une seule. Ce meilleur des cas est très facile à obtenir, il suffit de mettre le segment entre 2 intersections.

Le maximum de régions pour n anti-segments est donc :
[TeX]\dfrac{n(n+1)}2+1-n=\dfrac{n(n-1)}2+1[/TeX]
Le résultat pour n=2011 est de :
[latex]\dfrac{2011(2011-1)}2+1=2021056[/latex] yikes

Un peu moins impressionnante est la réponse à la question inverse : combien faut-il au d'anti-segments au minimum pour obtenir 2011 régions ?
Spoiler : [Afficher le message] La réponse est de 64.

 #3 - 04-11-2011 04:19:16

FRiZMOUT
Verbicruciste binairien
Enigmes résolues : 49
Messages : 2218

lzs anti-segments

On remarque que lorsqu'on ajoute un anti-segment, cela crée au maximum autant de régions qu'il y a déjà d'anti-segments.

Soit [latex]R(n)[/latex] le nombre maximal de région avec [latex]n[/latex] anti-segments.

On a [latex]R(0) = R(1) = 1[/latex], donc [latex]R(n) = 1 + \sum_{k=0}^{n-1} k[/latex].

Ce qui équivaut à : [latex]R(n) = \frac{1}{2} (n-1) n+1[/latex].

Donc : [latex]R(2011) = \frac{1}{2}\time 2010 \time 2011 +1 = 2021056[/latex].

 #4 - 04-11-2011 08:38:22

Klimrod
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 4050
Lieu: hébesphénorotonde triangulaire

les abti-segments

Bonjour,

Si les anti-segments se coupent tous dans leur partie évidée, alors il n'y a qu'une seule région. C'est clairement le minimum.

Le maximum est atteint lorsque les parties évidées de chaque anti-segment se trouvent en dehors des points d'intersection. Dans cette configuration, si l'on compare avec le problème des N segments, alors chaque anti-segment enlève une région.

Pour N anti-segments la réponse est donc [ N(N+1)/2 + 1 ] - N
Soit N(N-1)/2 + 1

Application avec N=2011 : résultat = 2 021 056

Klim.


J'ai tant besoin de temps pour buller qu'il n'en reste plus assez pour bosser. Qui vit sans folie n'est pas si sage qu'il croit.

 #5 - 04-11-2011 15:48:07

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Les anti-segmentts

2 021 056.

Je n'arrive pas à le démontrer, mais en passant de n à n+1 "anti-segments", on peut créer n zones supplémentaires. La forme générale est donc : [latex]\frac{n(n-1)}{2}+1[/latex] zones pour n segments.


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #6 - 05-11-2011 08:53:38

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3802

Les anti-segents

Je dirais n(n-1)/2 +1 secteurs avec n anti segments.
C'est simplement la même formule que pour les droites à laquelle on ôte n. Car quand on transforme une droite en un antisegment, on supprime un secteur, à la condition que le segment ne soit pas à l'intersection de 2 droites.

 #7 - 07-11-2011 12:02:46

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1106
Lieu: Jacou

Les ant-isegments

Bonjour à tous.

Désolé pour le retard à revenir sur ce sujet. WE compliqué oblige.
5 bonnes réponses et 2 méthodes: la directe (FRiZMOUT et Mathias) et l'inverse (les autres).

Pour ma part, j'ai aussi utilisé la méthode inverse c'est-à-dire en partant du problèmes des N droites et en montrant que, bien choisi, chaque anti-segment n'enlève pas plus d'une seule zone.

Peu de participation pour cette énigme sans que je sache bien pourquoi...
Merci de votre participation.

 

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 : 

Dans une course, vous doublez le 42ème, en quelle position êtes-vous ?

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