9 students and 9 professors attend a dinner at which they sit at a round table. The organisers wish to arrange the seating so that no one is seated between two professors. Is this possible to meet this condition?
Solution: Imagine we have found an arrangement that meets the conditions. Ask every other person to stand up, so 9 people will be standing. Then we cannot have two professors separated by only a single seated person, otherwise that person would be flanked by professors. But this means only 4 of the 9 standing persons can be professors.
However the same reasoning can be applied to the 9 people who are sitting down, so we can only accommodate 8 professors altogether, leaving one professor unaccounted for.
Consequentially no arrangement can exist that meets the given condition.
Comments
New comment
VERY ELEGANT AND INTERESTING EXPLANATION.
New comment
To be clear I didn't originate the problem, nor the solution, I just wrote my own version. The the problem appeared in 102 Combinatorial Problems, by Titu Andreescu and Zuming Feng, and is discussed here and here, and in many other places