Opravovatelia

Michal Staník [email protected]

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}$.