Let be a sequence of $ 51 $ natural numbers whose sum is $ 100. $ Show that for any natural number $ 1\le k<100 $ there are some consecutive numbers from this sequence whose sum is $ k $ or $ 100-k. $
Problem
Source: 2019 Danube
Tags: number theory, combinatorics, Sequence
31.10.2019 19:21
Anyone solved it? It seems to be hard
02.11.2019 04:15
Let the sequence be: $\{a_1, a_2, ..., a_{51}\}$, and $s_n=a_1+a_2+...+a_n$. Suppose $s_0=0$, and $S=\{s_0, s_1, ..., s_{51}\}$. So that $0=s_0<s_1<s_2<...<s_{51}=100$. For any specific $1\le k<100$, There exists $m$, $0<m<51$, so that $s_{m-1}+k<100$, and $s_{m}+k \ge 100$. Consider $A=\{s_1+k, s_2+k, ..., s_{m-1}+k\}$, and $B=\{s_m-(100-k), s_{m+1}-(100-k), ..., s_{51}-(100-k)\}$. Notice that, for any $p \in A$ and $q \in B$, 1. $0 \le p, q \le 100$. 2. $p>q$. Since $p \ge s_1+k > k = s_{51}-(100-k) \ge q$. Let $C=A\mathop{\cup}B$. There are 51 elements in $C$, and note that there are 52 elements in $S$. All the elements in $C$ or $S$ are within [0,100], which has only 101 integers. Due to Pigeonhole principle, there is at least one element both appearing in $C$ and $S$, supposing it $s_i$. If $s_i$ appears in $A$, then $s_i=s_j+k$. So that $k=s_i-s_j=a_{j+1}+ ... +a_i$. If $s_i$ appears in $B$, then $s_i=s_j-(100-k)$. So that $100-k=s_j-s_i=a_{i+1}+ ... +a_j$.
02.11.2019 19:35
Nice solution!
12.11.2020 00:23
Consider partial sums $s_i = a_1 + \ldots + a_i$ from $s_1$ to $s_{51}$. Clearly the $s_i$ are from $1$ to $100$, inclusive. If $k \geq 50$, then say we create the pairs\[(1, k+1), (2, k+2), \ldots , (100 - k, 100).\]There are $100 - k \leq 50$ such pairs. If we assign the $51$ partial sums $s_i$ to their values in the $100 - k \leq 50$ above pairs, then one pair must recieve two partial sums (by Pigeonhole), say pair $(j, j+k)$ receives partial sums $s_{\ell}, s_{m}$ with $\ell < m$. Then\[s_m - s_{\ell} = a_{\ell + 1} + \ldots + a_m = (j+k) - j = k\]as desired, so indeed some consecutive terms sum to $k$. If $k < 50$, then we can create the pairs\[(1, 101 - k), (2, 102 - k), \ldots , (k, 100).\]Since $k < 50$ there are $<50$ such pairs and we similarly assign the $51$ partial sums to their values in the above pairs. Again by Pigeonhole some pair $(j, j + (100 - k))$ receives two partial sums say $s_{\ell}$ and $s_m$ with $\ell < m$ so thus\[s_m - s_{\ell} = a_{\ell + 1} + \ldots + a_m = (j + (100 - k)) - j = 100 - k\]so some consecutive terms sum to $100 - k$. In either case, over all $k$, some consecutive terms sum to either $k$ or $100 - k$, as desired. $\blacksquare$