3
$\begingroup$

Problem: At a party there are $n$ people, some people give each other a hand. After the party everyone writes down on a piece of paper how many people he/she shook hands with. It turns out there are $n-1$ different numbers written down.Prove that there were two people at the party, such that every other person has shaken both of their hands or none of their hands.

My attempt: I want to try to prove this with induction on $n$.

Suppose that $n=3$. Then there are two different numbers written down. Without loss of generality, suppose that person 1 ($=p_1$) and person 2 ($=p_2$) have the same amount of handshakes, which is different from the amount of handshakes of $p_3$. Suppose that $p_3$ did a handshake with $p_1$, and not with $p_2$. In order for $p_2$ to get the same amount of handshakes, $p_2$ must shake hands with either $p_1$ or $p_3$. We said that $p_3$ didn't shake hands with $p_2$, so its only possible that $p_1$ shakes hands $p_2$, but then the difference in handshakes between $p_1$ and $p_2$ doesn't change, so contradiction. Conclusion: $p_3$ has either given both $p_1$ and $p_2$ a handshake or none of them.This concludes the induction basis.

Now we suppose that the situation where there are $n$ people, $n-1$ different numbers and $2$ people with the given constraints hold. Now we add another person to the party. The $n-1$ different numbers are numbers from the set $\{0,1,\ldots,n-1\}$ and we see that one number is not used. I will now prove that the number not used is either $0$ or $n-1$. Suppose that the number not used is not $0$ or $n-1$. Then we have a list with both $0$ and $n-1$ on it. But that means that there is a person that has shaken hands with no one and a person that has shaken hands with everyone (except themselves of course), so a contradiction.

My struggle: So at this point I realize that if the new person shakes hands with no one or everyone except themselves, the induction step holds (the same 2 people from the previous situation are the $2$ people in the new situation). But I am not sure how I can show this.

Does someone have suggestions for me about how to prove it/do it differently? I would love the hear feedback/get help.

$\endgroup$
7
  • $\begingroup$ Is this related to pigeonhole-principle? $\endgroup$ – Mathematician Jul 6 '20 at 10:00
  • $\begingroup$ No, this problem was given in chapter 1 of my book. The pigeonhole principle was given in chapter 2. $\endgroup$ – StudDC Jul 6 '20 at 10:03
  • $\begingroup$ From the problem description it sounds like you are supposed to prove that there are 2 people that either has shaken no hands or has shaken the hand of every other person, but in the base case you only prove this for 1 person (p3)? The problem description in that case sounds wrong since in the case of 3 people, it is possible 2 people shake hands and 1 person doesn't shake any hands? Or maybe I misunderstand something. $\endgroup$ – DancingIceCream Jul 6 '20 at 10:34
  • $\begingroup$ @DancingIceCream You are not understanding it properly. There are two people (p1,p2) such that for every other person (p3,...,pn) holds that every person p3,...,pn has either shaken the hand of both p1 and p2, or has not shaken the hand of p1 or p2 $\endgroup$ – StudDC Jul 6 '20 at 10:56
  • $\begingroup$ @StudDC Oh, I see. Now I understand. $\endgroup$ – DancingIceCream Jul 6 '20 at 11:13
5
$\begingroup$

It is sometimes easier to go in the opposite direction, using the contrapositive. So instead of:

Property true for $n-1$ implies property true for $n$.

you instead prove:

Property false for $n$ implies property false for $n-1$.

The above are equivalent, though if you now chain them together you get more of an infinite descent argument (and a proof by contradiction) than an induction argument.

The $n$ people shake hands somewhere from $0$ times to $n-1$ times. Clearly it is impossible for the party to contain someone who shakes no hands and someone who shakes hands with everybody, so the $n-1$ distinct numbers that are written down are either $0,...,n-2$ or $1,...,n-1$, and one of the numbers is written twice.

Suppose (for a contradiction) the two people who wrote the same number did not shake hands with exactly the same set of other people. Clearly that means they can't have written $0$ or $n-1$. Now remove the person who did write $0$ or $n-1$ from the party, and show that you now have a party of $n-1$ people who wrote $n-2$ numbers, and the two who wrote the same number did not shake hands with exactly the same set of other people.

So you can now repeat the argument until there are only $3$ or even $2$ people left. In that case the condition is impossible - it is not possible that the two people who shook the same number of hands did so with a different set of people. Therefore the assumption that this is possible in the party of $n$ people is also false.

