Problem A. 708. (November 2017)

A. 708. Let \(\displaystyle S\) be a finite set of rational numbers. For each positive integer \(\displaystyle k\), let \(\displaystyle b_k=0\) if we can select \(\displaystyle k\) (not necessarily distinct) numbers in \(\displaystyle S\) whose sum is \(\displaystyle 0\), and \(\displaystyle b_k=1\) otherwise. Prove that the binary number \(\displaystyle 0.b_1b_2b_3\dots\) is a rational number. Would this statement remain true if we allowed \(\displaystyle S\) to be infinite?

(5 pont)

Deadline expired on December 11, 2017.

Sorry, the solution is available only in Hungarian. Google translation

1. megoldás. Ha \(\displaystyle b_n=1\) minden \(\displaystyle n\)-re, akkor \(\displaystyle 0.b_1b_2\dots=1\) racionális. Tegyük fel ezentúl, hogy létezik olyan \(\displaystyle n\), melyre \(\displaystyle b_n=0\).

Azt mondjuk, hogy \(\displaystyle n\) primitív, hogyha kiválasztható egy \(\displaystyle n\)-elemű számlista \(\displaystyle S\)-ből úgy, hogy összegük \(\displaystyle 0\) legyen, de a lista semely részhalmazának ne legyen \(\displaystyle 0\) az összege.

Ha \(\displaystyle N\) primitív \(\displaystyle n\)-ek összege, nyilván \(\displaystyle b_N=0\). Megfordítva, ha \(\displaystyle b_N=0\), akkor \(\displaystyle N\) felírható néhány primitív \(\displaystyle n\) összegeként. Ezt teljes indukcióval bizonyítva: ha \(\displaystyle N\) primitív, kész, ha pedig \(\displaystyle N\) nem primitív, felírható \(\displaystyle N=N_1+N_2\) alakban úgy, hogy \(\displaystyle b_{N_1}=0\) és \(\displaystyle b_{N_2}=0\), s így mivel az indukciós feltevés szerint \(\displaystyle N_1\) és \(\displaystyle N_2\) is primitív \(\displaystyle n\)-ek összege, így ez \(\displaystyle N\)-re is fennáll.

Legyen \(\displaystyle L\) a primitív \(\displaystyle n\) értékek legnagyobb közös osztója. Ekkor ha \(\displaystyle b_N=0\), akkor \(\displaystyle L|N\). Másfelől, létezik olyan primitív \(\displaystyle n_1,n_2,\dots,n_k\), melyre \(\displaystyle L=\text{lnko}(n_1,n_2,\dots,n_k)\). Ekkor ismert (lásd Frobenius-probléma), hogy \(\displaystyle L\)-nek csak véges sok többszöröse nem áll elő \(\displaystyle \alpha_1 n_1+\alpha_2 n_2+\dots+\alpha_k n_k\) alakban nemnegatív \(\displaystyle \alpha_i\) együtthatókkal. Ebből következik, hogy \(\displaystyle L\)-nek csak véges sok \(\displaystyle N\) többszörösére lesz \(\displaystyle b_N\neq 0\).

Tehát elég nagy \(\displaystyle m\) esetén \(\displaystyle b_m=0\) pontosan akkor, ha \(\displaystyle L|m\), és így \(\displaystyle b_1,b_2,\dots\) sorozat egy idő után periodikus, azaz \(\displaystyle 0.b_1b_2\dots\in\mathbb{Q}\).

2. megoldás (csak véges \(\displaystyle S\)-re). Ha \(\displaystyle S\) véges, teljes indukcióval belátható, hogy a primitív \(\displaystyle n\) értékek száma is véges (bár tetszőlegesen sok lehet). Ha a primitív \(\displaystyle n\)-ek \(\displaystyle n_1,n_2,\dots,n_k\), akkor kapjuk, hogy \(\displaystyle N>M:=\max n_j\) esetén

\(\displaystyle b_N=0 \quad \text{pontosan akkor, ha} \quad b_{N-n_j}=0\quad \text{valamely} \quad j=1,2,\dots,k\text{-ra}.\quad (*)\)

Mivel a \(\displaystyle \big(B_i=(b_{i+1},b_{i+1},\dots,b_{i+M})\big)_{i=0,1,\dots}\) sorozatnak véges sokféle tagja lehet, \(\displaystyle B_{i_0}=B_{i_0+p}\) valamely \(\displaystyle i_0\ge 0\), \(\displaystyle p>0\) esetén. \(\displaystyle (*)\)-ból következik, hogy \(\displaystyle B_{i}=B_{i+p}\) teljesül \(\displaystyle i=i_0,i_0+1,\dots\)-ra, s így a \(\displaystyle (b_i)\) sorozat periodikus.

3. megoldás (Bursics Balázs megoldása). Ha semely \(\displaystyle M\)-re sem teljesül \(\displaystyle b_M=0\), akkor \(\displaystyle 0.b_1b_2\dots=1\) racionális. Egyébként létezik olyan \(\displaystyle M\), melyre \(\displaystyle b_M=0\).

Ha \(\displaystyle b_n=0\) és \(\displaystyle b_M=0\), akkor \(\displaystyle k=0,1,\dots\)-ra \(\displaystyle b_{n+k\cdot M}=0\), hisz \(\displaystyle n+k\cdot M\) darab \(\displaystyle S\)-beli szám is kiválasztható lesz, melyek összege \(\displaystyle 0\). Tehát minden modulo \(\displaystyle M\) maradékosztályra a benne szereplő \(\displaystyle n\) indexeknél vagy mindig \(\displaystyle b_n=0\), vagy pedig véges sok kivétellel mindig \(\displaystyle b_n=1\). Ebből következik, hogy a \(\displaystyle b_1,b_2,\dots\) sorozat egy idő után \(\displaystyle M\) szerint periodikus lesz, vagyis \(\displaystyle 0.b_1b_2\dots\in\mathbb{Q}\).

Statistics:

25 students sent a solution.
5 points:	Beke Csongor, Bukva Balázs, Bursics Balázs, Egri Máté, Gáspár Attila, Győrffy Ágoston, Hanics Mihály, Imolay András, Janzer Orsolya Lili, Matolcsi Dávid, Molnár Bálint, Molnár-Sáska Zoltán, Németh 123 Balázs, Schrettner Jakab, Szabó 417 Dávid, Tóth 827 Balázs, Weisz Máté, Zólomy Kristóf.
4 points:	Daróczi Sándor.
3 points:	3 students.
2 points:	1 student.
1 point:	1 student.
0 point:	1 student.

Problems in Mathematics of KöMaL, November 2017