Kavics Kupa 2013 7. feladat
(Feladat azonosítója: kk_2013_07f )
Témakör: *Halmazelmélet (logika)

Legfeljebb hány eleme lehet egy egész számokból álló  $M$  halmaznak, ha  $M$  egyik eleme sem osztható 7-tel, de bármely 4 eleme közt van néhány, melyeknek összege osztható 7-tel?



 

Végeredmény: 8

 

Kézzel ellenőrizhető, hogy ha az  $\{1,2,3,4,5,6\}$  redukált maradékrendszerben két ellentett elemet, mondjuk az  $ 1$  -et és a  $ 6$  -ot megduplázzuk:  $\{1,1,2,3,4,5,6,6\}$  , akkor jó  $ 8$  elemű listát kapunk. (Itt és a továbbiakban ,,jó'' azt jelenti, hogy bármely négy elem között vannak olyanok, amelyek összege osztható  $ 7$  -tel.)
Tegyük fel ezek után, hogy létezik nem nulla maradékoknak egy  $ 9$  elemű jó listája. Ebben minden maradék legfeljebb  $ 3$  -szor fordul elő. (  $ix\equiv 0 \ (mod \ 7)$  és  $i\leq 4 \rightarrow x\equiv 0 \ (mod\ 7)$  .)
Ha van olyan  $x$  maradék, amelyik pontosan háromszor fordul elő, akkor a lista minden további  $y$  maradékára az  $x+y, 2x+y, 3x+y$  összegek között van  $ 7$  -tel osztható. A lista további maradékai (hat darab) tehát legfeljebb háromfélék lehetnek. Az  $x$  -en kívül tehát legalább két további maradék fordul elő egynél többször.
Lényegében ugyanez a helyzet, ha egyetlen maradék sem fordul elő kettőnél többször: ekkor is van három olyan maradék,  $x,y$  és  $z$  , amelyek legalább kétszer fordulnak elő a listában. Eddig volt a tilitoli, jön a végjáték: ehhez kell a lista  $\{x,x,y,y,z,z\}$  része.
Nézzünk két párt:  $\{x,x,y,y\}$  . Ebben a négyesben három összegnek van esélye, hogy osztható legyen  $ 7$  -tel:  $x+y, 2x+y$  és  $x+2y$  . Ezek szorzata tehát osztható  $ 7$  -tel! A misztikus szorzat pedig:

$ (x+y)(2x+y)(x+2y)=2(x^3+y^3)+( 1+2+4)(x^2y+xy^2). $

Ebben az  $\{x,x,y,y\}$  négyesben tehát  $ 7\mid x^3+y^3$  . A másik kettőben ugyanígy  $ 7\mid y^3+z^3$  és  $ 7\mid z^3+x^3$  , vagyis mindhárom maradék  $ 0$  . Hát ez ellentmondás.