Seven people sit at a round table with 10 chairs. Show that there are three consecutive chairs that are occupied.

Question

Problem:

Seven people sit at a round table with 10 chairs. Show that there are three consecutive chairs that are occupied.

Solution:

Number the chairs from 1 to 10. There are 10 groups of three consecutive chairs:

{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}, {5, 6, 7}, {6, 7, 8}, {7, 8, 9}, {8, 9, 10}, {9, 10, 1}, {10, 1, 2}

Each of the seven people will belong to three of these groups,

and 21 people have to be allocated to 10 groups.

Since 21 = 2 * 10 + 1

the generalised pigeonhole principle guarantees that some group must contain three people.

Reference 1: Pigeonhole principle:

If n + 1 or more objects are placed into n holes, then some hole contains at least two objects.

Reference 2: Generalised pigeonhole principle:

If at least mn + 1 objects are placed into n holes, then some hole contains at least m + 1 objects.

Question:

Q1:

If I look at number 1, it belongs to {1, 2, 3}, {9, 10, 1}, {10, 1, 2}; however, this number 1 is the chair number.

So what is the reasoning behind "seven people will belong to three of these groups" and 21 people have to be allocated to 10 groups.

Q2:

About "21 people have to be allocated to 10 groups.", I assume the each group is a pigeonhole, each pigeon can go to multiple holes. Then what exactly does the word "allocated" mean in this context?

In general, I don't quite understand how a single pigeon can go to multiple holes.

Your help is appreciated.

Answer 1

You can use the pigeonhole principle here, but basically each position belongs to three holes. Thus instead of $7$ objects you have to count $3\cdot 7=21$ objects, as each one will be put in three holes (so you kind of clone each pidgeon).

Of course we are considering a different problem here, as these categories are linked. If we clone pidgeon $P_1$ to $P_1^1,P_1^2,P_1^3$ then $P_1^1\in[1,2,3],P_1^2\in[2,3,4],P_1^3\in[3,4,5]$ is thinkable, but $P_1^1\in[1,2,3],P_1^2\in[4,5,6],P_1^3\in[7,8,9]$ is not, as well as $P_1^1\in[1,2,3],P_1^2\in[2,3,4],P_1^3\in[2,3,4]$ is not or $P_1^1\in[1,2,3],P_1^2\in[3,4,5],P_1^3\in[2,3,4]$ is not.

But that is not a problem: Although there exists more possibilites to allocate 21 pidgeons to these groups what actually is possible here, it is still sufficient to argue that in every configuration at least one group will be hit thrice. So in the worst case we get a configuration that is not possible with the links that allows for each group being hit at most twice, but this does not turn out to be the case.

Allocating is just used for assigning some sort of space. You could also say "is put into" or something.

Answer 2

$$1\to \{9,10,1\},\{10,1,2\},\{1,2,3\}$$ $$4\to \{2,3,4\},\{3,4,5\},\{4,5,6\}$$ $$7\to \{5,6,7\},\{6,7,8\},\{7,8,9\}$$ We've hit all but $$\{8,9,10\}$$ once. Since picking $10$ forces avoiding $2$ or $9$ ,we'd have to pick from $3$, $5$, $6$ , or $8$ but we can't pick both in pairings $\{3,5\}$,$\{5,6\}$ , or $\{6,8\}$. Similar choice elimination happens if you choose $8$ or $9$. Choosing just 1 from each pair chooses $5$ and $8$, at least, but leaves us $1$ shy forcing one of these pairs to be used up.