Maths Olympiad Prep

Library / /405 of 462

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Ireland

Let nn be a positive integer. Consider all arrangements of nn identical green coins, nn identical white coins and nn identical orange coins in a row. Each such arrangement of 3n3n coins can be considered as a sequence of blocks, where coins within a block have the same colour and any two adjacent blocks contain coins of two different colours. For example, for the case n=4n = 4, the arrangement GGGOOWOOGWWWW is formed by 6 blocks, namely GGG, OO, W, OO, G and WWW.
Show that the average number of blocks, over all distinct arrangements of the 3n3n coins, can be expressed in the form An+BAn+B, and determine the values of the constants AA and BB.

Solution

For any arrangement, we say that a position k{2,3,,3n}k \in \{2, 3, \dots, 3n\} is a change if and only if the coin at position kk has a different colour to the coin at position k1k-1. Note that the number of blocks in any arrangement is one greater than the number of changes in that arrangement. For instance, the example arrangement given in the problem statement contains 5 changes (at positions 4, 6, 7, 9 and 10), and the number of blocks is 5+1=65+1=6.

Next we count the total number of changes in all distinct coin arrangements, partitioning the count according to the position k{2,3,,3n}k \in \{2, 3, \dots, 3n\} at which the change occurs (denote this total number of changes by NcN_c). If position kk is a change, we can choose the coin at position kk in 3 ways and the coin at position k1k-1 in 2 ways. For the remaining positions we can arrange the coins in (3n2)!/(n!(n1)!(n1)!)(3n-2)!/(n!(n-1)!(n-1)!) ways. Since the number of blocks is always one greater than the number of changes, we obtain
Nc=(3n1)32(3n2)!n!(n1)!(n1)!=2n(3n)!(n!)3 N_c = (3n - 1) \cdot 3 \cdot 2 \cdot \frac{(3n - 2)!}{n!(n - 1)!(n - 1)!} = 2n \cdot \frac{(3n)!}{(n!)^3}
where the factor 3n13n-1 accounts for all of the possible change positions i.e., all possible values of k{2,3,,3n}k \in \{2, 3, \dots, 3n\}.

Since the number of blocks is always one greater than number of changes, the total number of blocks NbN_b over all distinct coin arrangements, is obtained from NcN_c by adding (3n)!/(n!)3(3n)!/(n!)^3, which is equal to the total number of distinct coin arrangements, hence
Nb=Nc+(3n)!(n!)3=(2n+1)(3n)!(n!)3 N_b = N_c + \frac{(3n)!}{(n!)^3} = (2n + 1)\frac{(3n)!}{(n!)^3}
Thus the average number of blocks over all distinct coin arrangements is
Nb=Nc[(3n)!(n!)3]1=2n+1. N_b = N_c \cdot \left[ \frac{(3n)!}{(n!)^3} \right]^{-1} = 2n + 1.
Thus we have established the result, with A=2A = 2 and B=1B = 1.

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.