Let A be a finite set of positive integers, and for each positive integer n we define Sn={x1+x2+⋯+xn|xi∈A for i=1,2,…,n} That is, Sn is the set of all positive integers which can be expressed as sum of exactly n elements of A, not necessarily different. Prove that there exist positive integers N and k such that |Sn+1|=|Sn|+k for all n≥N. Proposed by Ariel García
Problem
Source: Mexico National Olympiad Mock Exam 2018 Problem 6
Tags: combinatorics, elements of set
plagueis
07.11.2018 06:19
Any solutions?
Define a=min, B = \{x - a \;\vert\; x \in A\}, C = B \setminus \{0\}, and T_n = \{x_1 + x_2 + \dots + x_n \;\vert\; x_i \in B\}. Then observe that T_n = \{x_1 + x_2 + \dots + x_k \;\vert\; x_i \in C, k \leq n\}.
plagueis
08.11.2018 02:06
Since there are no solutions, I'll post the official one
Let a = \min A and B = \{x - a \;\vert\; x \in A\}. B is a set of non-negative integers which contains zero. Let T_n = \{x_1 + x_2 + \dots + x_n \;\vert\; x_i \in B\}, then it is clear that S_n = \{t + an \;\vert\; t \in T_n\}, and thus \vert S_n \vert = \vert T_n \vert. Let now C = B \setminus \{0\}, then we can check that
T_n = \{x_1 + x_2 + \dots + x_k \;\vert\; x_i \in C, k \leq n\}
since we can add n - k zeros to an element of this set so as to obtain an element of B. From this it follows that T_{n - 1} \subseteq T_n. Then we have
\vert S_n \vert - \vert S_{n - 1} \vert = \vert T_n \vert - \vert T_{n - 1} \vert = \vert T_n \setminus T_{n - 1} \vert
And we want to prove that for large n, the cardinality of this set is constant. This set consists of all positive integers which can be represented as sum of n elements of C, but not less.
Let C = \{c_1, c_2, \dots, c_m\} where c_1 < c_2 < \dots < c_m. Let us observe that each sum of elements of C can be written in the form
x = a_1c_1 + a_2c_2 + \dots + a_mc_m
Where a_1, a_2, \dots, a_m are non-negative integers. In this way we can assign x the m-tuple (a_1, a_2, \dots, a_m), where each number can have multiple assigned tuples.
We now show a useful way to choose for each number only one of its assigned tuples. For a tuple a we denote s(a) = a_1 + a_2 + \dots + a_m. We say that a tuple a is less than another tuple a' if one of the following conditions holds:
\begin{align*}
1.\quad&\quad s(a) < s(a') \\
2.\quad&\quad s(a) = s(a') \text{ and } a_m > a'_m \\
3.\quad&\quad s(a) = s(a'), a_m = a'_m \text{ and } a_{m - 1} > a'_{m - 1} \\
4.\quad&\quad s(a) = s(a'), a_m = a'_m, a_{m - 1} = a'_{m - 1} \text{ and } a_{m - 2} > a'_{m - 2}\\
\vdots\hspace{1.5em}& \\
(m + 1).&\quad s(a) = s(a'), a_i = a'_i \text{ for } i = 2, 3, \dots, m \text{ and } a_1 > a'_1
\end{align*}
This introduces an order for the tuples assigned to x, for each x. For each x let us consider then its assigned tuple \tau(x) which is minimal under this order. Then, we can easily see x \in T_n\setminus{T_{n - 1}} if and only if s(\tau(x)) = n.
Consider now some tuple t = \tau(x). Let us see first that t_i < c_m for i = 1, 2, \dots, m - 1, otherwise we can replace c_m appearances of c_i by c_i of c_m to obtain a lower tuple. As the t_i are non-negative integers this implies that (t_1, t_2, \dots, t_{m - 1}) have a finite number of possible values. Then we can define the finite set
\Omega_n = \{(t_1, t_2, \dots, t_{m - 1}) \;\vert\; s(t) = n \text{ y } t = \tau(x) \text{ for some } x\}
We claim that for all n suficciently large, \Omega_n \subseteq \Omega_{n + 1}. Let us consider some m-tuple t such that (t_1, t_2, \dots, t_{m - 1}) \in \Omega_n. We claim that the tuple t' = (t_1, t_2, \dots, t_m + 1) makes that (t_1, t_2, \dots, t_{m - 1}) is in \Omega_{n + 1}. If this does not hold then there must be a tuple r = (r_1, r_2, \dots, r_m) assigned to the same number than t' which is lower than t'. If r_m > 0 then r' = (r_1, r_2, \dots, r_m - 1) is less than t, contradicting that t \in \Omega_n. Thus r_m = 0. But since r_i < c_m this gives
r_1c_1 + r_2c_2 + \dots + r_mc_m < c_m(c_1 + c_2 + \dots + c_{m - 1}) = C
So that for n suficciently large (n > \max \{s(\tau(x)) \;\vert\; x < C\}) this tuple cannot exist, thus proving our result.
Since \Omega_n \subseteq \Omega_{n + 1} for n suficciently large, and all sets are subsets of some finite set, there existe an N and a set \Omega such that \Omega_n = \Omega for all n \geq N. Taking this N y k = \vert \Omega \vert we get the desired result.