We have $ n $ kinds of puddings. There are $ a_{i} $ puddings which are $ i $-th type and those $ S = a_{1}+\cdots+a_{n} $ puddings are distinct. Now, for a given arrangement of puddings: $ p_{1}, \dots, p_{n} $. Define $ c_{i} $ to be $$ \#\{1 \le j \le S-1 \ \mid \ p_{j}, p_{j+1} \text{ are the same type.}\} $$Show that if $ S $ is composite, then the sum of $ \prod_{i=1}^{n}{c_{i}} $ over all possible arrangements is a multiple of $ S $.
Problem
Source: 2019 Taiwan TST Round 3
Tags: combinatorics
stroller
05.04.2020 05:14
Are you sure you typed up the problem correctly?
stroller
06.07.2020 06:13
I thought it would be funnier to state the problem with the original flavor text included so here it is: Quote: The squad leader sees that old Zhao is bored carrying out soldier duties, so he ordered him to arrange some steamed buns. The buns have $n$ different colors with $a_i$ buns of color $i$, for a total of $S = \sum_{i=1}^n a_i$ buns. The $S$ buns are pairwise distinct (specifically two buns of the same color are also considered distinct). Old Zhao wants to arrange $S$ buns in a row. For each permutation of the buns, the squad leader uses the following way to rate old Zhao: (i) For each $i \in \{1,2,\dots, n\}$ let $c_i$ be the number of indices $j$ such that the $j$th and $j+1$st buns in the permutation (counting from left) all have color $i$. (ii) Old Zhao is given a score of $\prod_{i=1}^n c_i$. Suppose $S$ is composite, prove that the score of old Zhao over all possible permutations he can make is a multiple of $S$.
Let $S_i|\sigma$ be the set of positions of buns that have color $i$ given arrangement $\sigma$. Use $[\bullet]$ to denote the indicator function. Then
$$\sum_\sigma \prod_{i=1}^n c_i = \sum_\sigma \prod_{i=1}^n \sum_{j=1}^{S-1} [j\in S_i][j+1\in S_i] = \sum_\sigma \sum_{j_1,\dots,j_n = 1}^{S-1} \prod_{i=1}^n [j_i,j_{i+1} \in S_i] $$$$= \sum_{j_1,\dots,j_n = 1}^{S-1} \sum_{\sigma} \prod_{i=1}^n [j_i,j_{i+1} \in S_i]$$$$ = \sum_{j_1,\dots,j_n = 1}^{S-1} \#($\sigma$ \text{ such that } j_i,j_{i+1} \text{ have color } i \ \forall i).$$Note that for each $j_1,...,j_n$ such that the 2-element sets $\{j_i ,j_{i+1}\}$ are pairwise disjoint, this count is $\binom{S-2n}{a_1-2,\dots,a_n-2}$, and the count is $0$ otherwise. Therefore the sum of scores over all possible arrangements is $\binom{S-2n}{a_1 - 2,\dots, a_n - 2}\binom{S-n}{n}n! = \frac{(S-n)!}{(a_1 - 2)!\dots (a_n-2)!}$ (here we did not take into account the fact that the buns are pairwise distinct). Multiplying by $\prod_{i=1}^n a_i!$ to account for distinctness we obtain $(S-n)!\prod_i a_i(a_i-1)$ for the sum of scores.
It remains to show that $S| (S-n)!\prod_i a_i(a_i-1)$. If $a_i = 1$ for some $i$ then $S = 0$. Suppose now $a_i \ge 2 \forall i \implies S \ge 2n$. If $S | (S-n)!$ then we are done. Suppose now $S \nmid (S-n)!$, then there exists a prime $p|S$ with $\nu_p(S) > \nu_p((S-n)!)$. However the largest power of $p$ dividing $S$ is $\le S/2$, so this is impossible.