1
$\begingroup$

I was doing some old International Mathematical Olympiad (IMO) problems and one question went this way:

In a party with 1982 persons, among any group of 4, there is at least one person, who knows each of other three. What is the minimum number of people in the party who knows everyone else?

My knowledge of combinatorics is not working here. I'm stuck and completely blank, hope you guys can help me with it (You can use advance combinatorics but in a simple manner). Thanks.

$\endgroup$
  • $\begingroup$ This Aops post could help. $\endgroup$ – StubbornAtom Nov 17 '16 at 16:07
  • $\begingroup$ This was an USAMO question to be precise. $\endgroup$ – StubbornAtom Nov 17 '16 at 16:14
  • $\begingroup$ I was there at IMO '82, but this problem doesn't ring a bell. Are you sure? Ahh, it was USAMO '82. Ok. $\endgroup$ – Jyrki Lahtonen Nov 17 '16 at 17:24
  • $\begingroup$ it is possible that you are right, but it is mentioned in my book that it is IMO 1982 problem.Anyway that is not the matter. $\endgroup$ – Vidyanshu Mishra Nov 17 '16 at 17:28
  • $\begingroup$ I wonder what the answer would be if the question is changed to: "In a party with $n$ persons, among any group of $k$, there is at least one person who knows each of other $k-1$." $\endgroup$ – Batominovski Nov 18 '16 at 2:35
2
$\begingroup$

Hint. Show by induction for $n\geq 4$ that in a party with $n$ people, there are at least $(n-3)$ people who know everyone else.

$\endgroup$
1
$\begingroup$

Assume $A$ does not know everyone else, say $A$ does not know $B$. Assume there is a third person $C$ who does not know everyone else. Then for any other $X$, $X$ knows $A,B,C$. In particular, the person(s) $C$ does not know can at most be $A$ and/or $B$. By the same argument, if $X$ does not know everybody else, the persons $X$ does not know are at most among $A,B,C$ - but $X$ knows these.

$\endgroup$
  • 2
    $\begingroup$ You appear to use that the relation "knowing" is symmetric (notably you never consider the possibility that $B$ knows everyone). I don't think it can be inferred from the problem statement, nor do I think it is true in real life. $\endgroup$ – Marc van Leeuwen Nov 17 '16 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.