Problem B. 5168. (April 2021)

B. 5168. Each of the integers 1 to 100 is written on a piece of paper. 16 pieces of paper are selected out of the 100 pieces. Is it certain that there will always be four pieces of paper among the selected ones such that the sum of the numbers on two of them equals the sum of the numbers on the other two?

(6 pont)

Deadline expired on May 10, 2021.

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

Megoldás. Azt fogjuk bizonyítani, hogy a válasz igenlő.

Jelölje \(\displaystyle A\) a 16 kiválasztott cédulán szerepelő számot tartalmazó halmazt, és tegyük fel indirekten, hogy nem választható ki négy cédula úgy, hogy közülük kettőn-kettőn álló számok összege megegyezik.

Tekintsük az \(\displaystyle a-a'\) különbségeket, ahol \(\displaystyle a,a'\in A\) és \(\displaystyle a>a'\). Mivel \(\displaystyle A\subseteq \{1,2,\dots,100\}\), ezért \(\displaystyle 1\leq a-a'\leq 99\). Összesen \(\displaystyle \binom{16}{2}=120\) ilyen különbség képezhető, így a skatulya-elv alapján biztosan lesznek egybeesések. Tekintsünk egy ilyet: legyen \(\displaystyle a,a'\in A\) (ahol \(\displaystyle a>a'\)) és \(\displaystyle b,b'\in A\) (ahol \(\displaystyle b>b'\)) két olyan pár, melyekre \(\displaystyle a-a'=b-b'\). Világos, hogy \(\displaystyle a\ne b\), hiszen \(\displaystyle a=b\) esetén \(\displaystyle a'=b'\) is teljesülne. Ehhez hasonlóan \(\displaystyle a'\ne b'\) is teljesül. A szimmetria alapján tegyük fel például, hogy \(\displaystyle a>b\). Az egyenletet átrendezve:

\(\displaystyle a+b'=a'+b.\)

