Salut à tous,
Cela fait un bon moment que je n'ai plus montré le bout de mon nez ici...

A première vue, j'ai choisi de former des quadrilatères pour éliminer 4 par 4 nos duellistes. Sur le cercle, on choisit 4 duellistes côte à côte, ils forment un quadrilatère, on trace les diagonales de ce quadrilatère et on désigne le point de croisement des diagonales. On procède comme cela jusqu'à avoir 4 ou moins de 4 duellistes restants sur le cercle. Dans ce cas, on finit en appliquant l'un des cas particuliers suivants:

Les 4 cas particuliers:

Cas 1 (1 seul duelliste sur le cercle) : o coup supplémentaire (rien d'autre à faire, c'est du bénèf!),

Cas 2 (2 duellistes sur le cercle) : 1 coup supplémentaire (désigner un point sur la droite portante de leur position en dehors du segment entre les 2),

Cas 3 (3 duellistes sur le cercle) : 1 coup supplémentaire (désigner un point sur un segment formé par 2 duellistes),

Cas 4 (4 duellistes sur le cercle) : 2 coups supplémentaires (désigner un point sur un segment formé par 2 duellistes => il reste 2 duellistes. Un autre coup en appliquant le cas 2)

Généralisation du nombre de coups:

Pour n duellistes, n peut s'écrire sous l'une des 4 formes suivantes (4*k, 4*k+1, 4*k+2 ou 4*k+3).

* si n s'écrit sous la forme de 4*k+1 alors on a k coups,
* si non, on a k+1 coups.

Voilà

Bonjour à tous,

N'arrivant pas à prouver la propriété que je sentais vraie, j'ai demandé à mon ami Google.

Une certain HERMANN HEINEKEN a démontré que dans un polygone régulier, pour un nombre impair de sommets, trois segments diagonaux ne peuvent être concourants. La démonstration n'est pas évidente et n'a sans doute pas sa place ici (de plus je ne l'ai trouvée qu'en allemand).

Il reste donc à grouper les sommets par 4 et à les tuer en choisissant l'intersection des diagonales du quadrilatère convexe qu'ils déterminent.

Quand le nombre de sommets est un multiple de 4 plus 1, la tuerie nécessite (n-1)/4 coups.

Quand le nombre de sommets est un multiple de 4 plus 3, la tuerie nécessite (n-3)/4+1 = (n+1)/4 coups puisqu'il reste alors un groupe de deux à tuer à la fin.

Je reviens puisque j'avais négligé le cas du nombre pair de sommets.

Dans ce cas, on pointe d'abord un sommet au hasard sur lequel tout le monde tire.

Lorsque celui-ci est tué, on pointe le centre de symétrie du polygone initial et toutes les paires de sommets opposés s'entre-tuent.

Seul reste le sommet dont l'opposé avait été tué au début.

Deux coups suffisent donc pour les cas pairs supérieurs à 2.

Dans le cas de 2 duellistes, la première étapes suffit : un coup donc.

looozer

Tu n'aurais pas inversé ta réponse ? Parce que je ne vois pas de possibilité de s'en sortir avec N pair vu qu'ils ne peuvent se tuer que 2 à 2... Et puis, je croyais que tu n'avais pas la réponse ?

EDIT pour le cas pair : Tu n'as pas dit que le point visé était dans le "cercle"

N=2 : 1 coup en visant dans le dos de l'un d'entre eux
N>2 : 2 coups , le premier en visant dans le dos d'un des tireurs, , le second en visant au centre.

@Gwen : je n'ai pas de réponse certaine pour le cas impair , disons que les réponses données coïncident, pour le moment, avec la mienne mais attendons ...
@Golgot : tu dois pouvoir faire bien mieux .

Vasimolo

Oui Gwen mais tu peux aussi rester dans le disque , ou plutôt sur le cercle

Vasimolo

Tu veux dire que sa religion lui interdit le suicide

Vasimolo

Ah, je n'avais pas compris qu'on cherchait à minimiser le nombre de rounds.
Je recherche alors...

oui looozer

Vasimolo

Si on désigne comme point un duelliste : où tire t'il ?
S'il tire sur lui même alors ça va, le cas pair peut se ramener en un round à un cas impair. Autrement, ce n'est pas possible d'avoir un seul survivant dans un cas pair : exactement deux duellistes étant toujours sur une unique droite, si l'un tire sur l'autre alors c'est que le point est sur cette droite, et donc qu'ils s'entretuent : on restera toujours sur un cas pair quel que soit le nombre de duellistes qui tombent sur ce round.

Par contre, la seule différence est que les joueurs ne se repositionnent pas a priori. Donc dans le cas pair, deux rounds suffisent : on pointe un duelliste au hasard, qui meurt, puis le centre du cercle. Tout le monde tombe sauf celui en face du premier point.

Dans le cas impair, on peut forcément s'en sortir en choisissant le vainqueur, puis en pointant au milieu des deux duellistes les plus éloignés. On s'en sort donc avec un total de (N-1)/2 rounds et un seul vainqueur. Mais on doit pouvoir faire mieux je pense. A voir

Edit: on peut faire en fait quasiment 2 fois moins.
On prend les quatre duellistes les plus éloignés, et on en forme un trapèze : les diagonales se coupent en un point qui sera désigné comme cible. Les duellistes tombent donc 4 par 4, et plus 2 par 2. Il faut donc (N-1)/4 rounds si N=4p+1; ou (N+1)/4 rounds si N=4p+3.
Je ne pense pas qu'on puisse faire encore mieux: les "polygones" formés par les duellistes sont irréguliers. Rien n'impose que leurs diagonales soient concourantes. Pour un trapèze, deux droites étant toujours parallèles ou concourantes, ça passe encore mais après ça n'est plus possible

@PRINCELEROI : Je n'ai rien compris
@Scarta : C'est ça . Si tu es gêné par le choix d'un tireur désigné comme cible , tu peux remarquer que deux points alignés avec la cible (distincte des deux points)  ne vont pas forcément s'entretuer .
@Godisdead : Oui , et nous en sommes tous là (las)

Vasimolo

Si on prend n points régulièrement disposés sur un cercle, alors deux cordes différentes ne passant pas par le centre se coupent (évidemment) en un point.
Je pourrais donc éliminer quatre tireurs par round.
Si, à la fin, il me reste 2, 3 ou 4 tireurs (donc si n n’est pas de la forme 4k+1),
il me faudra un round supplémentaire.
Si n = 4k+1, alors k rounds, et si n <> 4k+1, alors k+1 rounds.

Je suis par contre incapable de démontrer si plus de deux cordes peuvent être
(ou non) concourantes, ce qui est le vrai intérêt de cette énigme.
Je suis parti de n points de la forme Mk(cos(ak);sin(ak)) avec ak=2k.pi/n pour
n variant de 0 à n-1, ou si on veut n points d’affixe exp(i.2k.pi/n)
Mais je n’arrive pas à avancer.

Si une 20aine de pages en bon anglais ne vous font pas peur :
http://www-math.mit.edu/~poonen/papers/ngon.pdf