8. príklad - Vzorové riešenie

Poprvé je dobré si uvedomiť, že ak nájdeme najmenší možný súčet a dokážeme že je naozaj najmenší, a stále bude väčší alebo rovný 1, tak tým dokážeme aj to, že nech vyberieme ľubovoľné čísla, tak ich súčet bude tiež väčší alebo rovný 1.

Môžeme všimnúť, že v každom riadku čísla klesajú z ľava doprava a v každom stĺpci klesajú zhora dole. Konkrétne, za každé políčko doprava/dole sa zvačšuje menovateľ o 1.

Teda ak by sme nachvíľku zanedbali, že tie čísla musia byť z rôznych stĺpcov, tak by sme zjavne mohli vybrať čísla z pravého stĺpca, a súčet by bol najmenší možný. Tento súčet síce nespĺňa zadanie, ale vieme ho využiť tak, že ku každému číslu v riadku prirátame rozdiel medzi krajným číslom z nášho súčtu a číslom v tom istom riadku ktoré naozaj vyberieme. Tým vlastne dostaneme v súčte to číslo v riadku, ktoré sme vybrali. 
Potom úlohu môžeme premeniť na to, že sa pokúšame zistiť čo je najmenej môžeme prirátať.

Čiže napríklad ak v prvom riadku v nejakom konkrétnom výbere čísiel vyberieme tretie číslo sprava, tak by sme ku \frac{1}{n}​ prirátali

\frac{1}{n-2} - \frac{1}{n} = \frac{n-(n-2)}{n(n-2)} = \frac{2}{n(n-2)}
\frac{1}{n} + \frac{2}{n(n-2)} = \frac{1}{n-2}​​

Najprv sa pozrime na to, že koľko treba prirátať všeobecne v i-tom riadku, kde horný riadok je nultý a spodný je n-1. Potom pekne platí, že v i-tom riadku je číslo úplne vpravo \frac{1}{n+i} keďže ako sme si už vyššie všimli, tak za každé políčko smerom dole sa menovateľ zväčšuje o 1.

Potom sa pozrime, že aký je rozdiel medzi krajným a políčkom o x políčok vľavo.

​\frac{1}{n+i-x}-\frac{1}{n+i}=\frac{n+i-(n+i-x)}{(n+i)(n+i-x)}=\frac{x}{(n+i)(n+i-x)}​​

Teraz si môžeme uvedomiť, že kebyže sa pozeráme na políčko v tom istom stĺpci, ale v nižšom riadku (teda i by bolo väčšie), tak by sme výsledne prirátali menšie číslo. Nemôžeme si ale len tak povedať, že všetko budeme prirátavať v poslednom riadku, keďže musíme mať jedno číslo z každého riadku.

Môžeme sa teda teraz pozrieť, že či čísla viac vľavo tabuľky sa oplatí vyberať z hora alebo z dola.

Porovnajme nejaké čísla v i-tom a j-tom riadku. Nech bez ujmy na všeobecnosti platí i\lt j. Podobne nech si vyberieme čísla, ktoré sú v jednom riadku o x​ políčok od pravého kraja, a v druhom o y
Nech bez ujmy na všeobecnosti, x\gt y

Teraz máme 2 možnosti, buď máme políčko vzdialené o x od kraja v i-tom, alebo v j-tom stĺpci (to vzdialené o y bude logicky v tom, v ktorom nie je x​)

Poďme teda zistiť, že v ktorom prípade je ten rozdiel ktorý prirátame menší.

​\frac{x}{(n+i)(n+i-x)}+\frac{y}{(n+j)(n+j-y)} \ \Box \ \frac{y}{(n+i)(n+i-y)}+\frac{x}{(n+j)(n+j-x)} \ /-\frac{y}{(n+i)(n+i-y)}-\frac{y}{(n+j)(n+j-y)} \\[0.5em]\frac{x}{(n+i)(n+i-x)}-\frac{y}{(n+i)(n+i-y)} \ \Box \ \frac{x}{(n+j)(n+j-x)}-\frac{y}{(n+j)(n+j-y)} \\[0.5em]\frac{x(n+i-y) - y(n+i-x)}{(n+i)(n+i-x)(n+i-y)}\ \Box \ \frac{x(n+j-y) - y(n+j-x)}{(n+j)(n+j-x)(n+j-y)} \\[0.5em]\frac{(x-y)(n+i)}{(n+i)(n+i-x)(n+i-y)}\ \Box \ \frac{(x-y)(n+j)}{(n+j)(n+j-x)(n+j-y)} \ /:(x-y) \\[0.5em]\frac{1}{(n+i-x)(n+i-y)}\ \Box \ \frac{1}{(n+j-x)(n+j-y)} \ / \cdot (n+i-x)(n+i-y)(n+j-x)(n+j-y) \\[0.5em](n+j-x)(n+j-y)\ \Box \ (n+i-x)(n+i-y)

