2021 WSMO Team Round/Problem 8

Problem

Isaac, Gottfried, Carl, Euclid, Albert, Srinivasa, René, Adihaya, and Euler sit around a round table (not necessarily in that order). Then, Hypatia takes a seat. There are possible seatings where Euler doesn't sit next to Hypatia and Isaac doesn't sit next to Gottfried, where is maximized. Find . (Rotations are not distinct, but reflections are).

Proposed by mahaler

Solution

We can use complementary counting. The number of ways that they can sit around the round table without restrictions is . The number of ways that don't work is equal to the sum of ways where Euler sits next to Hypatia and the ways where Isaac sits next to Gottfried minus the number of ways where both of these conditions are satisfied. If we have one pair of people, we can think of them as one person and order them from there. Therefore the number of ways is for one pair of people is equal to . For two pairs, we can do the same thing but for two pairs. That is, . The number of ways that don't work is therefore . Finally, we subtract this from the total amount of ways there are to sit around the round table. . Since is maximized (44 is not divisible by 8), the answer is . ~programmeruser