Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 5168. feladat (2021. április)

B. 5168. Felírjuk 1-től 100-ig az egész számokat egy-egy cédulára. A száz darab cédula közül kiválasztunk 16 darabot. Található-e biztosan négy olyan cédula a kiválasztottak között, hogy közülük kettőn-kettőn álló számok összege megegyezik?

(6 pont)

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


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


Statisztika:

A B. 5168. feladat értékelése még nem fejeződött be.


A KöMaL 2021. áprilisi matematika feladatai