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 ?
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 ?
More Questions From This User See All
Lista de comentários
Verified answer
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
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.