Competition problem — Combinatorics

Library / /147 of 196

Combinatorics Difficulty 5.7 AIME, harder Prove it Soviet Union

Problem:

Form 10A has 29 students who are listed in order on its duty roster. Form 10B has 32 students who are listed in order on its duty roster. Every day two students are on duty, one from form 10A and one from form 10B. Each day just one of the students on duty changes and is replaced by the following student on the relevant roster (when the last student on a roster is replaced he is replaced by the first). On two particular days the same two students were on duty. Is it possible that starting on the first of these days and ending the day before the second, every pair of students (one from 10A and one from 10B) shared duty exactly once?

Solution

Solution:

Answer: no.

Suppose such an arrangement is possible. Suppose that it includes $m$ cycles through the form 10A roster and $n$ cycles through the 10B roster. Then the total number of changes is $29m + 32n = 29 \times 32$ (since each pair occurs once). But that means $29$ divides $n$ and $32$ divides $m$ . Both $m$ and $n$ are at least $1$ , so that means $n \geq 29$ and $m \geq 32$ , but then $29m + 32n > 29 \times 32$ . Contradiction.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.