$2n$ knights around a table with namecards, is it possible that for every rotation there is exactly one person with a correct namecard?

Question

I need help with the following puzzle:

Consider a round table which hosts $2n$ knights. At each seat, there is a namecard of one knight. The knights don't necessarily sit in front of their own namecard. Prove that we can rotate the table such that at least 2 knights sit in front of their own nameplate.

Using the pigeon hole principle, it's quite easy to see that this is equivalent with:

• Proving that there exists a rotation where no knights sit in front of their own namecard.
• Proving that it is impossible that in every rotation, exactly one knight sits in front of his own namecard.

After going over some examples, I noted that if for knight number $k$, the angle needed to get this knight in front of his nameplate is $\frac{a_k \pi}{n}$, then the sum $a_1 + ... + a_{2n}$ is a multiple of n. If one could prove this, then this would solve the problem: if in every rotation, there is exactly one person sitting in front of his namecard, then $$a_1 + .. . + a_{2n} = 0+1+...+ (2n-1) = n(2n - 1),$$ which is not a multiple of $2n$.

Another method is also welcome of course. Thank you in advance!

Answer 1

Let $1,2,..,,2n$ be the numbers of the knights clockwise. Let $a_i$ be the number of places we have to rotate a table counter-clockwise so that $i$-th knight sits in front of his namecard.

If $a_i=a_j$ for some $i\neq j$ then we’re done. Otherwise $$\sum a_i = 0+1+2+…+(2n-1)=n\cdot(2n-1).$$

Note that $i+a_i$ or $i+a_i-2n$ is the number of place where the namecard of the $i$-th knight is. It means that for some integer $k$ holds $$\sum (i+a_i)=1+2+…+2n+(2n)\cdot k.$$

So $$\sum a_i=(2n)\cdot k=n\cdot(2k).$$

But $n\cdot(2n-1)= n\cdot(2k)$ never holds. Contradiction.

Answer 2

Another way to present the same argument (I solved it like this when I saw it).

---

Label the cards around the table in clockwise order as $0,1,2 \ldots 2n-1$ and name the knights with their respective numbers. Let $f: \Bbb Z/(2n)\Bbb Z \to \Bbb Z/(2n)\Bbb Z$ be such that $f(k)$ is the position (i.e., the name card at his current position) of knight $k$.

Define $g: \Bbb Z/(2n)\Bbb Z \to \Bbb Z/(2n)\Bbb Z$ as $g(k) = (f(k) - k) \text{ mod } 2n$. FTSOC assume that $g$ is injective (and hence, bijective).

Next, note that the orbit of $f(k)$ is a cycle of length $l_k$, where $1\le l_k \le 2n$. Then

$$f(0) - 0 = g(0)$$ $$f^2(0) - f(0) = g(f(0))$$ $$\cdot \\ \cdot \\ \cdot$$ $$f^{l_0}(0) - f^{l_0-1}(0) = g(f^{l_0-1}(0))$$ Since $g$ is injective, the values in the RHS's must be distinct. Sum this, and note the LHS telescopes to give $0$, so the RHS must be $0 \text{ mod } 2n$. Do this for all the cycles, to get $$\sum_{k=0}^{2n-1} k \equiv \sum_{k=0}^{2n-1} g(k) \equiv 0 \pmod{2n}$$ a contradiction.

---

The uselessly technical terminology aside, note that the orbits of $f$ will always have such properties; it is the injectivity of $g$ that allows us to achieve a contradiction, and as such, all other methods must boil down to the injectivity of $g$.