MathDB

3

Part of 2010 Costa Rica - Final Round

Problems(1)

Sequence of numbers

Source: Costa Rica National Olympiad, Final Round, Problem 3

10/14/2011
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)i) In the screen of the box will appear a sequence of n+1n+1 numbers, C0=(a0,1,a0,2,...,a0,n+1)C_0 = (a_{0,1},a_{0,2},...,a_{0,n+1})
ii)ii) If the code K=(k1,k2,...,kn)K = (k_1,k_2,...,k_n) opens the security box then the following must happen:
a) A sequence Ci=(ai,1,ai,2,...,ai,n+1)C_i = (a_{i,1},a_{i,2},...,a_{i,n+1}) will be asigned to each kik_i defined as follows:
ai,1=1a_{i,1} = 1 and ai,j=ai−1,j−kiai,j−1a_{i,j} = a_{i-1,j}-k_ia_{i,j-1}, for i,j≥1i,j \ge 1
b) The sequence (Cn)(C_n) asigned to knk_n satisfies that Sn=∑i=1n+1∣ai∣S_n = \sum_{i=1}^{n+1}|a_i| has its least possible value, considering all possible sequences KK.
The sequence C0C_0 that appears in the screen is the following:
a0,1=1a_{0,1} = 1 and a0,ia_0,i is the sum of the products of the elements of each of the subsets with i−1i-1 elements of the set A=A = {1,2,3,...,n1,2,3,...,n}, i≥2i\ge 2, such that a0,n+1=n!a_{0, n+1} = n!
Find a sequence K=(k1,k2,...,kn)K = (k_1,k_2,...,k_n) that satisfies the conditions of the problem and show that there exists at least n!n! of them.
algorithmalgebrapolynomialalgebra unsolved