Question

40 people are sitting around a table. Everyone noticed that one of the people sitting
beside him is wearing a dress of the same colour as him, but the other one was wearing a
dress of different colour. What is the number of different dress colours of those people?

Answer 1

Question: 40 people are sitting around a table. Everyone noticed that one of the people sitting beside him is wearing a dress of the same colour as him, but the other one was wearing a dress of different colour. What is the number of different dress colours of those people?

Solution. Let us choose one of the people as the starting point ("first person") and numerate the dress colours (1, 2, etc.).

The first person should have a neighbour with similar dress colour; therefore, the second person will also be dressed in colour 1.

We now focus on the second person. He or she already has a neighbour with similar dress colour (first person); therefore, his or her other neighbour (third person) should not be dressed in colour 1.

Denote the dress colour of the third person as 2.

Applying the same logic, we obtain that the fourth person should be dressed in colour 2.

We can continue in the same manner and receive the following:

Note that the solution above is possible due to the fact that 40 is divisible by 2, and so the *fortieth* person is not dressed in the same colour as the *first*.

We have thus shown that the people in our question can be dressed in **20 different colours**.

However, this is not the only solution: we can repeat the initial steps, but instead of dressing the *fifth* person in colour **3**, dress him or her in colour **1** again, and so on:

Thus, another possible answer to this question is **2 different colours**.

Finally, we note that for every pair of neighbours dressed in the same colour, we can replace this colour with a new one without violating the rules, e.g. take the previous solution and only change the dress colour of the fifth and sixth person:

We see that 3 is also a possible answer to this problem.

In this manner, we can dress the people in any number of different colours between 2 and 20.

Answer. The 40 people can be dressed in any number of different colours between 2 and 20, inclusive ( $2 \leq x \leq 20$ , where $x$ is the number of different colours).