Maths Olympiad Prep

Library / /105 of 397

Algebra Difficulty 5.3 AIME, harder Prove it Taiwan

There are 65 couples going out together. Each boy has a motorcycle, and each is responsible for carrying one girl. Suppose they can arrange a way of carrying such that for any two motorcycles, exactly one of the following two propositions holds:
(i) The boys on these two motorcycles know each other;
(ii) The boyfriends of the girls on these two motorcycles know each other.
Prove that it is always possible to find a couple such that, after removing them, the remaining 64 couples can still be arranged in a way of carrying satisfying the above condition.

Solution

Suppose these 65 couples have already chosen an arrangement of carrying satisfying the conditions of the problem. We prove that there must be a couple on the same motorcycle (in fact there must be exactly one such couple), so that after removing them, the remaining 64 couples can simply keep using the original arrangement, which clearly satisfies the condition of the problem.

Number all the couples from 1 to 65, and define the function f(a)=bf(a) = b to mean that girl number aa is carried by boy number bb. Then f(a)f(a) is a one-to-one and onto function, so if for all 1a651 \le a \le 65 we keep substituting aa into ff until the value returns to aa, and write the process as a cycle, we obtain af(a)f(f(a))f(k)(a)=f(f(f(a)))=aa \rightarrow f(a) \rightarrow f(f(a)) \cdots \rightarrow f^{(k)}(a) = f(f(\cdots f(a)\cdots)) = a; in this way, 1 through 65 can be split into a number of disjoint cycles, so there must be a cycle with an odd number of elements. Suppose this cycle is
a1a2aka1 a_1 \rightarrow a_2 \rightarrow \cdots \rightarrow a_k \rightarrow a_1
where kk is odd.

Suppose k>1k > 1; we define the symbol g(a,b)g(a, b) to mean that boy number aa and boy number bb know each other, and <a,b><a, b> to mean that boy number aa and boy number bb do not know each other. Suppose we have (a1,a2)(a_1, a_2); then since f(a1)=a2,f(a2)=a3f(a_1) = a_2, f(a_2) = a_3, we know that the boyfriends of the girls carried by boy a2a_2 and boy a3a_3 (namely a1a_1 and a2a_2) know each other, and so we obtain <a2,a3><a_2, a_3>; similarly, from f(a2)=a3,f(a3)=a4f(a_2) = a_3, f(a_3) = a_4 we know that the boyfriends of the girls carried by boy a3a_3 and boy a4a_4 (namely a2a_2 and a3a_3) do not know each other, so boy a3a_3 and boy a4a_4 should know each other, giving us (a3,a4)(a_3, a_4); continuing this reasoning gives:
(a1,a2)<a2,a3>(a3,a4)(ak,a1)<a1,a2> (a_1, a_2) \rightarrow <a_2, a_3> \rightarrow (a_3, a_4) \cdots \rightarrow (a_k, a_1) \rightarrow <a_1, a_2>
a contradiction! If instead the case <a1,a2><a_1, a_2> held, the same reasoning can still be used to derive a contradiction!

Therefore k=1k=1, that is f(a1)=a1f(a_1) = a_1, which completes the proof.

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 translated into English from zh; metadata (topic, difficulty) added by this project.