0
$\begingroup$

There are $n$ people in the room, some know each other and some don't. If $i$ knows $j$, then $j$ knows $i$. Suppose that for every four different people there exists one who knows the remaining three. A person who knows all the rest is called "connected".

a. Prove that there exists a "connected" person

b. Prove that at least $n-3$ people are "connected"

$\endgroup$
0
1
$\begingroup$

HINT for (a): Suppose that there is no connected person. Then for each person $p$ there is a person $q$ whom $p$ does not know. Pick a person $p$, and let $q$ be someone whom $p$ does not know. Pick a third person, $r$, different from both $p$ and $q$.

  • If $r$ knows both $p$ and $q$, then there must be a fourth person, $s$, whom $r$ does not know. Is the set $\{p,q,r,s\}$ possible under the hypotheses of the problem?

  • Suppose that $r$ does not know $p$, and let $s$ be any fourth person different from $p,q$, and $r$. Then $s$ must know each of $p,q$, and $r$; why? Still, there is some person $t$ whom $s$ does not know; consider the set $\{p,q,s,t\}$.

HINT for (b): If the assertion is false, then there are at least $4$ people who are not connected. That’s enough unconnected people for you to carry out a slight modification of the argument sketched above for (a).

$\endgroup$

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.