Riešky tábor - Milí naši Rieškari, ako je už zvykom, aj tento rok sme si pre Vás pripravili Letný tábor Riešok. Je to desaťdňová akcia počas ktorej sa zabavíte, niečo naučíte a hlavne … Prejsť na článok
×5. príklad - Vzorové riešenie
Zadanie
Jeden z týchto strojov vedel prepisovať čísla v tabuľke 5 \times 5 nasledovne:
- Buď si vyberie jeden stĺpec a od všetkých čísel v ňom odčíta 1,
- alebo si vyberie jeden riadok a všetky čísla v ňom vynásobí dvomi.
Teraz má Turing tabuľku s rozmermi 5 \times 5. V každom políčku je celé kladné číslo a chcel by ju pomocou stroja prepísať tak, aby v nej boli samé nuly. Vie to určite urobiť bez ohľadu na to, s akými číslami začína? Ak áno, ako to má spraviť? Ak nie, nájdite príklad kedy to nepôjde a vysvetlite prečo.
Vzorové riešenie
Vieme, že stroj môže buď od celého stĺpca odčítať 1, alebo celý riadok vynásobiť 2. Na začiatok je dôležité uvedomiť si, že ak sa nám podarí dostať nejaké políčko na 0, odčítaním v danom stĺpci sa nám táto 0 zmení na záporné číslo. Avšak ak by sme vynásobili riadok, v ktorom sa toto políčko nachádza, s touto 0 by sa nič nestalo. Tým pádom vieme, že chceme políčka v tabuľke nulovať postupne po stĺpcoch. Ak dostaneme v celom stĺpci samé 0, odčítavať od neho už nemusíme a násobením sa nám nezmení.
Ďalej si treba dávať pozor na to, aby sme sa odčítavaním nedostali do záporných čísel. Odtiaľ sa už totiž nikdy nevieme dostať na 0, pretože odčítavaním sa číslo bude stále zmenšovať, a ak by sme záporné číslo vynásobili 2, taktiež by sme išli iba viac do záporu. Z toho vyplýva, že všetky políčka v jednom stĺpci musíme dostať na 0 naraz, keďže ak by 0 nebola vo všetkých, čísla väčšie ako 0 by sme museli zmenšiť odčítaním, čím by sme ale z núl dostali záporné čísla. V jednom stĺpci tak najprv musíme dostať do všetkých políčok rovnaké čísla.
Ako dostať v stĺpci rovnaké čísla?
Pozrime sa na príklad nejakého jedného stĺpca. Keďže v celej tabuľke máme na začiatku kladné celé čísla, ostatné stĺpce nás teraz zaujímať nemusia keďže odčítavaním v tom našom stĺpci ich meniť nebudeme. Ak by sme nejaký riadok násobili 2, v stĺpcoch s kladnými číslami zostanú kladné a v už vynulových nuly.
5 |
3 |
8 |
4 |
3 |
Krok 1: Teraz môžeme od stĺpca odčítavať , až kým sa nám v nejakom políčku neobjaví 1. Ak by sme odčítali aj vtedy, v tomto políčku by sme dostali 0 a zvyšné by sme už nemohli zmenšovať. Dostaneme napríklad:
3 |
1 |
6 |
2 |
1 |
Krok 2: Ako som už ukázali, odčítavať kvôli políčkam s jednotkami nemôžeme. Neostáva nám nič iné, ako vynásobiť všetky políčka, v ktorých je 1.
3 |
2 |
6 |
2 |
2 |
Keďže 1*1=2, krokom 2 sme vlastne ku vybraným políčkam pripočítali 1. Tým pádom môžeme opäť odčítavať od celého stĺpca. Teraz nám už len stačí striedať krok 1 a krok 2. Postupne totiž zmenšujeme všetky čísla, ktoré sme ešte nikdy nedostali na 1, keďže riadky v ktorých sa tieto čísla nachádzajú nemusíme násobiť a čísla, ktoré sme už niekedy dostali na 1, krokom 2 zväčšíme na 2 a potom krokom 1 opäť na 1. Toto môžeme robiť, až kým odčítavaním nedostaneme do všetkých políčok 1. Vtedy už môžme spokojne odčítať a budeme mať vynulovaný celý stĺpec a presúvame sa na ďalší stĺpec.
Keďže čísla v ďalšom stĺpci, ktorý sa rozhodneme nulovať sa mohli iba zväčšiť, postupným opakovaním krokov 1 a 2 sa nám podarí vynulovať aj tento stĺpec a napokon aj všetky zvyšné.