Maths Olympiad Prep

Library / /49 of 61

Combinatorics Difficulty 6.4 National Olympiad Prove it Ibero-American Mathematical Olympiad

Problem:

Representatives from n>1n > 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 nn.

Solution

Solution:

Answer: n2n^{2}.

Obviously there cannot be more than n2n^{2} people. For if there were, then at least one country would have more than nn representatives. But there are only nn different countries to choose their right-hand neighbours from. Contradiction.

Represent someone from country ii by ii. Then for n=2n = 2, the arrangement 11221122 works. [It wraps round, so that the second 22 is adjacent to the first 11.] Suppose we have an arrangement for nn. Then each of 11,22,,nn11, 22, \ldots, nn must occur just once in the arrangement. Replace 1111 by 1(n+1)111(n+1)11, 2222 by 2(n+1)222(n+1)22, \ldots, and (n1)(n1)(n-1)(n-1) by (n1)(n+1)(n1)(n1)(n-1)(n+1)(n-1)(n-1). Finally replace nnnn by n(n+1)(n+1)nnn(n+1)(n+1)nn. It is easy to check that we now have an arrangement for n+1n+1. We have added one additional representative for each of the countries 11 to nn and n+1n+1 representatives for country n+1n+1, so we have indeed got (n+1)2(n+1)^{2} people in all. We have also given a representative of each country 11 to nn a neighbour from country n+1n+1 on his right and we have given the (n+1n+1) representatives from country n+1n+1 neighbours (on their right) from each of the other countries. Otherwise we have left the seating unchanged.

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.