$25$ little donkeys stand in a row; the rightmost of them is Eeyore. Winnie-the-Pooh wants to give a balloon of one of the seven colours of the rainbow to each donkey, so that successive donkeys receive balloons of different colours, and so that at least one balloon of each colour is given to some donkey. Eeyore wants to give to each of the $24$ remaining donkeys a pot of one of six colours of the rainbow (except red), so that at least one pot of each colour is given to some donkey (but successive donkeys can receive pots of the same colour). Which of the two friends has more ways to get his plan implemented, and how many times more? Eeyore is a character in the Winnie-the-Pooh books by A. A. Milne. He is generally depicted as a pessimistic, gloomy, depressed, old grey stuffed donkey, who is a friend of the title character, Winnie-the-Pooh. His name is an onomatopoeic representation of the braying sound made by a normal donkey. Of course, Winnie-the-Pooh is a fictional anthropomorphic bear. Proposed by F. Petrov
Problem
Source: Tuymaada 2012, Problem 8, Day 2, Juniors
Tags: combinatorics proposed, combinatorics
22.07.2012 23:04
In fact both these numbers can be computed. Label the colours of the rainbow by $1,2,3,4,5,6,7$, with red being the $7$-th. Denote by $A_k$, $1\leq k\leq 7$, the set of ways to give balloons of any but the $k$-th colour to $25$ donkeys, so that neighbouring donkeys receive balloons of different colour (though maybe not all $6$ of the available colours are being used). Clearly, for any $K\subseteq \{1,2,3,4,5,6,7\}$, we have $\displaystyle \left |\bigcap_{k\in K} A_k\right | = (7-|K|)(6-|K|)^{24}$. By the Principle of Inclusion/Exclusion (PIE) we have \[\left |\bigcup_{k=1}^7 A_k\right | = \sum_{\ell = 1}^7 (-1)^{\ell-1}\sum_{|K| = \ell}\left |\bigcap_{k\in K} A_k\right | = \sum_{m = 0}^6 (-1)^{m}\binom {7} {m} m(m-1)^{24}.\] Now, denote by $A_0$ the set of ways to give balloons of any of the colours of the rainbow to $25$ donkeys, so that neighbouring donkeys receive balloons of different colour (though maybe not all $7$ of the available colours are being used). Clearly $|A_0| = 7\cdot 6^{24}$. The number we are looking for, the number of such ways that use all $7$ colors, is therefore \[\displaystyle |A_0| - \left |\bigcup_{k=1}^7 A_k\right |= \sum_{m = 0}^7 (-1)^{m-1}\binom {7} {m} m(m-1)^{24}.\] We have now to compute the number of ways to distribute pots, i.e. $6$ colours (no red), $24$ donkeys, no restriction for neighbouring donkeys, but all $6$ colours to be used. Denote, following the fashion of above, by $B_k$, $1\leq k\leq 6$, the set of ways to give pots of any but red and the $k$-th colour to $24$ donkeys (though maybe not all $5$ of the available colours are being used). Clearly, for any $K\subseteq \{1,2,3,4,5,6\}$, we have $\displaystyle \left |\bigcap_{k\in K} B_k\right | = (6-|K|)^{24}$. By the Principle of Inclusion/Exclusion (PIE) we have \[\left |\bigcup_{k=1}^6 B_k\right | = \sum_{\ell = 1}^6 (-1)^{\ell-1}\sum_{|K| = \ell}\left |\bigcap_{k\in K} B_k\right | = \sum_{m = 0}^5 (-1)^{m-1}\binom {6} {m} m^{24}.\] Now, denote by $B_0$ the set of ways to give pots of any of the colours of the rainbow but red to $24$ donkeys (though maybe not all $6$ of the available colours are being used). Clearly $|B_0| = 6^{24}$. The number we are looking for, the number of such ways that use all $6$ colors, is therefore \[\displaystyle |B_0| - \left |\bigcup_{k=1}^6 B_k\right |= \sum_{m = 0}^6 (-1)^{m}\binom {6} {m} m^{24}.\] All it remains is to notice that, term by term, \[\sum_{m = 1}^7 (-1)^{m-1}\binom {7} {m} m(m-1)^{24} = 7\sum_{m = 0}^6 (-1)^{m}\binom {6} {m} m^{24},\] so there are $\boxed{7}$ more ways to distribute balloons than pots. Alternative Official Solution. This method does not actually count the ways, but rather establishes a one-to-one correspondence between Eeyore's ways to distribute pots and Winnie's ways to distribute balloons, all the while giving Eeyore a red one. In a nutshell, pots and balloons have the same color, except when a pair of two consecutive pots share a same color, in which case the colour of the second balloon in the pair is red. Now, the total number of ways Winnie can distribute balloons is $\boxed{7}$ times larger, since the balloon given to Eeyore may be of any of the $7$ colours, not just red, and clearly for each of the colours of the balloon given to Eeyore there are a same number of ways to do it.
01.11.2014 16:42
Another way to solve this is first fix the color of Eeyore,$WLOG$ color $7$.Now,fix the ballons(pots) where the first ballon(pot)(our first pot is Eeyore) occured of color $1$,color $2$,etc color $6$.Now,it is easy to see that the number of ways to give ballons from k-color that occured to $k+1$-color are the same,so we are finished.