Track / Stage 6 / 114 of 400 #1114 of 1964

Problem 1114

National olympiad, first round

Combinatorics Difficulty 6.1 Prove it

King Louis was suspicious of some of his courtiers. He made a complete list of each of his courtiers and told each of them to spy on another courtier. The first on the list was to spy on the courtier who was spying on the second on the list, the second on the list was to spy on the courtier who was spying on the third on the list, and so on, the second-to-last was to spy on the courtier who was spying on the last, and the last was to spy on the courtier who was spying on the first. Verify that King Louis had an odd number of courtiers.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution

Let $n$ be the number of courtiers on the list and suppose that $n$ is even. Place them around a circular table so that each one is spying on their left neighbor.

Courtier 1 spies on courtier $X$ who spies on courtier 2, courtier 2 spies on courtier $Z$ who spies on courtier 3, and so on until courtier $\frac{n}{2}$ spies on courtier $Y$ who spies on courtier $\frac{n}{2}+1$ . Since the numbers $1,2,3, \ldots, n$ must alternate around the circle, we conclude that courtier $\frac{n}{2}+1$ is equal to courtier 1, that is, $n=0$ . This absurdity shows that $n$ is odd.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.