CR-MO 2010 Problem 3

Christian Reiher and Reid Barton want to open a security box, they already managed to discover the algorithm to generate the key codes and they obtained the following information: $i)$ In the screen of the box will appear a sequence of $n+1$ numbers, $C_0 = (a_{0,1},a_{0,2},...,a_{0,n+1})$ $ii)$ If the code $K = (k_1,k_2,...,k_n)$ opens the security box then the following must happen:

a) A sequence $C_i = (a_{i,1},a_{i,2},...,a_{i,n+1})$ will be asigned to each $k_i$ defined as follows: $a_{i,1} = 1$ and $a_{i,j} = a_{i-1,j}-k_ia_{i,j-1}$ , for $i,j \ge 1$ b) The sequence $(C_n)$ asigned to $k_n$ satisfies that $S_n = \sum_{i=1}^{n+1}|a_i|$ has its least possible value, considering all possible sequences $K$ .

The sequence $C_0$ that appears in the screen is the following: $a_{0,1} = 1$ and $a_0,i$ is the sum of the products of the elements of each of the subsets with $i-1$ elements of the set $A =$ { $1,2,3,...,n$ }, $i\ge 2$ , such that $a_{0, n+1} = n!$ Find a sequence $K = (k_1,k_2,...,k_n)$ that satisfies the conditions of the problem and show that there exists at least $n!$ of them.