J'ai une petite énigme pour vous.

On a n « duellistes » disposés régulièrement sur un cercle. Ce sont tous d'excellents tireurs et ne ratent jamais leur cible. Malheureusement ils sont aussi tous extrêmement bêtes : ils visent sans réfléchir le point qu'on leur désigne.

On leur montre un point : ils tirent simultanément dessus (on suppose que les balles se croisent sans encombre), on montre un nouveau point : les survivants tirent , ... . Par exemple, pour un nombre pair de combattants, en montrant le centre du cercle on fait disparaitre tout le monde en un seul coup. Pour trois duellistes, en montrant un point entre deux protagonistes, on récupère un seul rescapé .

Si on veut un seul survivant, quelle doit être la stratégie à adopter (en fonction de n) et combien faut-il prévoir de rounds ?

2

Réponses

2014-07-18T15:02:46+02:00
Il y a plusieurs cas :
1 seul duelliste : 0 coup à tirer

2 duellistes : 1 coup à tirer en désignant un point sur la droite reliant les duelliste mais situé dans le dos de l'un deux.

3 duellistes : 1 coup à tirer en désignant un point situé sur le segment entre 2 des 3 duellistes

A partir de 4 duellistes et pour tous les nombres pairs : 2 coups à tirer. Le premier en désignant un duelliste, le second en désignant le centre du cercle

Pour un nombre impair de duellistes > 3, c'est un peu plus compliqué :
On peut éliminer les duellistes 4 par 4 en désignant le point à l'intersection de 2 droites reliant  2 duellistes 2 à 2 et tous distincts.
A 5 duellistes, il faut donc 1 seul coup
A 7, il en faut 2, le premier tir ramenant au cas à 3 duellistes
A 9, il en faut 2, le premier tir ramenant au cas à 5 duellistes.
A 11, il en faut 3, le premier tir ramenant au cas à 7 duellistes
Donc si n=4*k+1 il faut k coups ou encore (n-1)/4
Et si n=4*k+3, il faut k+1 coups soit (n+1)/4
Pour les nombres impairs, les éliminer 2 à 2 n'est pas optimal (si l'on suppose qu'il s'agisse d'un problème d'optimisation), dans la mesure où on peut les éliminer 4 par 4.
C'est pou ça que j'ai corrigé tout à l'heure et donné une solution 4 par 4
Désolée je n'avais pas vu (la page n'était pas actualisée).
Pas de souci et je pense que tous les cas pairs se résolvent en 2 coups.
A part 2 bien sûr.
2014-07-18T15:29:26+02:00
Bonjour à toi.

En voilà un problème qui nécessite un peu de réflexion !
On va se servir du fait que 4 duellistes peuvent toujours s’entretuer (en tirant à l’intersection des diagonales du parallélogramme formé par les 4 duellistes) , et 2 duellistes peuvent eux aussi toujours s’entretuer.

Pour n impair, on aura deux cas : n=4k+1 ou n=4k+3.
Pour n=4k+1, on éliminera les duellistes en les faisant s’entretuer 4 par 4 jusqu’à ce qu’il ne reste plus qu’un duelliste, et on aura alors gagné.
Pour n=4k+3, on éliminera les duellistes en les faisant s’entretuer 4 par 4 jusqu’à ce qu’il ne reste plus que 3 duellistes, auquel cas on fera s’entretuer deux des trois duellistes restant, pour qu’il ne reste plus qu’un duelliste.
Pour n pair, il suffira de placer le point sur un duelliste, pour arriver à un nombre de duellistes n impair. Ce nombre atteint, on place le point au centre du cercle, tous les duellistes s'entretueront à l'exception d'un qui ne recevra pas de tirs et tirera dans le vide.

Concernant le nombre de coups :
Pour les nombres n impairs :
Pour n=4k+1, on aura un nombre de coups égal au quotient de la division de euclidienne de n par 4.
Pour n=4k+3, on aura un nombre de coups égal au quotient de la division de euclidienne de n par 4 auquel on ajoute 1 (la dernière étape ou les deux duellistes s’entretuent).
Pour les nombres pairs : 
On aura un nombre de coups égal à 2, le coup pour tuer un duelliste, et le coup pour les éliminer à l'exception d'un.

Exemple : 
Pour 7 : On élimine d’abord 4 duellistes, il en reste 3, on en élimine 2, on a donc gagné en deux coups.
Pour 13 : On élimine d’abord 4 duellistes, il en reste 9, on en élimine 4, il en reste 5, on en élimine 4, on a donc gagné en 3 coups.
Pour 8 : On en élimine 1, il en reste 7, on élimine 6 duellistes, on a donc gagné en deux coups.

En espérant avoir répondu, je suis désolée si il existe une solution plus simple. N’hésites pas à poser une question si tu ne comprends pas.

Cersei Lannister.
Et pour en revenir à l'optimisation , il me semble qu'il a été démontré qu'un polygone régulier ayant un nombre de sommets impairs ne peut avoir plus de 2 segments diagonaux concourants ce qui exclu une solution 6 par 6
C'est Jaime* :) Et je garde tout de même ma politesse.
Et oui j'ai tenté avec n=7, il n'y a pas de solution en 6 par 6, avec n=9 non plus, on peut donc abandonner l'idée.
Désolé si j'ai écorché son nom, ça doit être parce qu'il est antipathique au moins au début
Il n'est jamais antipathique, à mes yeux tout du moins. ;)