I am recently practicing the application of Pigeon Hole Principle. One of the classic exercise is to prove that 3 people must recognize or not recognize each other among a group of 6. And I was able to solve this problem. However, I was struggling to prove that 6 people must recognize or not recognize each other out of 12 people. Is this situation even reasonable?
My attempt to this problem is shown as below:
Assume A is one of these 12 people. According to the Pigeon Hole Principle, A must recognize/not recognize at least 6 people among the rest of 11 people.
Then I tries to solve the relationship of the 6 people with the classic 3 out of 6 exercise.
Assume B to be one of the 6 people that A recognizes, the rest we called C, D, E, F, G. According to the Pigeon Hole Principle again, we can know that B recognizes/not recognizes at least 3 people among C, D, E, F, G.
Assume B recognizes C, D, E:
- If one of (C, D), (D, E), (C, E) recognizes each other, then we can say 3 out of 6 recognizing each other is proven.
- If the above assumptions are not satisfied, then 3 out of 6 not recognizing each other is proven.
After this step, I am not capable of integrating the results to the primitive question.
The statement you're aiming to prove is actually not true!
The Ramsey numbers $R(a, b)$ tell the size of the smallest gathering of people such that there will always be either $a$ people who all recognize each other or $b$ people who all don't recognize each other. For example, $R(3,3) = 6$ is the "classic exercise" you mentioned.
Your question's desired claim is $R(6,6) <= 12$. But in fact the table on that Wikipedia page says $R(6,6)$ is not currently known, but people have proven that it's between $102$ and $161$. In other words, if you want to be sure that your gathering has a group of $6$ who all know each other or a group of $6$ who all don't know each other, then you need the gathering to include over a hundred people!