Maths Olympiad Prep

Library / /72 of 104

Combinatorics Difficulty 6.2 National Olympiad Prove it Bulgaria

Problem:

In a group of nn people there are three that are familiar to each other and any of them is familiar with more than half of the people in the group. Find the minimum possible triples of familiar people?

Solution

Solution:

Denote by AA, BB and CC the three familiar people in the group.
Let n=2k+1n=2k+1 be an odd integer. Then any of AA, BB and CC has at least k+1k+1 familiar ( k1k-1 of them are not AA, BB or CC ). Denote by TT the set of all people except AA, BB and CC and let aia_{i}, i=0,1,2,3i=0,1,2,3, be the set of the people in TT who have exactly ii familiar among AA, BB and CC.
Then a0+a1+a2+a3a_{0}+a_{1}+a_{2}+a_{3} is the number of all members of TT, i.e. we have
a0+a1+a2+a3=2k2 a_{0}+a_{1}+a_{2}+a_{3}=2k-2
On the other hand, a1+2a2+3a3a_{1}+2a_{2}+3a_{3} is the number of all familiar to AA, BB and CC, i.e. we have
a1+2a2+3a33k3 a_{1}+2a_{2}+3a_{3} \geq 3k-3
Hence
3k3a1+2a2+3a3=a0+a1+a2+a3+a2+2a3=2k2+a2+2a3 \begin{aligned} 3k-3 &\leq a_{1}+2a_{2}+3a_{3}=a_{0}+a_{1}+a_{2}+a_{3}+a_{2}+2a_{3} \\ &=2k-2+a_{2}+2a_{3} \end{aligned}
and therefore a2+2a3k1a_{2}+2a_{3} \geq k-1.
Since any familiar to two of AA, BB and CC is a member of a triple of familiar people and any familiar to AA, BB and CC is member of three such triples, then the number of these triples is at least 1+a2+3a31+a_{2}+3a_{3}. Thus 1+a2+3a3>a2+2a3k11+a_{2}+3a_{3}>a_{2}+2a_{3} \geq k-1, which means that the number of the triples is not less than kk.
It remains to construct an example with kk triples of familiar people. Let there be no familiar people in TT. If AA is familiar to exactly k1k-1 people of TT, and BB and CC to the remaining k1k-1, then the number of the triples is kk.

Let n=2kn=2k be even. As in the previous case, we get that the number of the triples of familiar people is at least k+1k+1. If AA and BB have exactly one common familiar person from TT (it is possible, since T=2k3|T|=2k-3 and the familiar to AA and BB are at least k1k-1 ) who is not familiar to CC, then the number of the triples is exactly k+1k+1.

So the answer of the problem is kk for n=2k+1n=2k+1 and k+1k+1 for n=2kn=2k.

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.