cefer wrote: Let $n$ be a positive integer. Let $P_n=\{2^n,2^{n-1}\cdot 3, 2^{n-2}\cdot 3^2, \dots, 3^n \}.$ For each subset $X$ of $P_n$, we write $S_X$ for the sum of all elements of $X$, with the convention that $S_{\emptyset}=0$ where $\emptyset$ is the empty set. Suppose that $y$ is a real number with $0 \leq y \leq 3^{n+1}-2^{n+1}.$ Prove that there is a subset $Y$ of $P_n$ such that $0 \leq y-S_Y < 2^n$ Let $S_n$ be sum of all elements of $P_n$. Note that $S_n=3^{n+1}-2^{n+1}$ and $S_{n+1}=3S_{n}+2^{n+1}$. We will use induction on $n$. Case when $n=1$ is trivial. Suppose that statement is true for some $n$ ie: $\forall y\in\mathbb{R}$ and $0<y<S_{n}$ we can find $S_y$ such that $0<y-S_y<2^n$(*). Now consider following cases: 1. case: $0< x< 2S_n+2^{n+1}$ 1.1. If $x<2S_n$ then multiply (*) by two to get $0<\underbrace{2y}_{x}-\underbrace{2S_y}_{S_x}<2^{n+1}$. 1.2. If $x=2S_n+x_1$ then $0<\underbrace{2S_n+x_1}_{x}-\underbrace{2S_n}_{S_x}<2^{n+1}$ because $0<x_1<2^{n+1}$. 2. case: $2S_n+2^{n+1}\leq x\leq 3S_n$. Note that $3S_n+2^{n+1}-S_y=S_{n+1}-S_y=S_x$, so: \[0<\underbrace{2S_n+2^{n+1}+x_1}_{x}-\underbrace{(3S_n+2^{n+1}-S_y)}_{S_x}<2^{n+1}\] \[\Longleftrightarrow 0<\underbrace{(S_n+2^{n+1}-x_1)}_{y}-S_y<2^{n+1}\] But $2S_n>S_n+2^{n+1}-x_1>0$, so we can apply case 1.1. to get the result. 3. case: $3S_n< x < S_{n+1}$ \[0<\underbrace{3S_n+x_1}_{x}-\underbrace{3S_n}_{S_x}<2^{n+1}\Longleftrightarrow 0< x_1<2^{n+1}\] But this is true because $S_{n+1}-3S_n=2^{n+1}$. Now it enough to check cases when $y=0$ or $y=S_n$ but that is obvious.

dr_Civot wrote: 2. case: $2S_n+2^{n+1}\leq x\leq 3S_n$. Note that $3S_n+2^{n+1}-S_y=S_{n+1}-S_y=S_x$, so: \[0<\underbrace{2S_n+2^{n+1}+x_1}_{x}-\underbrace{(3S_n+2^{n+1}-S_y)}_{S_x}<2^{n+1}\] \[\Longleftrightarrow 0<\underbrace{(S_n+2^{n+1}-x_1)}_{y}-S_y<2^{n+1}\] Can you explain this more clearly please? sorry , I really don't understand about this part, cause the sign was change there. THX

matrix41 wrote: dr_Civot wrote: 2. case: $2S_n+2^{n+1}\leq x\leq 3S_n$. Note that $3S_n+2^{n+1}-S_y=S_{n+1}-S_y=S_x$, so: \[0<\underbrace{2S_n+2^{n+1}+x_1}_{x}-\underbrace{(3S_n+2^{n+1}-S_y)}_{S_x}<2^{n+1}\] \[\Longleftrightarrow 0<\underbrace{(S_n+2^{n+1}-x_1)}_{y}-S_y<2^{n+1}\] Can you explain this more clearly please? sorry , I really don't understand about this part, cause the sign was change there. THX First of all note that: \[\underbrace{2S_n+2^{n+1}+x_1}_{x}-\underbrace{(3S_n+2^{n+1}-S_y)}_{S_x}=S_y+x_1-S_n\] If we look at the left inequality we'll get: \[0<S_y+x_1-S_n\Longleftrightarrow (S_n-x_1)-S_y<0\] If we add $2^{n+1}$ on both sides in above inequality we'll get: \[(S_n-x_1+2^{n+1})-S_y<2^{n+1} (*)\] Now if we look at the right inequality we'll get: \[S_y+x_1-S_n<2^{n+1}\Longleftrightarrow (S_n-x_1+2^{n+1})-S_y>0(**)\] $(*),(**)\Longrightarrow 0<\underbrace{(S_n+2^{n+1}-x_1)}_{y}-S_y<2^{n+1}$ Is this clear enough?

