Le jeu des... petites croix...

[Ben314]

Un jeu trés...interessant...:

Sur une feuille on trace un certain nombre de croix à 4 "sommets" puis, à tour de rôle, chaque joueur trace une courbe reliant deux "sommets" distincts (mais pouvant être sur la même croix ou le même "trait") puis trace ou il veut sur la courbe un petit "trait" perpendiculaire matérialisant deux nouveaux "sommets" utilisables par la suite.
Chaque "sommet" n'est utilisable qu'une seule fois. Les courbes ne doivent pas se couper, sont d'épaisseur nulle et "trés régulières" (pas de sin(1/x) ou de courbes de Peano caché derrière tout ça).
Si à un moment donné un joueur ne peut pas jouer, il a perdu.

Questions :
1) Le jeu peut il durer indéfiniement ?
2) Vaut il mieux commencer (en fonction du nombre de croix) ?
3) Quelle stratégie doit on suivre ?

P.S. Le jeu est... "assez surprenant"... et la question interessante est surtout la 1)...

[Doraki]

Je suis légèrement déçu par le manque de suspense du jeu.

[Ben314]

Je suis légèrement déçu par le manque de suspense du jeu.

C'est... tout à fait ça... :mur:

[vincentroumezy]

Je dirais oui.

[Ben314]

Je dirais oui.

Peut tu préciser ta pensée... :doh:

[vincentroumezy]

Le jeu est infini.

[Anonyme]

Moi je pense que non : il suffit de démontrer que le nombre de sommets "utilisables" ne peut que diminuer au fur et a mesure du jeu. Mais je ne pense pas pouvoir faire une demo un peu rigoureuse ...

[nodjim]

Tiens, en 1ère lecture, j'aurais dit que le jeu est fini.
En seconde lecture aussi.
En troisième lecture aussi.
Etc..

[beagle]

Tiens, en 1ère lecture, j'aurais dit que le jeu est fini.
En seconde lecture aussi.
En troisième lecture aussi.
Etc..

Pas mal nodjim, mais as-tu fait des croix vertes?
Non, alors faut revérifier.

[nodjim]

Ce que je vois, c'est que dès qu'on a fait une boucle, ce qu'il y a à l'intérieur est condamné. Or tout tracé est amorce de boucle. Et on y arrive toujours à ces boucles. En revanche, je ne sais pas encore comment s'y prendre pour gagner...

[nodjim]

Ah si c'était des points à 4 sommets, pas de soucis, on pourrait faire de l'infini à partir d'une seule croix. Le problème est que les croix nouvelles sont coupées par la ligne qui les crées!

[nodjim]

Bon, je crois avoir trouvé, je le donne: 3+5k segments pour (k-1) croix initiales.

[Ben314]

Bon, je crois avoir trouvé, je le donne: 3+5k segments pour (k-1) croix initiales.

:king2: Parfait :king2:
Preuve ?

[nodjim]

Ben là (pas le ben de Ben314, le ben de l'embarras) je suis un peu hésitant encore...

[Doraki]

Je donne une interprétation combinatoire au jeu.

Quand on crée des boucles dans le jeu, ça sépare le terrain de jeu en plusieurs terrains plus petits qui ne peuvent plus jamais interagir entre eux.
A l'intérieur d'un terrain, on regroupe les sommets libres par leur composante connexe, et on obtient, dans chaque terrain, la liste des composantes connexes, et pour chaque composante connexe, le nombre de sommets qui s'y trouvent :

Au début on commence avec 1 terrain, n composantes à 4 sommets :
Je reprends l'exemple :
(4 4 4 4 4)

Il y a deux sortes de coups.
Ceux qui fusionnent deux composantes connexes, en gardant le même nombre de sommets.
-> (8 4 4 4)

Et ceux qui coupe le terrain en deux parties. Ce faisant, on doit découper une composante en deux, mettre un morceau dans chaque terrain, puis répartir ce qui reste parmi les 2 nouveaux terrains.

Sur l'exemple, on coupe avec la composante à 8 sommets :
-> (1 4) (7 4 4)

Et ainsi de suite :
-> (1 4) (11 4)
-> (1 4) (5 4) (6)
-> (1 4) (2 4) (3) (6)

Le jeu s'arrête quand on ne peut plus rien faire, c'est à dire quand le jeu est sous la forme
(1) (1) (1) (1) .... (1)

On voit facilement que le nombre N = nombre de composantes - 2 * nombre de terrains diminue de 1 à chaque coup,
il va de n-2 à -4n, donc le jeu a toujours 5n-2 coups.

Si n est pair, le joueur qui commence est forcé de perdre, si n est impair il est forcé de gagner.

[nodjim]

Bravo Doraki, vu comme ça c'est très clair.

[Ben314]

C'est exactement cela.
Si on connait "la formule d'Euler étendue" (avec sommets, façes, arêtes ET composantes connexes) on peut très légèrement simplifier la preuve en comptant plutôt les sommets et les arêtes, mais en fait, c'est exactement la même chose.