Representatives from n > 1 different countries sit around a table. If two people are from the same country then their respective right hand neighbors are from different countries. Find the maximum number of people who can sit at the table for each n.
Solution
Answer: n2.
Obviously there cannot be more than n2 people. For if there were, then at least one country would have more than n representatives. But there are only n different countries to choose their right-hand neighbours from. Contradiction.
Represent someone from country i by i. Then for n = 2, the arrangement 1122 works. [It wraps round, so that the second 2 is adjacent to the first 1.] Suppose we have an arrangement for n. Then each of 11, 22, ... , nn must occur just once in the arrangement. Replace 11 by 1(n+1)11, 22 by 2(n+1)22, ... , and (n-1)(n-1) by (n-1)(n+1)(n-1)(n-1). Finally replace nn by n(n+1)(n+1)nn. It is easy to check that we now have an arrangement for n+1. We have added one additional representative for each of the countries 1 to n and n+1 representatives for country n+1, so we have indeed got (n+1)2 people in all. We have also given a representative of each country 1 to n a neighbour from country n+1 on his right and we have given the (n+1) representatives from country n+1 neighbours (on their right) from each of the other countries. Otherwise we have left the seating unchanged.
© John Scholes
jscholes@kalva.demon.co.uk
24 Oct 2002