Maths Olympiad Prep

Library / /10 of 10

Combinatorics Difficulty 9.2 IMO level Prove it Vietnam

A school has two classes AA and BB which have mm and nn students each. The students of the two classes sit in a circle. Each student is then given a number of candies equal to the number of consecutive students sitting to the left of him that are from his same class. After distributing the candies, the teacher decides to group the students such that in each group, all the students receive the same amount of candies, and any two students from two different groups should receive a different amount of candies.
a) What is the maximum number of students that a group can have?
b) Excluding the group where every student receives no candies, what is the maximum number of students that a group can have?

Solution

Arrange m+nm+n students on a circle forming the arcs on which any two students are in the same class, and as few arcs as possible. Obviously with this division, two adjacent arcs contain students who are not in the same class. We claim that the number of students have candies is exactly the same as the number of arcs with at least i+1i+1 people. Indeed, if there is a student XX with ii candies, that means on the left hand side of XX, there are exactly ii classmates, so the arc contains at least i+1i+1 people. On the other hand, for each arc that has at least i+1i+1 people, the i+1i+1 students from the left side has exactly ii candies.

a) Since the number of students with ii candies is equal to the number of arcs with at least i+1i+1 people, the number of students without candy is exactly the same as the number of arcs. On the other hand, the number of students with ii candies is equal to the number of arcs with at least i+1i+1 people, and does not exceed the number of arcs of people, so the number of students that have 00 candies is the largest. We will prove that the maximum number of arcs is
2min(m,n). 2 \min(m, n).
Suppose that mnm \le n. Obviously, the maximum number of arcs that students are both in class AA is mm. On the other hand, the number of arcs containing students from AA is equal to the number of arcs containing students from BB, because between 22 consecutive arcs containing AA classmates there is exactly 11 arc containing BB classmates. So the number of arcs is twice times the number of arcs containing students from AA and no more than 2m2m. Equivalently, a group has at most 2m2m students. The equality is obtained when we arrange the mm arcs with 11 student from class AA, and mm arcs of students from BB.

b) For the same argument as above, the number of arcs containing at least 22 people is equal to the number of students having 11 of candy, an arc contains at least i+1i+1 where i>1i > 1 does not exceed the number of arcs containing at least 22 people, so we count the number of arcs containing at least 22 person and find the maximum number of such arcs. Assume mnm \le n. If there are xx arcs of students from AA then there are xx arcs of students from BB. Suppose there are aa arcs with at least 22 classmate of AA and bb arcs with at least 22 classmate of BB. We have two cases.
* If m<nm < n or m=nm = n and they are even. Since the number of arcs includes exactly 11 classmate of AA does not exceed m2am - 2a, so the maximum number of arcs is mam - a. Thus, maxbm - a \ge x \ge b or ma+bm \ge a + b. We show the equality holds.
* If m=2km = 2k then divide AA into kk arcs, each arc has at least 22 students, this is possible because mnm \le n. So there are 2k2k arcs.

◦ If m=2k1m = 2k - 1 then divide class AA into k1k - 1 arcs of 22 person and remaining 11 person. Since m<nm < n, then n2kn \ge 2k, class BB can be divided into kk arcs, each of which has at least 22 people. Therefore, we get 2k12k - 1 arcs with at least 22 students and a group has at most mm students.
• If m=n=2k+1m = n = 2k + 1. It's easy to see 2a<m2a < m and 2b<n2b < n so a,b<ka, b < k or having a maximum of 2k2k also has at least 22 people. The equality holds if dividing each class into kk arcs, where k1k - 1 contains 22 friends and 11 arc contains 33 friends and then alternates on the circle.

In conclusion, the answer is m1m - 1 when m=nm = n is odd and min(m,n)\min(m, n) in the rest of the cases. \square

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 and solution reproduced as published; topic and difficulty added by this site.