Pigeon hole principle application

158 Views Asked by At

I am watching a lecture on pigeonhole principle at this link.

enter image description here

At time 40:42, why does the instructor say that "either a will have 3 friends or 3 enemies". Why can't it be any of the other cases she mentions ?

Thanks.

2

There are 2 best solutions below

0
On

It can be, but in every case $a$ has at least $3$ friends or at least $3$ enemies, and that’s all that’s needed to make the rest of the argument work.

0
On

She states the possible cases: $$ \begin{array}{c:c} \mbox{friends} & \mbox{enemies}\\ \hdashline\\ 5 & 0\\ \hdashline\\ 4 & 1\\ \hdashline\\ 3 & 2\\ \hdashline\\ 2 & 3\\ \hdashline\\ 1 & 4\\ \hdashline\\ 0 & 5 \end{array} $$ So what she should have said was that A would have at least three either friends or enemies. There is no row above having both numbers less than 3 is another way of putting it.