$\endgroup$
6
  • $\begingroup$ I think that this argument can be used to prove my induction step (instead of n->n+1 I just prove (not n+1) -> (not n) in this fashion). Thanks! $\endgroup$ – StudDC Jul 6 '20 at 11:16
  • $\begingroup$ Btw a follow up question, so why cant you just prove (not n+1)-> (not n) for a general n instead of going all the way down until you are at the 'base case'? For me it's a bit odd that you choose to remove someone with a specific number (0 or n-1), go all the way down and then conclude that it doesn't hold generally. Couldn't it be the case that there is someone out there with a certain number and when you remove that person that it would hold? $\endgroup$ – StudDC Jul 6 '20 at 11:28
  • $\begingroup$ Oh ofc that person has to be removed in the case of n-1 handshakes, since otherwise you would have a party of n-1 people with someone who did n-1 handshakes, so a contradiction. But for the case that there is not someone with n-1 handshakes, but someone with 0 handshakes you have after the removal n-2 numbers with n-1 people. Still it could be the case with 0 handshakes that you could remove someone else instead of the 0 handshakes guy? $\endgroup$ – StudDC Jul 6 '20 at 11:39
  • 1
    $\begingroup$ @StudDC When you remove someone from the party, you have to then adjust the numbers that everyone who shook hands with him writes down, i.e. imagine what they write if the person hadn't turned up at all. If you remove some one other than the $0$ or $n-1$ person, then you are not guaranteed to still have just one pair of duplicate numbers. The proof needs to hold for all cases, so we don't do that. $\endgroup$ – Jaap Scherphuis Jul 6 '20 at 11:47
  • 1
    $\begingroup$ It is tricky to go by pure induction because it is easy to get the quantifiers wrong ("there exists", or "for all"). In the descent I assume there exists a counterexample for $n$, and using that specific case descend to a counterexample for the base case. When you go upwards, you are showing that the cases where the condition is true for $n$ can generate all cases where the condition is true for $n+1$. It is not as easy to get one's head around that. $\endgroup$ – Jaap Scherphuis Jul 6 '20 at 11:57
1
$\begingroup$

Rewrite the claim in the graph-theoretical form below. I shall use induction and prove the result directly.

Proposition. Let $n\geq 3$ be an integer, and $G(V,E)$ a simple graph on $n$ vertices. Suppose that there are exactly $n-1$ distinct values for the degrees of the vertices of $G$. Write $N_G(v)$ for the neighbor of $v\in V$ in $G$. Then, there are two distinct vertices $x$ and $y$ of $G$ such that $$N_G(x)\setminus\{x,y\}=N_G(y)\setminus\{x,y\}\,.$$

We induct on $n$. The case $n=3$ is proven by the OP. Let now $n>3$. Since the degree of each vertex of $G$ can be $0$, $1$, $2$, $\ldots$, $n-1$, there must exist a vertex of degree $0$ or $n-1$.

Case I: There exists a vertex $u$ of degree $0$. If there is another vertex $v$ of degree $0$, then $u$ and $v$ have the same (empty) neighbor, and we are done. If not, then removing $u$ from $G$, we obtain a graph $H$ on $n-1$ vertices such that there are exactly $(n-1)-1$ values for the degrees of its vertices. By induction hypothesis, $H$ has two vertices $v$ and $w$ such that $$N_H(v)\setminus\{v,w\}=N_H(w)\setminus\{v,w\}\,.$$ This also means that $$N_G(v)\setminus\{v,w\}=N_G(w)\setminus\{v,w\}\,,$$ since for each vertex in $H$, its neighbor in $H$ is the same as its neighbor in $G$.

Case II: There exists a vertex $u$ of degree $n-1$. Note that two vertices cannot both have degree $n-1$ (otherwise, the minimum degree of $G$ is $2$). By removing $u$, we get a graph $H$ on $n-1$ vertices such that there are exactly $(n-1)-1$ values for the degrees of its vertices. By induction hypothesis, $H$ has two vertices $v$ and $w$ such that $$N_H(v)\setminus\{v,w\}=N_H(w)\setminus\{v,w\}\,.$$ This also means that $$N_G(v)\setminus\{v,w\}=N_G(w)\setminus\{v,w\}\,,$$, since for each vertex in $H$, its neighbor in $G$ is the same as its neighbor in $H$ annexing $u$.


You can also prove the proposition by contradiction without induction. Let $G$ be the smallest graph (i.e., with the smallest value of $n$) that satisfies the hypothesis but not the conclusion of the proposition. Clearly, $n>3$. As before, $G$ has a vertex of degree $0$ or $n-1$.

Case I: There exists a vertex $u$ of degree $0$. Since $G$ violates the conclusion of the proposition, every other vertex of $G$ has degree at least $1$. By removing $u$ from $G$, we obtain a graph $H$ on $n-1$ vertices such that there are exactly $(n-1)-1$ values for the degrees of its vertices. By minimality of $G$, $H$ has two vertices $v$ and $w$ such that $$N_H(v)\setminus\{v,w\}=N_H(w)\setminus\{v,w\}\,.$$ This also means that $$N_G(v)\setminus\{v,w\}=N_G(w)\setminus\{v,w\}\,,$$, since for each vertex in $H$, its neighbor in $H$ is the same as its neighbor in $G$. This is a contradiction.

Case II: There exists a vertex $u$ of degree $n-1$. Note that two vertices cannot both have degree $n-1$ (otherwise, the minimum degree of $G$ is $2$). By removing $u$, we get a graph $H$ on $n-1$ vertices such that there are exactly $(n-1)-1$ values for the degrees of its vertices. By minimality of $G$, $H$ has two vertices $v$ and $w$ such that $$N_H(v)\setminus\{v,w\}=N_H(w)\setminus\{v,w\}\,.$$ This also means that $$N_G(v)\setminus\{v,w\}=N_G(w)\setminus\{v,w\}\,,$$, since for each vertex in $H$, its neighbor in $G$ is the same as its neighbor in $H$ annexing $u$. This is also a contradiction.


Remark. My two proofs and Jeap Scherphuis's proof are essentially the same.

$\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.