Problem

Source: 2019 Taiwan TST Round 3

Tags: combinatorics



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 $.