Let $n$ be a positive integer. There are $n$ soldiers stationed on the $n$th root of unity in the complex plane. Each round, you pick a point, and all the soldiers shoot in a straight line towards that point; if their shot hits another soldier, the hit soldier dies and no longer shoots during the next round. What is the minimum number of rounds, in terms of $n$, required to eliminate all the soldiers? David Yang.
Problem
Source: ELMO Shortlist 2011, A1
Tags: algebra proposed, algebra
27.07.2012 18:49
This is a pretty silly problem.
This is a pretty silly problem... I thought we killed it from the shortlist?
30.07.2012 19:58
I'm not sure I agree with the "a shoots b" implies "b shoots a" bit. For example, when $n = 3$ pick the point $-1/2 + i$; only the guy on $-1/2 + i\sqrt{3}/2$ gets hit.
30.07.2012 22:42
MellowMelon wrote: I'm not sure I agree with the "a shoots b" implies "b shoots a" bit. For example, when $n = 3$ pick the point $-1/2 + i$; only the guy on $-1/2 + i\sqrt{3}/2$ gets hit. Indeed! Anyway, what happens if you pick the point to be the root of unity itself? Where does that guy shoot?
31.07.2012 03:06
Let's just take it's an illegal operation. Sketch for odd: Prove that no three chords intersect at the same point (maybe; if this fails then this proof fails) The above implies that at most four soldiers are killed each shot You cannot kill only three soldiers Hence the bound is established; proving it's achievable is pretty easy
31.07.2012 04:45
chaotic_iak wrote: Prove that no three chords intersect at the same point (maybe; if this fails then this proof fails) This appears to be true -- a lot of papers online on the subject of concurrent diagonals refer to a "delightful" proof in Heineken's "Regelmässige Vielecke und ihre Diagonalen" (1962) which I am having trouble finding a copy of (though pdf's of Regelmässige Vielecke und ihre Diagonalen II, published in 1968, abound).
31.07.2012 06:18
MellowMelon wrote: I'm not sure I agree with the "a shoots b" implies "b shoots a" bit. For example, when $n = 3$ pick the point $-1/2 + i$; only the guy on $-1/2 + i\sqrt{3}/2$ gets hit. David's intention was for the point to be inside the polygon, but this is a more interesting interpretation with roots in complex bashing and algebraic number theory. (And now I am very sad we did not put this on the ELMO in 2011, all because the ELMO committee sucks at English.) Mewto55555 wrote: chaotic_iak wrote: Prove that no three chords intersect at the same point (maybe; if this fails then this proof fails) This appears to be true -- a lot of papers online on the subject of concurrent diagonals refer to a "delightful" proof in Heineken's "Regelmässige Vielecke und ihre Diagonalen" (1962) which I am having trouble finding a copy of (though pdf's of Regelmässige Vielecke und ihre Diagonalen II, published in 1968, abound). Yes, and this is why surveys are extremely helpful. (See section 2 on "Primitive relations between roots of unity".)
31.07.2012 06:50
math154 wrote: MellowMelon wrote: I'm not sure I agree with the "a shoots b" implies "b shoots a" bit. For example, when $n = 3$ pick the point $-1/2 + i$; only the guy on $-1/2 + i\sqrt{3}/2$ gets hit. David's intention was for the point to be inside the polygon, but this is a more interesting interpretation with roots in complex bashing and algebraic number theory. (And now I am very sad we did not put this on the ELMO in 2011, all because the ELMO committee sucks at English.) If the point is inside the polygon, then would the reflexiveness be in place? Because, if you shoot somebody, the point you were aiming at would be between the two of you, and therefore the other person would shoot you.
31.07.2012 11:45
Err the intention for the points to be inside the polygon simplifies everything substantially; that explains why it's A1. If points can be outside the polygon, I'd put it as C3 of IMO. Yeah, reflexiveness will take place.
03.04.2019 16:05
Well it doesn't say that three chords never concurrent. It just proves they don't concur at a point inside the polygon. (At least the paper I found says so, but I assume that using complex numbers there is not really a difference.)