Zadanie: Do tabuľky s veľkosťou vpíšeme čísla , každé práve raz. Je pravda, že vždy vieme vybrať dvojicu políčok susediacich rohom alebo stranou tak, že súčet čísel vpísaných v týchto políčkach bude deliteľný ?

meno: e-mail:

[cituj]Justus napísal: Ako to, že tento pekný príklad ešte nikto nepochválil:( No tak šup-šup do písania. Pre ostatných tu máme riešenie. Oproti vzoráku sa bude trochu viac venovať tomu, ako sme na tú-onú vec prišli. R: V takejto úlohe potrebujeme najskôr pojať podozrenie, že to buď ide alebo nejde. Preto si najskôr skúsme tabuľku nejako premyslene vyplniť. Ako zjednodušovák nám poslúži poznatok, že namiesto čísiel $1$, $\dots $, $22^2$ stačí používať ich zvyšky po vydelení štyrma, teda $0$, $1$, $2$ a $3$. Dvaja susedia tak budú mať súčet deliteľný štvorkou, práve ak ho aj pôvodné čísla mali ňou deliteľný. Ukladajme čísla tak, aby sme nemali taký súčet. Ak vyplníme celú tabuľku, tak sme skončili. Ak sa nám to naopak nepodarí, tak by to mohlo niečo znamenať. Snažíme sa teda izolovať jednotlivo nuly a dvojky a nemiešať jednotky s trojkami. To by šlo napríklad tak, že nepárne riadky vyplníme s $0202\dots$ a párne riadky striedavo buď s $111\dots$ alebo $333\dots$. Nepárnych riadkov je ale nepárny počet, takže by sme takto nevpísali rovnaký počet jedničiek a trojiek. Ďaľšími drobnými úpravami síce dôjdeme až k tabuľke s jedinkou dvojicou nevhodných susedov, ktorých sa ale nie a nie zbaviť. To je už fakt podozrivé. Všimnime si, že tabuľka $2008\times2008$ sa vyššie uvedeným spôsobom vyplniť dá tak, že v nej nenájdeme inkriminovanú dvojicu. No a keby sa dala vyplniť aj naša tabuľka, tak sa môžete staviť, že by zadávači použili tabuľku $2008\times2008$. Takže teraz vieme, že máme dokázať pravdivosť tvrdenia v zadaní. Skúsime úlohu riešiť pre nejakú menšiu tabuľku s podobnými vlastnosťami, ako má naša. Predošlé vyplnenie sa dá úspešne zrealizovať pre rozmery tabuľky deliteľné štyrma, preto je rozumné očakávať, že štvorka je perióda, s akou sa vlastnosti tabuliek opakujú. Takže sa pozrime na tabuľku $2\times2$ :) Vieme, že v nej bude jednotka a trojka. Taktiež vidíme, že každé dve políčka tejto tabuľky spolu susedia, čo platí aj pre jednotku a trojku pri ľubovoľnom vyplnení. Tvrdenie preto platí. Vedeli by sme niečo z toho použiť aj na väčšie tabuľky? Veľmi sľubne vyzerá tá časť o každých dvoch políčkach. Kým pre dve políčka totiž máme jeden vzťah, pre tri už sú to tri vzťahy a pre štyri dokonca až šesť. Bohužiaľ pre päť a viac políčok už nenájdeme také plošné usporiadanie, aby každá dvojica susedila, čo by mohlo veci komplikovať. Ale aj chlievik $2\times2$ vyzerá veľmi schopne. Našu tabuľku vieme pekne rozdeliť na $11^2$ takýchto chlievikov. Čo sme tým dostali? Pretože políčka chlievika susedia, tak pokiaľ v niektorom sú dve nuly, máme našu dvojicu. Nech je teda v každom chlieviku práve jedna nula. Nech je tiež po jednej dvojke v každom chlieviku, inak máme zase hľadanú dvojicu. V chlievikoch ostávajú ešte po dve voľné miesta. V tomto momente by už malo byť vidieť, ako to dorazíme na nesediacej parite. Ak to nevidíte, radšej na chvíľku nečítajte ďalej a popremýšľajte. Ďaľší postup je len rutinný dôkaz, z ktorého možno ideu nie je hneď vidieť. Okrem toho ho možno previesť mnohými spôsobmi. Ak by sa v žiadnom chlieviku nemiešali jednotky a trojky, tak by v celej tabuľke bol párny počet jednotiek (lebo počet jednotiek v nemiešanom chlieviku je párny). Ale my máme $11^2$ jednotiek, preto musí existovať miešaný chlievik, a to jedine tak, že v ňom bude jedna jednotka a jedna trojka- a opäť máme hľadanú dvojicu. Fertig.[/cituj]

V príspevku je na písanie matematických výrazov možné používať príkazy TeXu. Help k ich používaniu nájdete na kms.sk/tex.php.