Všimnime si, že n+i-x, n+i-y, n+j-x, n+j-y sú všetky väčšie ako 0, lebo stále reprezentujú čísla v tabuľke, a tie všetky majú kladného menovateľa. To znamená, že sme nimi mohli našu rovnicu vynásobiť.
Taktiež, keďže sme povedali, že x\gt y tak x-y\gt 0 a teda sme mohli týmto výrazom bez problémov deliť.

Keďže j\gt i tak vieme povedať, že ľavá strana je väčšia ako pravá, čo znamená, že aj pôvodne bola ľavá väčšia ako pravá. Pravá strana, ako sme si už vyššie popísali, reprezentuje, že číslo viac v pravo vyberieme z nižšieho riadku, a menšie z vyššieho. 

​\frac{x}{(n+i)(n+i-x)}+\frac{y}{(n+j)(n+j-y)} \ \gt \frac{y}{(n+i)(n+i-y)}+\frac{x}{(n+j)(n+j-x)}​​

Keďže ale pre ľubovoľnú dvojicu platí, že čísla viac vpravo chcú byť vyššie, tak môžeme povedať, že najmenšie riešenie bude vtedy, keď zoberieme číslo najviac vpravo v hornom riadku, potom číslo v riadku pod ním o jedna vľavo, v ďaľšom o 2, atď. Taže celkovo najmenší možný súčet nastane vtedy, keď zoberieme diagonálu z ľavého dolného do pravého horného rohu.

Teraz si len stačí všimnúť, že na tejto diagonále sú všetky čísla \frac{1}{n} a keďže ich je dokopy n tak ich súčet bude n \cdot \frac{1}{n}=1

Keďže sme dokázali, že toto je najmenší možný súčet, tak všetky ostatné možné musia teda tiež byť aspoň 1. 

Komentár k inému riešeniu:

Veľa riešiteľov NEDOSTATOČNE argumentovalo nasledovne:

Chceme ukázať, že každé riešenie má rovnaký alebo väčší súčet, ako keď vyberieme čísla na uhlopriečke. Výpočtom (podobným ako vyššie) ukážeme, že keď namiesto čísla z tejto uhlopriečky vyberieme iné číslo, tak budeme musieť zmeniť aj jedno iné číslo (aby sme zachovali že v každom riadku aj stĺpci je jedno) a tieto dokopy nám budú dávať rovnaký súčet. Teda všetko je horšie ako uhlopriečka.

Tento argument však nie je úplný. Nie všetky vybratia políčok vieme dostať z uhlopriečky tak, že vymeníme riadok a stĺpec nejakej dvojice z uhlopriečky. Robíme aj iné výmeny, a niektoré nám aj súčet znížia. Je ťažké dokázať, že tieto zníženia nás nevedia dostať pod súčet 1. Preto bol potrebný o trochu sofistikovanejší argument:

Výpočtom (ako vyššie) sme ukázali, že ak máme dva stĺpce, z ktorých ten naľavo má vybraté políčko vyššie, ako ten napravo, tak vieme súčet zmenšiť tým, že v nich vybraté políčka vymeníme (vymeníme, ktorý je v ktorom riadku). Spôsob vybratia políčok s najmenším súčtom bude teda musieť byť nejaký taký, v ktorom toto zlepšenie spraviť nevieme, teda sa tam také dva stĺpce nenachádzajú. Vo všetkých ostatných prípadoch vieme vybraté políčka postupne po dvojiciach stĺpcov meniť, kým sa k takému nedostaneme. Ako môže vyzerať takéto vybratie? Každé vybraté políčko musí mať napravo od seba vybraté políčka iba vyššie. Teda v stĺpci naľavo musí byť políčko úplne dole, aby všetky ďalšie boli nad ním, a tak ďalej, a dostaneme sa k jedinej možnosti, čo je práve uhlopriečka. Ukázali sme teda, že všetky iné vybratia sa dajú upravovať tak, že iba zmenšujeme súčet, a dostaneme sa k uhlopriečke. Tá má preto najmenší možný súčet, ktorý je 1​.