Problem B. 5088. (March 2020)

B. 5088. With respect to a given set \(\displaystyle G\) of numbers, the positive integer \(\displaystyle k>1\) is called interesting if there exist \(\displaystyle k\) distinct elements in set \(\displaystyle G\) such that the arithmetic mean of these elements also belongs to set \(\displaystyle G\).

Let \(\displaystyle H=\{1;3;4;9;10;\ldots\}\) be the set of those numbers that can be represented as a sum of some different powers of 3.

\(\displaystyle a)\) What numbers \(\displaystyle k>1\) are interesting with respect to the set \(\displaystyle H\)?

\(\displaystyle b)\) Let \(\displaystyle c \notin H\) be an arbitrary positive integer. Prove that every number \(\displaystyle k>1\) is interesting with respect to the set \(\displaystyle H'=H \cup \{c\}\).

(5 pont)

Deadline expired on April 14, 2020.

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

Megoldás. a) Megmutatjuk, hogy tetszőleges \(\displaystyle k>2\) érdekes, de \(\displaystyle k=2\) nem.
Legyen \(\displaystyle 2<k\) hármas számrendszerbeli alakja (végig hármas számrendszerben fogunk dolgozni): \(\displaystyle k=\overline{b_1b_2...b_n}\). Ekkor ha \(\displaystyle 3d=\overbrace{100...0100...0....100...0}^{k \text{ db \(\displaystyle n\) hosszú }10...0}\) alakú szám (és így \(\displaystyle d \in H\)), akkor megmutatjuk, hogy \(\displaystyle d\) olyan szám, amelynek \(\displaystyle k\)-szorosa előáll \(\displaystyle k\) darab különböző \(\displaystyle H\)-beli \(\displaystyle a_i\) szám összegeként, és így \(\displaystyle k\) érdekes.
Első eset (az első jegy alapján): Ha \(\displaystyle b_1=1\), akkor a \(\displaystyle kd=b_1b_2...b_nb_1b_2...b_n...b_1b_2...b_n=1b_2b_3...b_n1b_2...b_n1b_2b_3...b_n\) számot a következőképpen bonthatjuk ilyen \(\displaystyle a_1,a_2,...,a_k \in H\) számok összegére:
Legyenek: \(\displaystyle a'_1=3^{1\cdot n - 1};a'_2=3^{2\cdot n - 1};...;a'_k=3^{k\cdot n - 1}\).
Innen a (vessző nélküli) \(\displaystyle a_i\)-ket úgy konstruáljuk meg, hogy \(\displaystyle a_i=a'_i\) legyen, továbbá a \(\displaystyle kd\) szám ,,maradék, szét nem osztott jegyeit 1-esével'' valahogyan szétosztjuk az \(\displaystyle a_i\)-k között (ezt megtehetjük, mivel \(\displaystyle k>2\) és minden helyiértéken legfeljebb 2 db 1-est kell ,,szétosztanunk''). Mivel az \(\displaystyle a_i\) számok az \(\displaystyle l \cdot n -1\)-dik helyiértékükben biztosan különböznek, így nyilván csupa különböző \(\displaystyle H\)-beli \(\displaystyle a_i\) összegére bontottuk fel \(\displaystyle kd\)-t.
(Pl. ha \(\displaystyle b=5=12_3 \Rightarrow d=101010101_3 \Rightarrow kd=5 \cdot d = 1212121212_3 \Rightarrow a'_1=10; a'_2=1000, a'_3=100000,a'_4=10000000,a'_5=1000000000\).
És a további 2-es jegyeket szétosztva mondjuk \(\displaystyle a_5,a_4\) között: \(\displaystyle a_5=1101010101; a_4=11010101;a_3=a'_3=100000;a_2=a'_2=1000;a_1=a'_1=10\).)
Második eset: Ha pedig \(\displaystyle b_1=2\), akkor (a korábbi \(\displaystyle a'_i\)-ket felhasználva): \(\displaystyle a_1=a'_1+a'_2; a_2=a'_2+a'_3;...;a_{k-1}=a'_{k-1}+a'_k;a_k=a'_k+a'_1\), és a további jegyeket az előző esethez hasonlóan megint szétosztjuk. Ezzel ismét \(\displaystyle k\) darab csupa különböző \(\displaystyle H\)-beli \(\displaystyle a_i\) összegére bontottuk fel \(\displaystyle kd\)-t.
(Pl. ha \(\displaystyle b=7=21_3 \Rightarrow d=1010101010101_3 \Rightarrow kd=7 \cdot d= 21212121212121_3 \Rightarrow a'_1=1010; a'_2=101000, a'_3=10100000,a'_4=1010000000,a'_5=101000000000,a'_6=10100000000000, a'_7=10000000000010\).
És a további 2-es jegyeket szétosztva (mondjuk mind \(\displaystyle a_7\)-nek adva): \(\displaystyle a_7=11010101010111; a_6=a'_6;a_5=a'_5;...;a_1=a'_1=1010\).)

Továbbá nyilvánvaló, hogy \(\displaystyle k=2\) nem érdekes \(\displaystyle H\)-hoz, hiszen tetszőleges átlagos \(\displaystyle d \in H\) szám duplája csak \(\displaystyle 0\) és \(\displaystyle 2\) jegyekből áll hármas számrendszerben, viszont ez nem állhat elő csupán két darab különböző \(\displaystyle H\)-beli szám összegeként.

b) Mivel a \(\displaystyle k>2\) számok már \(\displaystyle H\)-hoz érdekesek voltak, így \(\displaystyle H'\)-höz is érdekesek, csak \(\displaystyle k=2\) a kérdés.
\(\displaystyle c\) hármas számrendszerbeli alakjában biztosan van 2-es jegy (különben \(\displaystyle c \in H\) lenne). Legyen az utolsó 2-es a \(\displaystyle 3^n\) helyiértéken. Ekkor a \(\displaystyle 2c\) szám 3-as számrendszerbeli alakjában \(\displaystyle 2c=c_m c_{m-1}...1...c_1\) alakú (de a jelzett \(\displaystyle 3^{n+1}\) helyiértéken álló 1-es előtt biztosan van legalább egy további nem nulla jegy). Legyen ekkor \(\displaystyle a'_1=0;a'_2=3^{n+1}\) és innen az \(\displaystyle a_1,a_2\) számokat a fentiekhez hasonlóan kapjuk.
– Ha a \(\displaystyle 2c=c_m c_{m-1}...1...c_1\) szám \(\displaystyle l \neq (n+1)\)-edik \(\displaystyle c_l\) jegyére \(\displaystyle c_l=1\), akkor az \(\displaystyle a_1\) szám \(\displaystyle l\)-edik jegye \(\displaystyle 1\), míg \(\displaystyle a_2\) \(\displaystyle l\)-edik jegye \(\displaystyle 0\).
– Ha a \(\displaystyle 2c\) szám \(\displaystyle l \neq (n+1)\)-edik jegye \(\displaystyle c_l=2\), akkor az \(\displaystyle a_1\) szám \(\displaystyle l\)-edik jegye \(\displaystyle 1\), és \(\displaystyle a_2\) \(\displaystyle l\)-edik jegye is \(\displaystyle 1\).
– Míg ha a \(\displaystyle 2c\) szám \(\displaystyle l \neq (n+1)\)-edik jegye \(\displaystyle c_l=0\), akkor az \(\displaystyle a_1\) szám \(\displaystyle l\)-edik jegye \(\displaystyle 0\), és \(\displaystyle a_2\) \(\displaystyle l\)-edik jegye is \(\displaystyle 0\).
Ekkor \(\displaystyle a_1,a_2\) különböző számok (hiszen \(\displaystyle (n+1)\)-dik jegyükben mások) és elemei \(\displaystyle H\)-nak (\(\displaystyle a_1>0\) is teljesül, mert \(\displaystyle 2c\)-nek legalább két nem 0 jegye van).
Mivel ekkor \(\displaystyle c=\dfrac{a_1+a_2}{2}\) teljesül, igazoltuk, hogy \(\displaystyle k=2\) is érdekes \(\displaystyle H'\)-höz.

Statistics:

49 students sent a solution.
5 points:	Andó Viola, Bán-Szabó Áron, Baski Bence, Beinschroth Ninett, Beke Csongor, Bognár 171 András Károly, Csizmadia Miklós, Csonka Illés, Fekete Richárd, Fleiner Zsigmond, Fülöp Csilla, Füredi Erik Benjámin, Gábriel Tamás, Jánosik Áron, Jánosik Máté, Kercsó-Molnár Anita, Király Csaba Regő, Kovács 129 Tamás, Lengyel Ádám, Lovas Márton, Mácsai Dániel, Mátravölgyi Bence, Móricz Benjámin, Nádor Benedek, Németh Márton, Osztényi József, Seres-Szabó Márton, Szabó 991 Kornél, Sztranyák Gabriella, Terjék András József, Tiderenczl Dániel, Tóth 057 Bálint, Vakaris Klyvis, Varga Boldizsár, Velich Nóra, Wiener Anna.
4 points:	Feczkó Nóra, Móra Márton Barnabás, Nguyen Bich Diep.
3 points:	4 students.
2 points:	2 students.
1 point:	1 student.
0 point:	3 students.

Problems in Mathematics of KöMaL, March 2020