Notice that $3^{n+1}-2^{n+1} = S_{P_n}$. It is easily seen it is enough to prove that for any subset $\emptyset \subsetneq X \subseteq P_n$ there exists a subset $\emptyset \subseteq X'\subsetneq P_n$ such that $0 < S_{X} - S_{X'} \leq 2^n$, which reads as claiming the gaps between consecutive values of $S_X$ for $\emptyset \subseteq X \subseteq P_{n}$ are at most $2^n$. The proof goes by induction on $n$, the case $n=1$, where $P_1 = \{2,3\}$ and the values of $S_X$ for $\emptyset \subseteq X \subseteq P_1$ are $\{0,2,3,5\}$, being trivial. For $n>1$ and $\emptyset \subsetneq X \subseteq P_n$, if $3^n \not \in X$ then $\emptyset \subsetneq \dfrac {1} {2} X = Y \subseteq P_{n-1}$, and we can take $X'= 2Y'$, where $0 < S_{Y} - S_{Y'} \leq 2^{n-1}$ by the induction hypothesis. If $3^n \in X$ then if $\emptyset \subsetneq \dfrac {1} {2} \left (X\setminus \{3^n\} \right ) = Y \subseteq P_{n-1}$, we can proceed as above and take $X'= 2Y' \cup \{3^n\}$, where $0 < S_{Y} - S_{Y'} \leq 2^{n-1}$ by the induction hypothesis. Finally, if $X = \{3^n\}$, then notice that $3^n < S_{P_n} - 3^n = 2S_{P_{n-1}} = S_{2P_{n-1}} = 2(3^n - 2^n)$, since equivalent to $3^n > 2^{n+1}$, true for $n\geq 2$. But by the induction hypothesis, the gaps between consecutive values of $S_Y$ for $\emptyset \subseteq Y \subseteq 2P_{n-1}$ are at most $2^n$, thus there will exist $\emptyset \subseteq X' \subsetneq 2P_{n-1} = P_n \setminus \{3^n\}$ such that $0 < S_{X} - S_{X'} \leq 2^n$. This proof is related in many ways to Official Solution 2. It is noteworthy that Official Solution 1 offers an algorithmic, constructive way to build a set $Y$ associated to $y$.

dr_Civot wrote: First of all note that: \[\underbrace{2S_n+2^{n+1}+x_1}_{x}-\underbrace{(3S_n+2^{n+1}-S_y)}_{S_x}=S_y+x_1-S_n\] If we look at the left inequality we'll get: \[0<S_y+x_1-S_n\Longleftrightarrow (S_n-x_1)-S_y<0\] If we add $2^{n+1}$ on both sides in above inequality we'll get: \[(S_n-x_1+2^{n+1})-S_y<2^{n+1} (*)\] Now if we look at the right inequality we'll get: \[S_y+x_1-S_n<2^{n+1}\Longleftrightarrow (S_n-x_1+2^{n+1})-S_y>0(**)\] $(*),(**)\Longrightarrow 0<\underbrace{(S_n+2^{n+1}-x_1)}_{y}-S_y<2^{n+1}$ Is this clear enough? Yes, crystal clear. and thanks By the way, my solution is almost the same with yours, but for the first case we use $0<3y-3S_Y<2^n,3 \iff 0<(3y-2^n)-3S_Y<2^{n+1}$ take $x$ as $3y-2^n$ and this solve for $x\le 3S_n-2^n$ :p Then continue for $3S_n-2^n\le x<3S_n$ with $S_X=3S_n-2^n=3S_n-3.2^n+2^{n+1}$ which is a subset of $P_{n+1}$ and for the remaining, is the same as what you write for your solution

A very quick solution: For any $x>0$, let $r(x)$ be the proper base-$\frac{3}{2}$ representation of $\frac{x}{2^n}$, that is, the base $\frac{3}{2}$ representation with all digits 0 or 1, with the maximal value when interpreted in base 2 (i.e. digits are placed greedily with preference to higher place values). Thus the ordering of $r(x),r(y)$ matches the ordering of $x,y$. By construction, the number of digits before the decimal point in $r(x)$ is $\lfloor \log_{\frac{3}{2}} \frac{x}{2^n} \rfloor + 1$ for $x\geq 1$. Consider a (greedily constructed) proper base-$\frac{3}{2}$ representation $x$ of a positive real number. Notice that if $x$ has $k > 0$ digits before the decimal point, $x<(\frac{3}{2})^k$ so removing the leftmost digit leaves $x-(\frac{3}{2})^{k-1} < \frac{3}{4}(\frac{3}{2})^{k-2} < (\frac{3}{2})^{k-1}$. Since the remaining representation is then (recursively) greedily constructed again, this means that for any digit $d$ in $x$, the value of the number formed after removing $d$ and all digits to the left of $d$ is less than the place value of d. In particular, the "fractional part" (part after the decimal point) of any proper base-$\frac{3}{2}$ representation is less than 1. Notice that $r(2^{n-k} 3^k) = 1\underbrace{0\cdots 0}_{k\text{ zeros}}$. Furthermore, since $0\leq y \leq 3^{n+1} - 2^{n+1} = S_{P_n}$, $0 \leq r(y) \leq r(S_{P_n}) = \underbrace{1\cdots 1}_{n+1\text{ ones}}$. So we construct the subset $Y$ as follows: For each $k$, include $2^{n-k}3^k$ if and only if the $k+1$th digit before the decimal point in $r(y)$ is $1$. Then the "integer part" of $r(S_Y)$ (part before the decimal point) matches that of r(y), since each has $1$s at exactly the same places. In particular, since the fractional part of $r(S_Y)$ is zero, $0\leq r(y)-r(S_Y) < 1$, so $0 \leq y - S_Y < 2^n$ as desired.

