BMO 2012, problema 3

[Laurențiu Ploscaru]

Fie $n$ un număr natural nenul și $P_n=\{2^n,2^{n-1}\cdot 3, 2^{n-2}\cdot 3^2, \dots, 3^n \}$.
Pentru fiecare submulțime $X$ a lui $P_n$, notăm cu $S_X$ suma tuturor elementelor lui $X$, cu convenția $S_{\emptyset}=0$.
Alegând un număr real $y$ cu proprietatea $0 \leq y \leq 3^{n+1}-2^{n+1}$, arătați că există o submulțime $Y$ a lui $P_n$ a.î. $0 \leq y-S_Y < 2^n$.

[Laurențiu Ploscaru]

Voi rezolva problema prin inducţie după $n$. Pasul de verificare este trivial. Trecem la pasul de indcuţie.

Cazul 1: $0\le y\le 2(3^n-2^n)$. Pentru orice $t$ natural cu $0\le t\le 3^n-2^n$ există $T\in P_{n-1}$ cu $0\le t-S_T<2^n-1$.
Considerăm mulţimea $V=\{2k\mid k\in T\}$. Evident $V\in P_n$ şi $S_V=2S_T$. Avem relaţia $0\le 2t-S_V<2^n$.
Prin urmare pentru orice $y$ par existenţa unei mulţimi $V$ e demonstrată. Însă cum $S_V$ e par, mulţimea $V$ e bună şi pentru $y+1$.

Cazul 2: $2(3^n-2^n)<y\le 3^{n+1}-2^{n+1}$. Pentru început Îl băgăm în $Y$ pe $3^n$ şi considerăm $X=Y-\{3^n\}$.
Rămâne de găsit o mulţime $X\in P_n-\{3^n\}$ cu $0\le p-S_X<2^n$ unde $p=y-3^n$. Avem $0\le 3^n-2^{n+1}<p\le 2(3^n-2^n)$.
Pentru orice $t$ natural cu $0\le t\le 3^n-2^n$ există $T\in P_{n-1}$ cu $0\le t-S_T<2^n-1$.
Construim $X=\{2k\mid k\in T\}$. Evident $X\in P_n-\{3^n\}$ şi $S_X=2S_T$. Avem relaţia $0\le 2t-S_X<2^n$.
Prin urmare pentru orice $p$ par existenţa unei mulţimi $X$ e demonstrată. Însă cum $S_X$ e par, mulţimea $X$ e bună şi pentru $p+1$.