Problem B. 5218. (January 2022)

B. 5218. What is the largest number of elements that can be selected out of the first \(\displaystyle 2022\) positive integers such that the difference of any two selected numbers is not a prime?

(5 pont)

Deadline expired on February 10, 2022.

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

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

Statistics:

88 students sent a solution.
5 points:	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 points:	11 students.
3 points:	8 students.
2 points:	10 students.
1 point:	12 students.
0 point:	2 students.

Problems in Mathematics of KöMaL, January 2022