Telefonní číslo jedním tahem

Úloha Bobříka informatiky z roku: 2020 , kategorie: Benjamin
obtížnost: Lehká, kód úlohy: 2020-UZ-04
autor: Maksim Bolonkin

Klávesnice chytrého telefonu vypadá následovně:

Telefonní číslo vytočené jedním tahem je takové, při němž se položí prst na některé tlačítko a pak se s ním jezdí po tlačítkách, prst se nezvedá. Nesmí se sjet prstem do prostoru mimo klávesy.

Například, když je prst na tlačítku 1, můžeme s ním přejet na sousední tlačítka 2, 4 nebo 5. Když je prst na tlačítku 5, lze prstem přejet na kterékoliv tlačítko od 1 do 4 a od 6 do 9.

Jaké telefonní číslo můžeme vytočit jedním tahem?

Odpovědi

752 480 900

742 235 425

780 753 605

753 685 151

Nechci odpovídat

Zdůvodnění správné odpovědi

Správná odpověď je 753 685 151.

Ostatní odpovědi nejsou správné:

Při vytáčení čísla 780 753 605 bychom museli u předposledního čísla zvednout prst, neboť tlačítko 0 se nenachází vedle 6.

Při vytáčení čísla 752 480 900 nelze napsat dvě stejná čísla za sebou (00) jedním tahem prstu, mmuseli bychom zvednout prst.

Při vytáčení čísla 742 235 425 je stejný problém jako u přechozího čísla. Nelze napsat dvě stejná čísla za sebou (22) jedním tahem prstu.

Co má tato úloha společného s informatikou

Sousedící tlačítka odpovídají v informatice husté mřížce s osmi sousedy (každý bod uvnitř mřížky má 8 sousedů, což je hodně oproti normální mřížce třeba u drátěného plotu, kde má každý bod 4 sousedy.

Mřížkové grafy se používají v různých praktických problémech, souvisejících např. s návrhem integrovaných obvodů VLSI (s velmi vysokou mírou propojení), při výrobě tištěných spojů do počítačů, se snižováním jejich složitosti.

Dnešní displeje mobilních telefonů umožňují tzv. gesta, tedy třeba psaní slov tažením prstu po klávesnici. Stejně jako některá telefonní čísla jsou více žádaná, protože se snadno zapamatují (např. 123456789, 212121212, 666666666), jiná telefonní čísla mohou být zajímavá tím, že jdou vytvořit gestem, ted tažením prstu po displeji (jako v naší úloze) nebo tím, jaký obrazec vykreslí při jeho vytáčení (např. 123698741 vykreslí čtverec nebo 147258369 projde tlačítka postupně po sloupcích).