My solution. At first,observe that $2^n< 3\cdot 2^{n-1}<\ldots <3^n$. $P_n$ has $n+1$ elements,therefore,it has $2^{n+1}$ subsets.Let $X_1,X_2,\ldots,X_{2^{n+1}}$ be these subsets,and $0=S_{X_1}\leq S_{X_2}\leq \ldots S_{X_{2^{n+1}}}=3^{n+1}-2^{n+1}$ be their sums. Lemma:$S_{X_{i}}-S_{X_{i-1}}\leq 2^n \ \forall i\in \{2,\ldots,2^{n+1}\}$. Proof:We will use strong induction. For $i=2,i=3$ the result is obviously true.Suppose that it is true for all $i\in \{1,\ldots,k\}$ for some $k\in \{3,\ldots ,2^{n+1}\}$. Our target is to show that $S_{X_{k+1}}-S_{X_k}\leq 2^n$.Let $3^{j}2^{n-j}$ be the smallest element of $P_n$ that doesn't belong to $X_k$. $\bullet$ If $j=0$ then for the subset $X_k'=X_k+\{2^n\}$ of $P_n$ we have $S_{X_k'}=S_{X_k}+2^n$ and $S_{X_k'}\geq S_{X_{k+1}}$ whence we get the desired result. $\bullet$ If $j=1$ then $2^n$ belongs to $X_k$.For the subset $X_k''=X_k-\{2^n\}+\{3\cdot 2^{n-1}\}$ we have $S_{X_k''}\geq S_{X_{k+1}}$ and $S_{X_k''}=S_{X_k}+2^{n-1}$ whence we get the desired result. $\bullet$ Suppose that $j\geq 2$.Then $X_k$ contains $2^n,\ldots,3^{j-1}2^{n-j+1}$ thus $S_{X_k}\geq \sum_{i=0}^{j-1}2^{n-i}3^{i}$. Observe that $\sum_{i=0}^{j-1}2^{n-i}3^{i}>3^{j}2^{n-j} \ \forall j\geq 2$ (use induction for a strict proof). Hence $S_{X_k}>3^{j}2^{n-j} \ (1)$Suppose that $\{3^{j}2^{n-j}\}=X_{l}$.From $(1)$ we obtain that $l<k$. Thus,from the strong induction hypothesis,we obtain $S_{X_l}-S_{X_{l-1}}\leq 2^{n}$. Also,it is obvious that $X_{l-1}$ contains elements that are all smaller than $3^{j}2^{n-j}$ thus,they all belong to $X_k$. Hence,for the set $X_k'''=X_k-X_{l-1}+X_{l}$ we have $S_{X_k'''}=S_{X_k}+S_{X_l}-S_{X_{l-1}}\leq S_{X_k}+2^n$ and $S_{X_{k+1}}<S_{X_k'''}$ whence we get the desired result and the lemma has been proved. Now take a random $y\in [0,3^{n+1}-2^{n+1}]$.If $y=0$ or $y=3^{n+1}-2^{n+1}$ then our result is obviously true. Otherwise,there exists $p\in \{1,2,\ldots 2^{n+1}-1\}$ such that $S_{X_p}\leq y>S_{X_{p+1}}$. From the lemma we get $0\leq y-S_{X_p}<2^n$ and we are done.

We prove the following claim, which implies the problem statement by scaling. Claim: Let $Q_n = \{1, \left(\tfrac{3}{2}\right), \left(\tfrac{3}{2}\right)^2, \dots, \left(\tfrac{3}{2}\right)^n\}$. Suppose $z$ is a real number with $0 \leq z \leq 1 + \left(\tfrac{3}{2}\right) + \cdots + \left(\tfrac{3}{2}\right)^n$. There exists a subset $Z \subset Q_n$ such that $z - 1 < S_Z \leq z$. Proof: Proceed by induction. When $n = 1$, the four subset sums are $0$, $1$, $\tfrac{3}{2}$, and $\tfrac{5}{2}$. The corresponding intervals for $z$ cover $[0,\tfrac{5}{2}]$, as desired. Suppose the claim is true for $n \geq 1$. With subset sums of $Q_n \subset Q_{n+1}$ we cover $z \in [0, \tfrac{3^{n+1}-2^{n+1}}{2^n}]$. Adding $\left(\tfrac{3}{2}\right)^{n+1}$ to each subset sum covers $z \in \left[\tfrac{3^{n+1}}{2^{n+1}}, \tfrac{3^{n+2}-2^{n+2}}{2^{n+1}}\right]$. Conclude by noting that \[\frac{3^{n+1}}{2^{n+1}} \leq \frac{3^{n+1}-2^{n+1}}{2^n}\]for all $n \geq 1$. Hence for all $z \in \left[0, 1 + \left(\tfrac{3}{2}\right) + \cdots + \left(\tfrac{3}{2}\right)^{n+1}\right]$ we can find a corresponding $Z \subset Q_{n+1}$, completing the inductive step. $\square$