Maths Olympiad Prep

Library / /753 of 860

Combinatorics Difficulty 5.5 AIME, harder Find the answer

In a chess-playing club, some of the players take lessons from other players. It is possible (but not necessary) for two players both to take lessons from each other. It so happens that for any three distinct members of the club, A,BA, B, and CC, exactly one of the following three statements is true: AA takes lessons from B;BB ; B takes lessons from C;CC ; C takes lessons from AA. What is the largest number of players there can be?

A number or a short expression. Spacing and $ signs are ignored.

Solution

If P,Q,R,SP, Q, R, S, and TT are any five distinct players, then consider all pairs A,BA, B \in {P,Q,R,S,T}\{P, Q, R, S, T\} such that AA takes lessons from BB. Each pair contributes to exactly three triples (A,B,C)(A, B, C) (one for each of the choices of CC distinct from AA and BB ); three triples (C,A,B)(C, A, B); and three triples (B,C,A)(B, C, A). On the other hand, there are 5×4×3=605 \times 4 \times 3=60 ordered triples of distinct players among these five, and each includes exactly one of our lesson-taking pairs. That means that there are 60/960 / 9 such pairs. But this number isn't an integer, so there cannot be five distinct people in the club. On the other hand, there can be four people, P,Q,RP, Q, R, and SS : let PP and QQ both take lessons from each other, and let RR and SS both take lessons from each other; it is easy to check that this meets the conditions. Thus the maximum number of players is 4.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.