Az A. 708. feladat (2017. november)

A. 708. Legyen \(\displaystyle S\) racionális számokból álló véges halmaz. Minden \(\displaystyle k\) pozitív egészre legyen \(\displaystyle b_k=0\), ha választható \(\displaystyle k\) darab (nem feltétlenül különböző) \(\displaystyle S\)-beli szám, melyek összege \(\displaystyle 0\), és \(\displaystyle b_k=1\) egyébként. Mutassuk meg, hogy a \(\displaystyle 0{,}b_1b_2b_3\dots\) kettedestört racionális szám. Igaz marad-e az állítás, ha \(\displaystyle S\)-ről nem kötjük ki, hogy véges?

(5 pont)

A beküldési határidő 2017. december 11-én LEJÁRT.

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}\).

Statisztika:

25 dolgozat érkezett.
5 pontot kapott:	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 pontot kapott:	Daróczi Sándor.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2017. novemberi matematika feladatai