Maths Olympiad Prep

Library / /52 of 65

Combinatorics Difficulty 6.3 National Olympiad Prove it Bulgaria

Problem:

Let m3m \geq 3 and n2n \geq 2 be integers. Prove that in a group of N=mnn+1N = m n - n + 1 people such that there are two familiar people among any mm, there is a person who is familiar with nn people. Does the statement remain true if N<mnn+1N < m n - n + 1?

Solution

Solution:

Consider a group with maximal number of people such that any two of them are not familiar. It is clear that if there are ll people in this group, then lm1l \leq m-1. Moreover, the maximality of ll implies that any of the other NlN-l people is familiar to at least one of the ll people in the group. Hence some of these ll people is familiar to at least Nll\frac{N-l}{l} people. Since
Nll=Nl1Nm11=n+1m11>n1 \frac{N-l}{l} = \frac{N}{l} - 1 \geq \frac{N}{m-1} - 1 = n + \frac{1}{m-1} - 1 > n-1
there is a person who is familiar to nn people.

Let N=mnn=(m1)nN = m n - n = (m-1) n and consider m1m-1 groups by nn people such that any two people from one group are familiar and there are no familiar people from different groups. Then among any mm people there are two from one and the same group, i.e. they are familiar. On the other hand, any of the people is familiar to n1n-1 of the other and hence the statement is not true if N<mnn+1N < m n - n + 1.

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