Let $b_0, b_1, b_2, \ldots$ be a sequence of pairwise distinct nonnegative integers such that $b_0=0$ and $b_n<2n$ for all positive integers $n$. Prove that for each nonnegative integer $m$ there exist nonnegative integers $k, \ell$ such that \begin{align*} b_k+b_{\ell}=m. \end{align*}
Problem
Source: 2019 Second Round - Poland
Tags: algebra, combinatorics
ThE-dArK-lOrD
12.07.2019 01:57
For each non-negative integer $n$ let $B_n=\{ b_i\mid 0\leqslant i\leqslant n\}$. We can show that $\{ 0,1,2,\dotsc ,2n\} \subseteq B_n+B_n$.
Tang_Tang
08.11.2022 13:13
Assume that there's some $m$ such that: $b_{k}+b_{l} \neq m \ \forall k,l \in \mathbb{N}$ Case 1: $m=2n$ for some $n \in \mathbb{N}$ Consider the numbers $b_{1},b_{2},...,b_{n}$ Since $b_{0}=0, b_{i} \geq 1 \ \forall i \geq 1$ By our assumption, $b_{k} \neq 2n-b_{l} \ \forall k,l \in \mathbb{N} $ Thus $b_{1},b_{2},...,b_{n},2n-b_{1},2n-b_{2},...,2n-b_{n}$ are $2n$ pairwise distinct positive integers. But each number is less than $2n$ which is clearly a contradiction. Case 2: $m=2n+1$ for some $n \in \mathbb{N}$ Proceeding similar as above by considering $b_{1},b_{2},...,b_{n+1},2n+1-b_{1},2n+1-b_{2},...,2n+1-b_{n+1}$ are $2n+2$ pairwise distinct positive integers where each number is less than $2n+2$. (Note that $b_{i} \neq 2n+1$ because otherwise $b_{i}+b_{0}=2n+1$) We also get a contradiction. So the assumption is wrong in both cases and we're done.