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 to mean that girl number is carried by boy number . Then is a one-to-one and onto function, so if for all we keep substituting into until the value returns to , and write the process as a cycle, we obtain ; 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
where is odd.
Suppose ; we define the symbol to mean that boy number and boy number know each other, and to mean that boy number and boy number do not know each other. Suppose we have ; then since , we know that the boyfriends of the girls carried by boy and boy (namely and ) know each other, and so we obtain ; similarly, from we know that the boyfriends of the girls carried by boy and boy (namely and ) do not know each other, so boy and boy should know each other, giving us ; continuing this reasoning gives:
a contradiction! If instead the case held, the same reasoning can still be used to derive a contradiction!
Therefore , that is , which completes the proof.