Balkan 2012 shortlist

Let $\alpha =3/2$ so $1+\alpha >{\alpha }^2$. Given $y$, we construct $Y$ algorithmically. Let $Y=\varnothing$ and of course $S_{\varnothing }=0$. For $i=0$ to $m$, perform the following operation: If $S_Y+2^i{3}^{m-i}\le y$, then replace $Y$ by $Y\cup \{2^i{3}^{m-i}\}$. When this process is finished, we have a subset $Y$ of $P_m$ such that $S_Y\le y$. Notice that the elements of $P_m$ are in ascending order of size as given, and may alternatively be described as $2^m,2^m\alpha ,2^m{\alpha }^2,\dots ,2^m{\alpha }^m$. If any member of this list is not in $Y$, then no two consecutive members of the list to the left of the omitted member can both be in $Y$. This is because $1+\alpha >{\alpha }^2$, and the greedy nature of the process used to construct $Y$. Therefore either $Y=P_m$, in which case $y=3^{m+1}-2^{m+1}$ and all is well, or at least one of the two leftmost elements of the list is omitted from $Y$. If $2^m$ is not omitted from $Y$, then the algorithmic process ensures that $(S_Y-2^m)+2^{m-1}3>y$, and so $y-S_Y<2^m$. On the other hand, if $2^m$ is omitted from $Y$, then $y-S_Y<2^m$.

---

Alternative solution.

Note that $3^{m+1}-2^{m+1}=(3-2)(3^m+3^{m-1}\cdot 2+\cdots +3\cdot 2^{m-1}+2^m)=S_{P_m}$. Dividing every element of $P_m$ by $2^m$ gives us the following equivalent problem: Let $m$ be a positive integer, $a=3/2$, and $Q_m=\{1,a,a^2,\dots ,a^m\}$. Show that for any real number $x$ satisfying $0\le x\le 1+a+a^2+\cdots +a^m$, there exists a subset $X$ of $Q_m$ such that $0\le x-S_X<1$. We will prove this problem by induction on $m$. When $m=1$, $S_{\varnothing }=0$, $S_{\{1\}}=1$, $S_{\{a\}}=3/2$, $S_{\{1,a\}}=5/2$. Since the difference between any two consecutive of them is at most 1, the claim is true. Suppose that the statement is true for positive integer $m$. Let $x$ be a real number with $0\le x\le 1+a+a^2+\cdots +a^{m+1}$. If $0\le x\le 1+a+a^2+\cdots +a^m$, then by the induction hypothesis there exists a subset $X$ of $Q_m\subset Q_{m+1}$ such that $0\le x-S_X<1$. If $\frac{a^{m+1}-1}{a-1}=1+a+a^2+\cdots +a^m<x$, then $x>a^{m+1}$ as $$\frac{a^{m+1}-1}{a-1}=2(a^{m+1}-1)=a^{m+1}+(a^{m+1}-2)\ge a^{m+1}+a^2-2=a^{m+1}+\frac{1}{4}.$$ Therefore $0<(x-a^{m+1})\le 1+a+a^2+\cdots +a^m$. Again by the induction hypothesis, there exists a subset $X$ of $Q_m$ satisfying $0\le (x-a^{m+1})-S_X<1$. Hence $0\le x-S_{X^{\prime }}<1$ where $X^{\prime }=X\cup \{a^{m+1}\}\subset Q_{m+1}$.