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