Maths Olympiad Prep

Library / /16 of 30

Combinatorics Difficulty 6.0 National Olympiad Find the answer Italy

Problem:

Two schools compete in a chess tournament in which each school fields 75 students: 75 games are organized in which all students play one against another (a member of the first school against one from the second) under the supervision of an external referee. Each school numbers its own students from 1 to 75 and the referee imposes the rule that two boys cannot play against each other if the difference between their numbers is a multiple of 3. If nn is the number of possible pairings that satisfy this rule, with how many zeros does nn end?

Pick one

Solution

Solution:

The answer is (D). We divide the 75 students of each of the two schools into 3 groups, according to the remainder of their number when divided by 3. In particular, in the first school, the students are divided into groups A,B,CA, B, C according to whether their number is of the form 3k,3k+13k, 3k+1 or 3k+23k+2 for some integer kk. Similarly in the second school the students are divided among A,B,CA', B', C'.

Each of the groups A,B,C,A,B,CA, B, C, A', B', C' consists of 25 students, and group AA cannot play against group AA', just as BB cannot play against BB' and CC cannot play against CC'.

Suppose that mm people from group AA play against someone in BB' and the remaining 25m25-m play against CC'. Then mm people of BB play against the remaining mm in CC' and 25m25-m play against students of AA'. Consequently there are mm people in CC who play against group AA' and the remaining 25m25-m play against group BB'. Once mm is fixed, then, we choose mm people from A,B,CA, B, C in (25m)3\binom{25}{m}^3 ways. Furthermore we choose in how many ways the people in AA' play against the mm chosen in CC and the 25m25-m in BB in 25!25! ways and similarly for B,CB', C'. Varying mm, then, the number of possible pairings is

n=(25!)3m=025(25m)3 n = (25!)^3 \sum_{m=0}^{25} \binom{25}{m}^3

We note that (25m)\binom{25}{m} is divisible by 5 exactly if m0m \neq 0 and m25m \neq 25, hence

(25m)3=2+5h \binom{25}{m}^3 = 2 + 5h

is not a multiple of 5. The number nn therefore has as many factors of 5 as there are in (25!)3(25!)^3, that is 63=186 \cdot 3 = 18. We note that in 25!25! there are at least 6 factors of 2, for example because it includes 16816 \cdot 8, and therefore nn ends with exactly 18 zeros.

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 it; metadata (topic, difficulty) added by this project.