Maths Olympiad Prep

Library / /308 of 462

Combinatorics Difficulty 6.2 National Olympiad Prove it Ireland

A round table has 2N2N chairs around it. Due to social distancing guidelines, no two people are allowed to sit next to each other. How many different ways are there to choose seats around the table on which N1N-1 guests can be seated?

Solution

Solution 1. Either there are 3 consecutive empty seats or two separate pairs of empty seats. In the first case, there are 2N2N possibilities as the middle of the three empty seats can be any of the 2N2N seats. In the second case, there are two pairs of empty seats. If the seats are numbered 1 to 2N2N then one of the pairs of empty seats will be odd-even and the other even-odd. There are NN choices for the odd-even empty pair. For each of these there are N2N-2 choices for the odd number in the even-odd pair. That gives rise to N(N2)N(N-2) seating arrangements. Adding the two cases gives a total of N2N^2 possibilities.

Solution 2. Divide the 2N2N seats into NN pairs of consecutive seats. N1N-1 of these pairs contain one person and the other is empty. There are NN ways to choose which pair is empty. The remaining 2N22N-2 seats are occupied in the form 01 or 10 where 1 represents occupation. Working clockwise from the empty pair, the sequence starts with a (possibly empty) sequence of the form 101010...10 and finishes with a (possibly empty) sequence of the form 01...0101. Considering the possible lengths of the starting sequence we find that there are NN different possible sequences of this kind. This gives a total of N×NN \times N possibilities.

Solution 3. Let PnP_n be the path graph with nn edges. A set of vertices HH of a graph GG is an independent set if no two vertices of HH are adjacent. Let I(G,m)I(G, m) = the number of independent sets of size mm of the graph GG. Number the seats 1, 2, ..., 2N2N. There are two options:
(A) seat 1 is occupied and so seats 2 and 2N2N are empty;
(B) seat 1 is empty.
The number of possibilities in case (A) is I(P2N4,N2)I(P_{2N-4}, N-2) and in case (B) is I(P2N2,N1)I(P_{2N-2}, N-1). Using the ideas from solution 1 or 2 it is easy to show that I(P2k,k)=(k+2)(k+1)2I(P_{2k}, k) = \frac{(k+2)(k+1)}{2}. Hence the number of possibilities is equal to N(N1)2+(N+1)N2=N2\frac{N(N-1)}{2} + \frac{(N+1)N}{2} = N^2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.