Kategórie:
5
6
7
8
9

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

Opravovali: Adel, Majko, MartinŠ, RiKi5515

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=2krokom 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 2 sa nám podarí vynulovať aj tento stĺpec a napokon aj všetky zvyšné.