Maths Olympiad Prep

Library / /25 of 30

Combinatorics Difficulty 6.7 National Olympiad Find the answer Italy

Problem:
At the Scuola Normale, this year's incoming students in the Science class are of four types: Mathematicians, Physicists, Chemists and Biologists. At the dining hall they all sit together around a round table; each of them has exactly one person sitting across from them, and moreover for every student the set consisting of himself, his right-hand neighbor, his left-hand neighbor and the student sitting opposite him includes all four types of students. How many can the incoming students of the Science class be, suitably divided among the four types, given that they are between 30 and 50 (inclusive)? Give as the answer the sum of all possible answers.

Pick one

Solution

Solution:
The answer is (B). Let mm be the number of Mathematicians and nn the total number of incoming students.
If for each freshman we consider the group consisting of that person, his right-hand neighbor, his left-hand neighbor and the person opposite him, we get nn groups, each of which contains exactly one Mathematician. On the other hand, each Mathematics freshman appears in exactly 4 of these groups (those corresponding to herself, to each of the two neighbors, and to the student seated opposite), from which n=4mn=4 m.

Let us now consider four people sitting next to one another counterclockwise, which we call a1,a2,a3,a4a_{1}, a_{2}, a_{3}, a_{4}. Without loss of generality we can say that the first three are, in order, of groups F,MF, M, and CC. The person a4a_{4}, however, could be FF or BB: let us now show that it is necessarily the second case.

Let us call bib_{i} the person sitting opposite aia_{i}. Then b2b_{2} is necessarily BB. If we consider b3b_{3}, who sits next to b2b_{2} counterclockwise, it cannot be BB or MM, because of the conditions given by b2b_{2}, but neither can it be CC, since it sits opposite a3a_{3}, which is CC. Hence b3b_{3} is FF and, similarly, b1b_{1} is CC. Let us now look at b4b_{4}: from the conditions on b3b_{3} we must exclude F,CF, C and BB, so it can only be MM. But then a4a_{4}, who sits opposite it, cannot be MM and must be BB.

So choosing the type of three people also fixes the fourth and, consequently, everything else. However, we must check that the patterns "fit together" well, since we must respect the condition on who sits opposite whom.

Let us number the seats around the table from 0 to 4m14 m-1. The person sitting opposite 0 is 2m2 m and, in general, the person sitting opposite kk is 2m+k2 m+k. We observe that people whose seat numbers lie in the same residue class modulo 4 have freshmen of the same type. Hence it is necessary that the residue class modulo 4 of kk and 2m+k2 m+k be different. If m=2hm=2 h, then 2m+k=4h+k4k2 m+k=4 h+k \equiv_{4} k, absurd. If instead m=2h+1m=2 h+1, then 2m+k=4h+2+k4k+22 m+k=4 h+2+k \equiv_{4} k+2. The people at the table, therefore, can be in a number that is a multiple of 4 but not of 8. Between 30 and 50 the numbers with these characteristics are 36 and 44, whose sum gives 80.

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.