A B. 5218. feladat (2022. január)

B. 5218. Legfeljebb hány választható ki az első \(\displaystyle 2022\) pozitív egész szám közül úgy, hogy semelyik két kiválasztott szám különbsége ne legyen prímszám?

(5 pont)

A beküldési határidő 2022. február 10-én LEJÁRT.

Megoldás. Azt fogjuk igazolni, hogy legfeljebb 506 szám választható ki a feltételeknek megfelelően.

Először mutatunk egy konstrukciót. Ha az összes 4-gyel osztva 1 maradékot adó számot (\(\displaystyle 1,5,9,\dots, 2021\)) választjuk ki, akkor bármely két elem különbsége 4-gyel osztható, és így nem prímszám. A kiválasztott számok száma ebben az esetben \(\displaystyle 2024/4=506\).

Annak igazolásához, hogy ennél több szám nem választható ki, először megmutatjuk, hogy bármely 8 szomszédos egész szám közül legfeljebb 2-t választhatunk ki. Ehhez elég igazolni, hogy ha egy \(\displaystyle k\) számot kiválasztunk, akkor az őt követő 7 szám, vagyis \(\displaystyle k+1,k+2,\dots,k+7\) közül legfeljebb egy lehet kiválasztva. A \(\displaystyle k+2,k+3,k+5,k+7\) számok nem lehetnek kiválasztva, hiszen \(\displaystyle k\)-val vett különbségük prímszám. A \(\displaystyle k+1,k+4,k+6\) számok páronkénti különbségei pedig mind prímszámok, így közülük is csak egyetlen szám választható ki. Tehát 8 szomszédos szám közül mindig legfeljebb 2 lehet kiválasztva. Az első 2022 pozitív egész számot beoszthatjuk 252 darab 8-as és egy darab 6-os csoportba:

\(\displaystyle \{1,2,\dots,8\}, \quad \{9,10,\dots,16\},\quad \dots,\quad \{2009,2010,\dots, 2016\},\quad \{2017,2018,\dots, 2022\}.\)

Ezek mindegyikéből legfeljebb 2-2 szám választható ki, ami mindösszesen legfeljebb \(\displaystyle 253\cdot2=506\) kiválasztott számot jelent.

Ezzel igazoltuk, hogy legfeljebb 506 szám választható ki a feltételeknek megfelelően (és ennyit ki is lehet választani).

Statisztika:

88 dolgozat érkezett.
5 pontot kapott:	Bencsik Dávid, Berkó Sebestyén , Bognár 171 András Károly, Chrobák Gergő, Csonka Illés, Czanik Pál, Diaconescu Tashi, Duchon Márton, Farkas 512 Izabella, Fazokán Marcell, Fülöp Csilla, Horváth 530 Mihály, Jánosik Máté, Juhász-Molnár Erik, Kalocsai Zoltán, Kercsó-Molnár Anita, Koleszár Domonkos, Kovács Alex, Kovács Benedek Noel, Kovács Dóra, Kovács Móric, Lovas Márton, Mizik Lóránt, Mohay Lili Veronika, Molnár István Ádám, Móricz Benjámin, Nagy 429 Leila, Nagy 551 Levente, Németh Márton, Nguyen Kim Dorka, Páhán Anita Dalma, Sági Mihály, Simon László Bence, Somogyi Dalma, Szabó 810 Levente, Szakács Ábel, Szakács Domonkos, Szanyi Attila, Szemlér Bálint, Tichy Márk, Tóth 057 Bálint, Varga Boldizsár, Virág Rudolf, Wiener Anna, Zömbik Barnabás.
4 pontot kapott:	11 versenyző.
3 pontot kapott:	8 versenyző.
2 pontot kapott:	10 versenyző.
1 pontot kapott:	12 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2022. januári matematika feladatai