A H halmaz a 2011-nél nem nagyobb pozitív egész számok halmazának olyan részhalmaza, hogy tetszőleges két elemének összege nem osztható 3-mal. Legfeljebb hány eleme van a H halmaznak?

Pozitív egészek modulo 3 lehetnek 0,1,2. Ha két azonos, nem nulla elemet (1+1 kongruens 2, 2+2 pedig 1) összeadsz akkor az nem lesz nulla. Ha két nem azonos, nem nulla elemet adsz össze azokból nulla lesz. Végül, ha két nullát adsz össze azokból is nulla lesz.

Tehát legfeljebb egy nulla lehet, a másik két fajtából pedig csak egyféle lehet. Mivel 2011 mod 3 az 1, ezért 671 kongruens 1 választunk ki plusz egy nullával oszthatót.

3-mal osztható (vagyis 3k+0 értékű) számból egyetlen egy lehet, mert ha kettő is lenne, akkor annak a kettőnek az összege osztható lenne 3-mal.

1 maradékot adó (vagyis 3k+1 értékű) számból lehet sok, mert az ilyeneknek az összege 3k+1 + 3n+1 = 3(k+n)+2, vagyis 2 maradékot ad 3-mal osztva (tehát nem osztható 3-mal). Valamint az ilyen 3k+1 számok mellett lehet a halmazban még egy 3n+0 is, mert az ilyen összeg sem osztható 3-mal (1 maradék lesz: 3(k+n)+1)

3k+1 helyett tehetünk a halmazba 3k+2 értékű (vagyis 2 maradékot adó) számokat is, mert azok egymás közötti összege sem osztható 3-mal (3k+2 + 3n+2 = 3(k+n+1)+1, vagyis 1 a maradék). Az előzőhöz hasonlóan ezek mellett is lehet még egy darab 3-mal osztható a halmazban.

Viszont 3k+1 valamin 3n+2 együtt nem lehet, mert azok összege 3(k+n+1)+0, osztható 3-mal.

Most már csak az a kérdés, hogy 3k+1 vagy 3k+2 értékűekből tudunk-e többet tenni a halmazba? A legkisebb, amit betehetünk az 1, ez 3·0+1 értékű. A legnagyobb, az a 2011, ami szintén 3k+1 értékű (3·670+1). Vagyis ilyenekből van 671 darab. 3k+2-ből viszont csak 670 darab van 2011-ig. Szóval legfeljebb 672 elemű lehet a halmaz: 1, 4, 7, ... 2011 (ez 670 darab 3k+1 értékű szám) plusz még egyetlen egy 3-mal osztható (bármelyik).

Ezt írta az első válaszoló is, csak kongruenciával.