10. Kontradikció Monotheism Superlatif vzorové riešenie

Označme si hľadanú množinu čísel \(x_1,\ x_2, \dots,\ x_n\). Má nám platiť \(x_1 + x_2 + \dots + x_n=n\) a \(x_1 \cdot x_2 \cdot \dots \cdot x_n=n\).

Môžeme si všimnúť, že ak máme nejakú množinu čísel a pridáme k nej jednotku, súčin sa nezmení, ale súčet (ktorý očakávame, že zvyčajne bude menší), sa zväčší o \(1\). Ďalšia užitočná vec, ktorá sa môže hodiť pri konštrukcii, je, že pridaním štyroch čísel \(-1,\ -1,\ 1,\ 1\) sa nezmení ani súčet, ani súčin. Teda keď sa nám podarí zapísať nejaké číslo \(n\) ako súčin aj súčet tých istých \(t\) čísel, vieme ho zapísať aj ako súčet \(t+4,\ t+8, \dots\) čísel atď.

Keďže \(x_1 \cdot x_2 \cdot \dots \cdot x_n=n\), musia byť všetky \(x_i\) deliteľmi čísla \(n\). Keďže chceme v tomto tvare zapísať čo najviac čísel, a to aj prvočísla, či čísla, ktoré sú súčinom len málo prvočísel a ťažko sa rozkladajú, bolo by dobré nájsť taký rozklad, ktorý obsahuje čo najviac \(\pm 1\) a čo najmenej iných čísel.

Keďže pridanie štvorice \(1,\ 1,\ -1,\ -1\) k nejakému zápisu nezmení ani súčet, ani súčin, pre čísla \(n=4k+1\) vieme jednoducho za čísla \(x_i\) zobrať číslo \(n\), \(2k\) jednotiek a \(2k\) mínus jednotiek.

\[n=n \cdot (-1)^{2k} \cdot 1^{2k}\] \[n=n+(-1) \cdot 2k+1 \cdot 2k\]

Ak máme párne číslo, musí vo svojom rozklade obsahovať párny počet párnych sčítancov, a teda aj činiteľov. Je to kvôli tomu, že keby ich bol nepárny počet, ich súčet by bol párny a k nemu by sme pridali ešte nepárny počet nepárnych čísel (zvyšné sčítance) a dokopy by sme mali nepárny súčet. My ale potrebujeme dostať párny súčet rovný \(n\).

Z toho vidno, že čísla tvaru \(n=4k+2\) v požadovanom tvare zapísať nemožno. Sú párne, musíme použiť aspoň jedno párne \(x_i\), ale zároveň takých musí byť párny počet, čiže musíme mať aspoň dve. Avšak vtedy už súčin bude deliteľný \(4\) a je jedno, čo k tomu prinásobíme, nikdy nedostaneme číslo tvaru \(4k+2\).

Ak máme číslo \(4\), musíme tiež použiť aspoň dva párne činitele, takže musíme použiť čísla \(1,\ 1,\ 2,\ 2\) s nejakými znamienkami. Záporných musí byť vždy párny počet. Ak budú všetky kladné, dostaneme súčet \(6\), ak budú aspoň dve záporné, dostaneme najviac \(2+2-1-1=2\). Ani štvorku teda zapísať nevieme.

Ak však budeme mať väčšie číslo deliteľné štyrmi, rozklad na súčin \(n=\frac{n}{2} \cdot 2\) nám už pomôže, len sa musíme pohrať so znamienkami tak, aby sme dostali správny súčet. Znamienko pri dvojke dokonca závisí od zvyšku \(n\) po delení ôsmimi, teda pre \(n\), ktoré je násobkom \(4\), rozlíšime dva prípady:

1. \(n=8k\), \(k \geq 1\): \[n=2 \cdot (4k) \cdot (-1)^{2k} \cdot 1^{6k-2},\] \[n=2 + 4k + (-1) \cdot (2k) + 1\cdot(6k-2),\]

2. \(n=8k+4\), \(k \geq 1\): \[n=(-2) \cdot (4k+2) \cdot (-1)^{2k-1} \cdot 1^{6k+3},\] \[n=(-2) + (4k+2) + (-1) \cdot (2k-1) + 1 \cdot (6k+3).\]

Číslo \(4\) by patrilo do prípadu \(2.\), lenže \(k\) by bolo \(0\) a počet mínus jednotiek by musel byť \(2k-1 = -1\), čo nie je možné.

Napokon nám ostávajú čísla \(n\) tvaru \(4k+3\). Tie sú tvrdý oriešok. Ak skúšame takéto čísla zapísať v požadovanom tvare, nijak sa nám to nedarí, takže by sme mohli skúsiť dokázať, že sa to nedá. Z toho, čo sme zistili doteraz, zrejme budú dôležité zvyšky po delení \(4\). Keďže máme \(n\) nepárne, všetky \(x_i\) musia byť nepárne, teda mať zvyšok \(1\) alebo \(3\) po delení \(4\) (inak dostaneme párny súčin).

Použijeme dôkaz sporom. Pre spor predpokladajme, že sme našli vyhovujúce čísla \(x_i\) a roztrieďme ich podľa zvyškov a znamienok.

Označme \(A\) počet tých, ktoré majú zvyšok \(1\) a sú kladné (napr. \(1\), \(5\), …), \(B\) počet tých, ktoré majú zvyšok \(3\) a sú kladné (\(3\), \(7\), …), pre záporné označme \(C\) počet tých, ktoré majú v absolútnej hodnote zvyšok \(1\) (\(-1\), \(-5\), …) a \(D\) počet tých v absolútnej hodnote so zvyškom \(3\) (\(-3\), \(-7\), …).

Musí platiť, že všetkých \(x_i\) so zvyškom abs. hodnoty \(3\) je nepárny počet, inak bude mať celkový súčin absolútnych hodnôt zvyšok \(1\) (dvojica čísel so zvyškom \(3\) má súčin so zvyškom \(1\)), takže \(B\) a \(D\) majú rôznu paritu.

Ďalej máme \(n=A+B+C+D \equiv 3 \pmod 4\), pretože počet všetkých \(x_i\) je dohromady \(n\).

Poďme sa pozrieť na to, aký zvyšok má súčet čísel \(x_i\) a porovnať ho s \(n\):

\[n = x_1 + \dots + x_n \equiv A \cdot 1 + B \cdot 3 - C \cdot 1 - D \cdot 3 \equiv A-B-C+D \equiv n \equiv A+B+C+D \pmod 4,\] \[A-B-C+D \equiv A+B+C+D \pmod 4.\]

Všetkých záporných čísel musí byť párny počet, aby bol súčin kladný, teda \[\begin{aligned} C+D &\equiv 0 \pmod 2,\\ 2C+2D &\equiv 0 \pmod 4.\end{aligned}\]

Keď túto kongruenciu odčítame od pravej strany, dostaneme \[\begin{aligned} A-B-C+D &\equiv A+B-C-D \pmod 4,\\ -B+D &\equiv B-D \pmod 4,\\ 2B-2D &\equiv 0 \pmod 4,\\ B-D &\equiv 0 \pmod 2,\end{aligned}\]

čo je ale spor, pretože \(B\) a \(D\) musia mať rôznu paritu (ako sme už ukázali vyššie).

Aby sme si to zhrnuli, čísla \(n\), ktoré sa dajú zapísať ako súčin aj súčet tých istých \(n\) celých čísel, sú práve všetky čísla so zvyškom \(0\) alebo \(1\) po delení \(4\) okrem samotného čísla \(4\).