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
05.04.2020 05:14
Are you sure you typed up the problem correctly?
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$.