Az eddigiekből kiderült már, hogy \(\displaystyle a\) különbözik \(\displaystyle a'\) és \(\displaystyle b\) mindegyikétől, és így \(\displaystyle b'\) is különbözik \(\displaystyle a'\) és \(\displaystyle b\) mindegyikétől.

Mivel, \(\displaystyle a>b>b'\), ezért \(\displaystyle a\ne b'\). Ha \(\displaystyle b\ne a'\) is teljesülne, akkor tehát találnánk négy olyan kiválasztott cédulát, hogy kettőn-kettőn ugyanannyi az összeg. Tehát csak \(\displaystyle b=a'\) lehet, ekkor \(\displaystyle a-a'=b-b'\) azt jelenti, hogy \(\displaystyle b',b,a\) egy (szigorúan növekedő) számtani sorozat.

Így minden \(\displaystyle a-a'=b-b'\) egybeeséshez (\(\displaystyle a>b\)) tartozik egy 3 hosszú \(\displaystyle A\)-beli számtani sorozat. Ez a kapcsolat visszafelé is egyértelmű: \(\displaystyle a,a'\) a számtani sorozat két nagyobb, \(\displaystyle b,b'\) a számtani sorozat két kisebb tagja.

Az eddigiekből az is leolvasható, hogy ugyanaz a különbség legalább háromféleképpen nem állhat elő. Ha ugyanis

\(\displaystyle a-a'=b-b'=c-c'\)

teljesülne (mondjuk) \(\displaystyle a>b>c\) mellett, akkor az eddigiek alapján egyrészt \(\displaystyle b=a'\), másrészt \(\displaystyle c=a'\), ami \(\displaystyle b>c\) miatt lehetetlen.

Tehát az eddigiek alapján van 120 darab \(\displaystyle a-a'\) (\(\displaystyle a>a'\), \(\displaystyle a,a'\in A\)) különbség, amik 1 és 99 közötti értékeket vehetnek fel, hiszen \(\displaystyle A\) elemei 1 és 100 közötiek. Minden különbség legfeljebb kétszer fordulhat elő, és ha egy \(\displaystyle d\) különbség kétszer is szerepel, akkor tartozik hozzá egy \(\displaystyle A\)-beli elemekből álló, \(\displaystyle d\) differenciájú számtani sorozat: \(\displaystyle a-d,a,a+d\in A\). Rendeljük ilyenkor a kétszer is előálló \(\displaystyle d\)-hez ennek a számtani sorozatnak a középső elemét. Ugyanaz az elem nem tartozhat két különböző (kétszer is előálló) differenciához, különben \(\displaystyle d\ne d'\)-re \(\displaystyle a-d,a,a+d\in A\) és \(\displaystyle a-d',a,a+d'\in A\) esetén

\(\displaystyle (a-d)+(a+d)=(a-d')+(a+d')\)

megfelelő előállítás lenne.

A három hosszú számtani sorozatok középső eleme nem lehet a 16 szám közül se a legkisebb, se a legnagyobb, vagyis csak 14-féle lehet. Ez egyben azt is jelenti, hogy legfeljebb 14-féle differencia állhat elő kétféleképpen is. Vagyis a különböző különbségek száma legalább \(\displaystyle 120-14=106\), ami ellentmond annak, hogy értékük csak 1 és 99 közötti lehet.

Ez az ellentmondás azt jelenti, hogy 16 kiválasztott cédula között mindig lesz négy, hogy közülük kettőn-kettőn álló számok összege megegyezik.

Megjegyzések. 1. Ha az \(\displaystyle a-a'\) különbségek helyett az \(\displaystyle a+a'\) összegeket vizsgáljuk, akkor világos, hogy bármely egybeesés esetén készen vagyunk. Azonban az összeg értéke 3 és 199 közötti lehet, ami 197 lehetőség, viszont csak 120-féle összeg van. További megfontolások nélkül tehát még nem következik közvetlenül a skatulya-elvből, hogy biztosan van egybeesés.

2. Az olyan \(\displaystyle A\) halmazokat, melyeken belül az \(\displaystyle a+b=c+d\) egyenletnek nincs nemtriviális, vagyis olyan megoldása, melyre \(\displaystyle \{a,b\}\ne \{c,d\}\) (additív) Sidon-halmazoknak nevezzük. A feladat megoldásából következik, hogy az \(\displaystyle 1,2,\dots,100\) legnagyobb Sidon részhalmazának mérete legfeljebb 15. Azonban a feladat megoldásához ennél erősebb állítást kellett igazolnunk, hiszen olyan négyest kellett találni, melynek tagjai mind különbözők, az \(\displaystyle a+b=c+c\) típusú megoldások mutatnák, hogy \(\displaystyle A\) nem Sidon-halmaz, de a feladat megoldásához ilyen megoldás létezésének igazolása még nem lenne elegendő.

Statistics:

53 students sent a solution.
6 points:	Bán-Szabó Áron, Baski Bence, Ben Gillott, Bencsik Ádám, Bencsik Dávid, Bognár 171 András Károly, Csilling Dániel, Csizmadia Miklós, Diaconescu Tashi, Duchon Márton, Fekete Richárd, Fülöp Csilla, Hajdú Bálint, Hegedűs Dániel, Jánosik Máté, Kalocsai Zoltán, Koleszár Domonkos, Kovács 129 Tamás, Kökényesi Márk Péter, Lovas Márton, Mezey Dorottya, Molnár-Szabó Vilmos, Móricz Benjámin, Nádor Artúr, Nádor Benedek, Nagy 551 Levente, Seres-Szabó Márton, Simon László Bence, Sztranyák Gabriella, Terjék András József, Tóth 057 Bálint, Török Ágoston, Varga Boldizsár, Viczián András, Wiener Anna.
5 points:	Horváth 530 Mihály, Szakács Ábel.
4 points:	2 students.
2 points:	3 students.
1 point:	6 students.
0 point:	5 students.

Problems in Mathematics of KöMaL, April 2021