Let $A$ be a finite set of positive integers, and for each positive integer $n$ we define \[S_n = \{x_1 + x_2 + \cdots + x_n \;\vert\; x_i \in A \text{ for } i = 1, 2, \dots, n\}\] That is, $S_n$ 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 $$\left\vert S_{n + 1} \right\vert = \left\vert S_n \right\vert + k \text{ for all } n\geq 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 A$, $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.