fórum o príkladoch
 korešpondenčný matematický seminár  
kontakt.php

 


8. príklad 2. letnej série 2007/2008

Zadanie:
Do tabuľky s veľkosťou $22\times 22$ vpíšeme čísla $1,2,3,\dots,22^2$, 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ý $4$?


Jardo - 16. 04. 2008 - 14:27:40 z kms.sk
Uhm, už len detail. Ako pozerám na vytlačené vzorové riešenie, počas redikcie (?) došlo k chybičke v počte všetkých vyplnení tabuľky zvyškami. Pre samotné riešenie je to takmer fuk, ale keby sa to niekomu nezdalo, malo tam byť $\binom{22^2}{22^2/2}\binom{22^2/2}{11^2}^2$.

cituj ma

Justus - 15. 04. 2008 - 15:23:50 z kms.sk
OK, pre $6\times 6$ je to fakt 3600... veľmi podozrivé. A chybu som mal už od tretieho člena, som tubas. Asi som nezvolil práve najrýchlejšie konvergujúcu sumu, usudzujúc podľa chyby pre $22\times 22$ :( Ale opäť sčítať to už nemienim, budem radšej veriť misofovi:P Takže Mustang, dobrá správa, mala si pravdu, skutočne tých možností nebolo tak veľa. Tá zlá správa je, že aj napriek tomu žiaden riešiteľ neprebral všetkých... po prihliadnutí k symetrii a tak... vyše $10^{21}$ možností (presne to len z misofovho výsledku neviem vyčísliť, sú tam ešte nejaké samodružné rozloženia).

cituj ma

bus - 15. 04. 2008 - 15:08:15 z dsl-static-251.213-160-168.telecom.sk
To je tak najviac deleno 8, a to tiež nie vždy. Stiahla si to asi tak o jednu cifru :).

cituj ma

Mustang - 13. 04. 2008 - 20:51:37 z static-081-022-141.dsl.nextra.sk
okej a aj tak to este musis vydelit istym poctom kedze nejake stredovo ci osovo sumerne pripady neratam:o)

cituj ma

misof - 11. 04. 2008 - 22:02:14 z spojar.lubbzonet.sk
Mustang: Presne tak. Naozaj si to skús pre $4\times 4$, už tam je tých možností dosť. Napríklad takáto:

$$ {\mbox{\tt 0.0.}\atop \mbox{\tt ....}} \atop {\mbox{\tt .0..} \atop \mbox{\tt ...0}}  $$

cituj ma

Mustang - 11. 04. 2008 - 21:52:30 z static-081-022-141.dsl.nextra.sk
ok a to su vsetko pocty moznosti ulozenia nul takych, ze sa nedotykaju ani rohmi?

cituj ma

Justus - 10. 04. 2008 - 19:11:14 z kms.sk
Čože, tak málo 8O
S tým nerozlišovaním $4$ a $8$ má Bus samozrejme pravdu, inak vychádzajú vo všetkom cifry $121!$ -krát väčšie. Predpokladal som, že pri takých hnusných počtoch spravím kiksy, toto je ale rádovo trochu moc. A ešte aj to s $6\times 6$, hmm. Ja to asi skúsim zrátať ručne-stručne:( Teda pre tých $6\times 6$, samozrejme:))

cituj ma

bus - 10. 04. 2008 - 14:12:48 z dsl-static-251.213-160-168.telecom.sk
Myslím že mišof aj Justus rátajú tie nuly ako rovnaké, teda že nezáleží na tom či vymeníš povedzme 4ku s 8kou. Aj tak je tých možností veľa - skús si to pre 4x4.

cituj ma

misof - 09. 04. 2008 - 22:03:43 z spojar.lubbzonet.sk
A pre $6\times 6$ mi tých rozmiestnení vyšlo len 3600, nie 3616.

cituj ma

misof - 09. 04. 2008 - 22:01:00 z spojar.lubbzonet.sk
Mne to vyšlo tak, že ak chceme, aby žiadne dve nuly nesusedili ani rohom, tak tých $121$ núl sa dá na šachovnicu $22\times 22$ rozmiestniť $10\,749\,154\,284\,380\,665\,611\,224$ spôsobmi.

cituj ma

Mustang - 09. 04. 2008 - 21:11:50 z static-081-022-141.dsl.nextra.sk
ale ved to je nejaka somarina. ty tam ratas kazdu nulu (resp. dvojku) ako inu? lebo inak nie je mozne aby tam bolo tolko roznych moznosti ked to nemoze spolu susedit... uznavam ze ich je viac vyhovujucich, ale tolko urcite nie...

cituj ma

Justus - 09. 04. 2008 - 18:47:48 z kms.sk
Hm, asi som to tam mal dať... Spôsobov, ako rozhodiť [0] do tej tabuľky, je $\binom{22^2}{11^2}$, čo je celkom pekné 117 -miestne číslo. To 60 -miestne vôbec-nie-pekné-číslo-ktoré-netreba-menovať dostaneš, ak nechceš, aby susedili.
Ak sa chceš presvedčiť, skús zrátať možnosti pre štyri čísla v tabuľke $4\times4$. Mala by si dostať 79. Pre $6\times6$ máš 3616 možností, atď.

cituj ma

katka j - 09. 04. 2008 - 14:07:17 z gjgt.sk
hm..ale ked uvazujem, ze tych cisel je 121 a nesmu spolu susedit, tak je tych rozlozeni trosku menej, nie?

cituj ma

Justus - 05. 04. 2008 - 17:53:44 z h3-21.nw.fmph.uniba.sk
Pomerne veľa riešení bolo za 1b alebo za 9b, takú vysokú disperziu som nečakal. Asi by sa hodilo poznamenať, že častou chybou bol predpoklad, že vieme veľmi presne určiť rozloženie čísel [0], resp. [2], v tabuľke. Niečo v tom zmysle, že je len zopár možných uložení týchto čísel do tabuľky. To je ale celkom mylné, počet tých možných rozložení je jedno veľmi škaredé 60 -miestne číslo:(

cituj ma

kamilama - 02. 04. 2008 - 16:55:09 z 158.196.244.87.in-addr.arpa
dobry priklad. ako zlozito som to najprv robila a potom vysvitlo ze je to uplne lahke. ja vo vsetkom najprv hladam zakeraky a potom sa ukaze ze ci to je zakerak alebo nie. toto nebol ta ho chvalim:)

cituj ma

JeFo - 30. 03. 2008 - 14:45:33 z 214.125.119.217.in-addr.arpa
tak ja teda ako prvý pochválim.
dobrý príklad, dobrý príklad, len papkaj a neplac

cituj ma

JeFo - 30. 03. 2008 - 14:44:45 z 214.125.119.217.in-addr.arpa
tak ja teda ako prvý pochválim.
dobrý príklad, dobrý príklad, len papkaj a neplac

cituj ma

Justus - 29. 03. 2008 - 17:26:05 z h3-44.nw.fmph.uniba.sk
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 ma

 

úvod | zadania | poradie | vzoráky | debata | sústredenia | výlety