29-th Balkan Mathematical Olympiad

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$.

If $2^m$ is not omitted from $Y$, then the algorithmic process ensures that $(S_Y-2^m)+2^{m-1}\cdot 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}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, $a=\frac{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<x-S_X<1$. We will prove this problem by induction on $m$. When $m=1$, $S_1=0$, $S_{11}=1$, $S_{1a}=\frac{3}{2}$, $S_{[1,a]}=\frac{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$. 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}$.