Zdá sa, že máte zablokovanú reklamu

Fungujeme však vďaka príjmom z reklamy a predplatného. Podporte nás povolením reklamy alebo kúpou predplatného.

Ďakujeme, že pozeráte .pod lampou. Chceli by ste na ňu prispieť?

Dve otázky

.časopis .veda

.otázka z minulého týždňa: Na obrázku je slávna matematická úloha, nazývaná Lloydova pätnástka. Ide v nej o to, ako dostať očíslované štvorčeky presúvaním (bez ich vyberania zo škatuľky, znázornenej sivým štvorčekom) do správneho poradia (t.j. do poradia, v ktorom nie je 15 pred 14). Lloyd si bol istý, že úloha sa nedá vyriešiť, pretože to vedel matematicky presne dokázať. Ako sa dá niečo také dokázať?

.odpoveď:
Dôkaz spočíva v zavedení šikovného čísla, preskúmaním zmien tohto čísla pri jednotlivých ťahoch a nakoniec ukázaním, že toto číslo nikdy nemôže nadobudnúť hodnotu zodpovedajúcu konečnej pozícii so správne usporiadanými štvorčekmi.
Spomínané číslo – hovorme mu Lloydovo číslo – je definované ako číslo riadka obsahujúceho prázdny štvorček plus počet tzv. zlých dvojíc, t.j. dvojíc štvorčekov v nesprávnom poradí. V našej štartovacej pozícii je prázdny štvorček v štvrtom riadku a zlá je jediná dvojica (15-14). Lloydovo číslo našej štartovacej pozície je teda 4+1=5. 
V konečnej pozícii sú všetky štvorčeky v správnom poradí a Lloydovo číslo tejto pozície je 4. Otázka teraz je, či sa dá prejsť z pozície s Lloydovým číslom 5 do pozície s Lloydovým číslom 4.
Ako sa zmení Lloydovo číslo pri jednom ťahu? Ak presunieme niektorý zo štvorčekov vodorovne, nezmení sa jeho riadok ani poradie štvorčekov, a teda ani Lloydovo číslo. Iné je to, ak presunieme niektorý zo štvorčekov v zvislom smere. Ak napríklad premiestnime v našej štartovacej pozícii dvanástku smerom nadol, posunie sa prázdny štvorček zo štvrtého do tretieho riadku a okrem toho vzniknú tri nové zlé dvojice: 13-12, 14-12 a 15-12. Lloydovo číslo sa teda zmení o 2.
Podstatné je, že Lloydovo číslo sa zmenilo o párne číslo, a to platí pri každom zvislom premiestnení štvorčeka. Počet zlých dvojíc sa pri takomto premiestnení zmení o nepárne číslo (z 0 na 3, alebo z 1 na 2, alebo z 2 na 1, alebo z 3 na 0 – premyslite si, že je to naozaj tak) a ak k tomu pripočítame zmenu riadka s prázdnym štvorčekom (ten sa zmení o 1) dostaneme párne číslo.
To však znamená, že ak štartujeme z pozície s nepárnym Lloydovým číslom, ostáva to číslo nepárne po každom ťahu (nepárne + párne = nepárne). Z pozície s nepárnym Lloydovým číslom sa preto nikdy nemôžeme dopracovať k pozícii s párnym Lloydovým číslom.
.otázka na tento týždeň:
Poľovník zastrelil medveďa a celý rozrušený z úlovku sa vybral na krátku prechádzku. Najprv išiel kilometer na juh, potom kilometer na západ, potom kilometer na sever a ocitol sa opäť pri zastrelenom medveďovi. Akej farby bol medveď?
Ak ste našli chybu, napíšte na web@tyzden.sk.
.diskusia
.posledné
.neprehliadnite