A B. 5196. feladat (2021. október)

B. 5196. Legyen \(\displaystyle p(x)=2x+1\). Az \(\displaystyle A\) az \(\displaystyle S=\{1,2,\dots,2021\}\) halmaz olyan részhalmaza, mely minden \(\displaystyle n\)-re az \(\displaystyle n\), \(\displaystyle p(n)\), \(\displaystyle p\big(p(n)\big)\) számok közül legfeljebb egyet tartalmaz, de újabb \(\displaystyle S\)-beli elem hozzávétele esetén már nem teljesül ez a feltétel. Hány elemű lehet az \(\displaystyle A\) halmaz?

(6 pont)

A beküldési határidő 2021. november 10-én LEJÁRT.

Megoldás. Először megvizsgáljuk, hogyan néznek ki az olyan \(\displaystyle A\) halmazok, amelyekre a megadott feltétel teljesül. Az

\(\displaystyle n,\ p(n)=2n+1,\ p(p(n))=4n+3\)

sorozat mindegyik tagjához 1-et adva az

\(\displaystyle n+1,\ 2n+2,\ 4n+4\)

2 kvóciensű mértani sorozatot kapjuk. Ha \(\displaystyle A\subseteq S\), akkor legyen \(\displaystyle A'\subseteq S':=\{2,3,\dots,2022\}\) az a halmaz, melyet úgy kapunk, hogy \(\displaystyle A\) minden elemét 1-gyel nagyobbra cseréljük. Az \(\displaystyle A\subseteq S\) pontosan akkor (nem) tartalmaz egyik \(\displaystyle n,p(n),p(p(n))\) alakú hármasból sem legalább két elemet, ha \(\displaystyle A'\subseteq S'\) nem tartalmaz sem két olyan elemet, melyek hányadosa 2, sem két olyat, melyek hányadosa 4. Az ilyen tulajdonságú \(\displaystyle A'\) halmazokat fogjuk megkeresni.

Az \(\displaystyle S'\) halmaz felbontható 2 kvóciensű mértani sorozatok diszjunkt uniójára úgy, hogy két elem akkor tartozik ugyanahhoz a sorozathoz, ha hányadosuk 2-hatvány. Ezek a sorozatok:

\(\displaystyle 2,4,8,\dots,1024,\)

\(\displaystyle 3,6,12,\dots\)

\(\displaystyle 5,10,20,\dots\)

\(\displaystyle \vdots\)

Összesen 1011 mértani sorozatról van szó, a legkisebb elem pedig a 2 vagy egy 3 és 2021 közé eső páratlan szám.

Egy \(\displaystyle A'\) halmaz pontosan akkor nem tartalmaz, sem 2, sem 4 hányadosú elemeket, ha az összes ilyen sorozatra teljesül, hogy sem szomszédos, sem másodszomszédos elemek nem kerülnek kiválasztásra. Ezt a tulajdonságot megtartva \(\displaystyle A'\) akkor nem bővíthető, ha egyik mértani sorozatból sem vehető hozzá újabb elem a tulajdonság megtartásával. Tekintsük az egyik mértani sorozatot, amit (oszthatósági) láncnak is fogunk nevezni a megoldás során:

\(\displaystyle a,2a,4a,\dots,2^k a.\)

Ennek hosszára \(\displaystyle 1\leq k+1\leq 10\) teljesül, most megvizsgáljuk milyen hosszúságú láncból hány van, illetve hogy egy ilyen sorozatnak hány tagja választható ki úgy, hogy a feltétel teljesüljön, de tovább már ne legyen bővíthető.

Egy lánc hossza pontosan akkor \(\displaystyle k+1\), ha az \(\displaystyle a\) kezdőelemére (ami vagy a 2 vagy egy 3 és 2021 közötti páratlan szám) \(\displaystyle 2^ka\leq 2022<2^{k+1}a\) teljesül. Ezek alapján a különböző hosszúságú láncok száma már könnyen meghatározható:

Ha az elemek száma egy, kettő vagy három, akkor pontosan egy elemet kell kiválasztani, ugyanis bármely 2 elem kiválasztása esetén sérülne a feltétel, ha viszont egyetlen elemet sem választanánk ki, akkor bővíthető lenne újabb elemmel.

Ha az elemek száma négy vagy öt, akkor az első három és az utolsó három elem közül is pontosan egyet kell választanunk, hiszen ha például az első háromból kettőt is választanánk, sérülne a feltétel, ha egyet sem, akkor a legelső elem hozzávehető lenne a halmazhoz. Így egy vagy két elemű lehet egy maximális (azaz nem bővíthető) halmaz, mindkét eset valóban lehetséges is, az alábbi példák alapján:

\(\displaystyle X,O,X,X\quad \text{vagy} \quad O,X,X,O,\)

\(\displaystyle X,X,O,X,X,\quad \text{vagy} \quad O,X,X,O,X,\)

ahol \(\displaystyle X\) jelöli, ha egy elem nincs kiválasztva, és \(\displaystyle O\), ha igen.

Ha az elemek száma legalább hat, akkor továbbra is teljesül, hogy az első három és az utolsó három elem közül is pontosan egyet kell választani, vagyis a kiválasztott elemek száma legalább kettő. Mivel három szomszédos elem közül legfeljebb egy elem választható, ezért kapjuk, hogy \(\displaystyle 6,7,8,9,10\) hosszú lánc elemei közül rendre legfeljebb \(\displaystyle 2,3,3,3,4\) elem választható. Az alábbi példák mutatják, hogy minden megmaradt lehetőség valóban meg is valósítható:

\(\displaystyle O,X,X,O,X,X,\)

\(\displaystyle X,X,O,X,X,O,X \quad \text{vagy} \quad O,X,X,O,X,X,O,\)

\(\displaystyle X,X,O,X,X,O,X,X \quad \text{vagy} \quad O,X,X,O,X,X,O,X,\)

\(\displaystyle X,X,O,X,X,X,O,X,X \quad \text{vagy} \quad O,X,X,O,X,X,O,X,X,\)

\(\displaystyle X,X,O,X,X,X,X,O,X,X \quad \text{vagy} \quad O,X,X,O,X,X,X,O,X,X, \quad \text{vagy} \quad O,X,X,O,X,X,O,X,X,O.\)

Meghatároztuk, hogy milyen hosszú mértani sorozatból hány elem választható ki, mindegyik esetben azt kaptuk, hogy a legkisebb és a legnagyobb méret között minden lehetőség előfordulhat. Az eredményt az alábbi táblázatban foglaljuk össze:

A különböző hosszúságú láncok számát már korábban meghatároztuk, ezek alapján egy megfelelő halmaz mérete legalább

\(\displaystyle 505\cdot 1 + 253\cdot 1+127\cdot 1+63\cdot 1+31\cdot 1+16\cdot 2+8\cdot 2+4\cdot 2+2\cdot 2+2\cdot 2=1043\)

és legfeljebb

\(\displaystyle 505\cdot 1 + 253\cdot 1+127\cdot 1+63\cdot 2+31\cdot 2+16\cdot 2+8\cdot 3+4\cdot 3+2\cdot 3+2\cdot 4=1155.\)

Mivel minden lánc esetében a legkisebb és legnagyobb érték között minden előfordulhat, ezért az összesen kiválasztott számok száma is bármi lehet 1043 és 1155 között.

Tehát az \(\displaystyle A\) halmaz elemszáma 1043 és 1155 közötti (egész) szám lehet.

Statisztika:

72 dolgozat érkezett.
6 pontot kapott:	Bálint Béla, Baski Bence, Bényei Borisz, Berkó Sebestyén , Chrobák Gergő, Dienes Ervin Fotisz, Duchon Márton, Farkas 512 Izabella, Fazokán Marcell, Fülöp Csilla, Jánosik Máté, Juhász-Molnár Erik, Kalocsai Zoltán, Kercsó-Molnár Anita, Lovas Márton, Molnár István Ádám, Németh Márton, Nyárfádi Patrik, Simon László Bence, Somogyi Dalma, Szanyi Attila, Varga Boldizsár.
5 pontot kapott:	Bencsik Dávid, Csonka Illés, Erdélyi Kata, Fekete Richárd, Koleszár Domonkos, László Anna, Moni Botond, Móricz Benjámin, Nádor Benedek, Nagy 551 Levente, Páhán Anita Dalma, Rareș Polenciuc, Sági Mihály, Sándor Péter, Tichy Márk, Tóth 057 Bálint, Zömbik Barnabás.
4 pontot kapott:	7 versenyző.
3 pontot kapott:	8 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	6 versenyző.
0 pontot kapott:	5 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2021. októberi matematika feladatai