9. Kamene Miesto Stravy vzorové riešenie

Uvážme čísla \(n^2-n, n^2-n+1, \dots n^2-1, n^2\). Z Dirichletovho princípu vždy nejaké dve z nich musia skončiť v tom istom riadku a tiež nejaké dve musia skončiť v tom istom stĺpci. Tieto dve dvojice čísel navyše nemôžu byť úplne rovnaké (môžu zdieľať iba jeden prvok).

Preto sa isto objaví podiel, ktorý je najviac \(\frac{n^2}{n^2-n}\) a tiež podiel druhej dvojice, ktorý je najviac \[\max\left(\frac{n^2}{n^2-n+1}, \frac{n^2-1}{n^2-n}\right) = \frac{n^2-1}{n^2-n} = \frac{(n-1)(n+1)}{n(n-1)} = 1+\frac{1}{n}.\] Ukážeme, že toto je maximálna možná charakteristika a teda, že vieme zabezpečiť, aby všetky podiely boli aspoň \(1+\frac{1}{n}\).

Čísla rozmiestnime po jednotlivých uhlopriečkach. Začneme \(1\) až \(n\) na hlavnej diagonále. Pokračujeme \(n+1\) až \(2n\) na diagonále pod ňou, pričom diagonály berieme cyklicky, teda prechádzame cez hranice tabuľky. Takto má každá diagonála práve \(n\) políčok. Pre \(n=6\) by tabuľka vyzerala takto.

Aby sa nám ľahšie pracovalo, chceli by sme si nájsť explicitné vyjadrenie prvku na pozícii \((i, j)\). Všimnime si, že vo zvislom smere stúpajú čísla vždy o \(6\) a vo vodorovnom klesajú o \(5\) (všeobecne zvislo stúpajú o \(n\) a vodorovne klesajú o \(n-1\)), preto na pozícii \((i, j)\) je číslo \((ni-(n-1)j) \pmod{n^2}\) indexujúc od \(1\). Jediná výnimka zo striktného modulovania vo vyjadrení je, že namiesto čísla \(0\) máme \(n^2\).

Potrebujeme dokázať tri veci (pre všetky \(n\)): že každé číslo je použité práve raz, že všetky pomery v riadkoch sú aspoň \(1+\frac{1}{n}\) a to isté o pomeroch v stĺpcoch.

Predpokladajme pre spor, že nejaké dve čísla na pozíciách \((i, j)\) a \((k, l)\) sú rovnaké: \[\begin{align} ni-(n-1)j &\equiv nk-(n-1)l \pmod{n^2}, \\ n(i-k) &\equiv (n-1)(j-l) \pmod{n^2}.\end{align}\] Z toho \(n \mid (n-1)(j-l)\) a keďže čísla \(n\) a \(n-1\) sú nesúdeliteľné, nutne \(n \mid j-l\). Avšak \(j\) a \(l\) sú indexy stĺpcov z rozsahu \(1\) až \(n\), a teda ich rozdiel je deliteľný \(n\) len pre \(j=l\). Máme teda \(n(i-k) \equiv 0 \pmod{n^2}\), čo podobne dáva \(n \mid i-k\), a teda aj \(i=k\). Ide teda o to isté číslo na tej istej pozícii. Žiadne číslo nie je v tabuľke dvakrát. Čísel je toľko, koľko políčok (\(n^2\)), takže sa každé v tabuľke musí vyskytovať.

Najmenší pomer v rámci riadku/stĺpca budú mať vždy čísla, ktoré sú v rámci neho po sebe idúce podľa veľkosti. Čísla v rámci riadku sa líšia vždy aspoň o \(n - 1\): keď si ich usporiadame podľa veľkosti, susedné čísla majú rozdiel \(n - 1\), keď sú vedľa seba v tabuľke, a \(2n - 1\), keď jedno je na začiatku a druhé na konci riadku.

Pri fixnom rozdieli je najmenší pomer pri najvyšších číslach, takže tento pomer bude aspoň \(\frac{n^2}{n^2-n+1}\). Tento konkrétny sa však nevyskytne, pretože čísla \(n^2-n+1\) až \(n^2\) sú na diagonále, a teda sa spolu nepomerujú. Preto pomer v riadku bude vždy aspoň \(\frac{n^2-1}{n^2-n} = \frac{n+1}{n} = 1+\frac{1}{n}\). V rámci stĺpca sa čísla vždy líšia aspoň o \(n\), takže podobne ich pomer bude aspoň \(\frac{n^2}{n^2-n} = \frac{n}{n-1} = 1 + \frac{1}{n-1} > 1+\frac{1}{n}\).

Najväčšia možná charakteristika je \(\frac{n+1}{n} = 1 + \frac{1}{n}\).