Zadanie



Bea si vytlačila v KMS-ku skriptá, ktoré majú \(2003\) strán s číslami \(1,\ 2,\ \dots ,\ 2003\). Skriptá však nedávajú zmysel, preto si musí z nich vybrať tie správne strany.

Nájdite najväčšiu takú množinu \(A\), ktorá je podmnožinou množiny \(\{1, 2, \dots , 2003\}\) a neexistujú dva prvky \(a\), \(b\) množiny \(A\), pre ktoré je číslo \(a + b\) deliteľné číslom \(a - b\).

Začnime v malom. Môže hľadaná množina obsahovať dve po sebe idúce čísla? Keby mohla, ich rozdiel by bol \(1\). Problém je, že \(1\) delí všetky prirodzené čísla, a teda bude určite deliť aj ich súčet, preto žiadne dve po sebe idúce čísla v hľadanej množine nebudú.

Poďme ďalej – môže hľadaná množina obsahovať dve čísla s rozdielom \(2\)? Keby áno, ich súčet by nesmel byť deliteľný dvomi. Lenže dve čísla s rozdielom \(2\) sú buď obe párne, alebo obe nepárne. Keď ich sčítame, výsledok bude vždy párny. Takže nie, ani dve čísla s rozdielom \(2\) v hľadanej množine nebudú.

Ďalšia rečnícka otázka asi nikoho neprekvapí – môže hľadaná množina obsahovať dve čísla s rozdielom \(3\)? Rozoberme si tak ako doteraz ich deliteľnosti. Ak by boli tieto čísla deliteľné tromi, aj ich súčet by bol deliteľný tromi a delil by ho potom aj ich rozdiel (ktorý je rovný \(3\)). Vyskúšajme zvyšok po delení trojkou rovný \(1\), teda čísla \(3k+1\) a \(3k+4\). Ich súčet bude \(6k+5\), čiže nebude deliteľný tromi. Hurá, našli sme konečne nejaké čísla, ktoré môžu byť v hľadanej množine!

V prvých dvoch odsekoch sme zistili, že najlepšie, čo vieme dosiahnuť, je množina obsahujúca každé tretie číslo z pôvodnej množiny. Každé tretie číslo znamená, že ostanú čísla vo forme \(3k\), \(3k+1\) alebo \(3k+2\). V treťom odseku sme zahodili možnosť \(3k\) a v možnosti \(3k+1\) sme zistili, že po sebe nasledujúce dvojice čísel fungujú. Vedeli by ale fungovať všetky? Poďme to zistiť – keď odčítame čísla \(3k+1\) a \(3l+1\) ich rozdiel bude deliteľný tromi (zvyšky \(1\) po delení tromi sa navzájom zrušia). Ich súčet bude \(3(k+l)+2\), preto určite nebude deliteľný tromi, teda ani ich rozdielom. Podmnožina pôvodnej množiny obsahujúca čísla \(3k+1\) bude preto celá vyhovovať podmienke zo zadania (rovnako viete ukázať, že bude fungovať aj podmnožina s číslami \(3k+2\)). Ľahko si už teraz dopočítame koľko prvkov má táto podmnožina. Je to počet všetkých prirodzených čísel zo zvyškom po delení tromi rovným \(1\). Tých je \(668\) a to je aj maximum, ktoré sa dá dosiahnuť.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.