Track / Stage 6 / 19 of 400 #1019 of 2000

Problem 1019

National olympiad, first round

Combinatorics Difficulty 6.0 Prove it

4. (1)15 seats are equally arranged around a round table, and there are 15 guests' name cards on the table. The guests did not notice these name cards until they sat down and found that none of them was sitting in front of their own name card. Prove: The round table can be rotated so that at least two guests are sitting in front of their own name cards.
(2)Give an example of seating arrangement where exactly one of the 15 guests is sitting in front of their own name card, and rotating the table cannot make more guests sit in front of their own name cards.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

4. (1) Since no one is sitting in front of their own name card, for each guest, there is exactly one way to rotate the table so that they sit in front of their own name card. Since there are 15 guests, there are at most 14 effective rotations, so there must be at least one rotation that makes at least two guests sit in front of their own name cards.
（2）Number the guests from 1 to 15, and their name cards correspondingly. Arrange the name cards around the round table. The first possible scenario is to let guest $x$ face name card $16-x$ . Rotating $y$ seats, guest $x$ will face $16-x+y(\bmod 15)$ . When $x \equiv 16-x+y(\bmod 15)$ , i.e., when $2 x \equiv 16 + y(\bmod 15)$ , guest $x$ will face their own name card. Since this congruence equation has exactly one solution for each $y$ , no matter how the table is rotated, only one person will be seated correctly. The second possible scenario is to let guest $x$ face name card $2 x(\bmod 15)$ .

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