Úloha 3.u2: Displej (4 b)

Zadáno v čísle 23.3.

Řešeno v čísle 23.5.

Zadání

Máme vysílačku se sedmisegmentovým displejem, který dokáže zobrazit jedinou číslici, a s tlačítky 0, 1, …, 9. Přijdeme ke zhasnuté vysílačce a můžeme libovolně mačkat tlačítka. Každé zmáčknutí vždy změní všechny segmenty příslušné číslice na opačný stav: zhasnutý segment se rozsvítí a ten, co svítil, naopak zhasne. Po prvním zmáčknutí bude tedy na displeji svítit číslice z tlačítka. Pokud bychom jej zmáčkli znovu, displej se vrátí do původního, zhasnutého stavu. Další příklad je na Obrázku 1.

  1. Vysílačka je bohužel už stará a jedno tlačítko se jí rozbilo. Dokážeš zobrazit na displeji číslici z rozbitého tlačítka pomocí těch ostatních? Je nějaké tlačítko nepostradatelné?

  2. Ukaž, že je možné za použití všech tlačítek na displeji zobrazit libovolný obrazec, tedy rozsvítit libovolnou podmnožinu segmentů displeje. S jakou nejmenší skupinou funkčních tlačítek to je možné?

Za každou část úlohy můžeš získat dva body.

Obrázek 1: Po zmáčknutí tlačítek s číslicemi 2 a 3 bude na displeji zobrazený útvar v pravé části obrázku.

Řešení

Nejdříve k části a). Zaměříme se na skupiny číslic takové, že když stiskneme odpovídající tlačítka, tak nakonec na displeji zhasnou všechny segmenty. Takovými skupinami jsou například 02468, 12369 a 5689. Pokud se rozbije nějaké tlačítko, tak stačí najít skupinu, ve které se tlačítko nachází, a zmáčknout všechna ostatní tlačítka z této skupiny. Protože nezáleží na pořadí stisknutí tlačítek, lze snadno nahlédnout, že nakonec na displeji bude svítit chybějící číslice. Všimněme si, že naše nalezené skupiny obsahují všechny číslice kromě 7, umíme tedy jakoukoliv zvolenou číslici kromě 7 nahradit ostatními. Sedmička je nepostradatelná, protože se jako jediná liší horním segmentem od dolního segmentu. Všechna ostatní tlačítka buď rozsvítí/zhasnou horní i dolní segment zároveň, nebo ho neovlivní vůbec, takže nemohou vytvořit číslici 7.

Nyní k části b). Základní postřehy: Pokud libovolné tlačítko zmáčkneme dvakrát, je to stejné, jako kdybychom ho nezmáčkli vůbec. Nezáleží na pořadí stisknutí tlačítek. Takže pokud bychom například postupně namačkali 1, 2, 7, 8, 9, 2, 1, 8, 8, 8, vede to ke stejnému výsledku jako zmáčknutí pouze 7 a 9. Z toho plyne, že má smysl pouze řešit, která podmnožina tlačítek dá jaký výsledek na displeji.

A teď už se budeme věnovat otázce, zda lze na displeji zobrazit libovolný obrazec. Pro ilustraci si řekněme, že chceme rozsvítit obrazec z Obrázku 2.

Obrázek 2: Ukázkový obrazec na displeji, který zkonstruujeme v úloze 3.2.

Sestavíme si rovnice pro stav každého segmentu displeje. Jednotlivé neznámé $x_0$$x_9$ nabývají hodnoty 0, pokud příslušná číslice nebyla zmáčknuta, a hodnoty 1, pokud příslušná číslice byla zmáčknutá. Budeme mít tedy soustavu sedmi rovnic o deseti neznámých.

Všechny naše výpočty budeme provádět nad dvouprvkovým tělesem $\mathbb {Z}_2$, kde sčítání funguje jednoduše: $0+0=0$, $0+1=1$, $1+0=1$, $1+1=0$, což je známo také jako operace XOR (čísla 0 a 1 budeme používat jako koeficienty před proměnnými, byť je nebudeme explicitně psát, takže mějme na paměti, že například $x_3 + x_3 = 0$). Níže uvedené rovnice vlastně vyjadřují, že pokud některý segment má svítit (1), tak z množiny číslic, které ho ovlivňují, musíme zmáčknout lichý počet. Naopak pokud segment nemá svítit (0), tak z jemu odpovídající množiny číslic musíme zmáčknout sudý počet. Podívejme se na naši soustavu rovnic. Pro horní vodorovný segment máme:

\[ x_0+x_2+x_3+x_5+x_6+x_7+x_8+x_9 = 1, \]

pro levý horní segment:

\[ x_0+x_4+x_5+x_6+x_8+x_9 = 0, \]

pro pravý horní segment:

\[ x_0+x_1+x_2+x_3+x_4+x_7+x_8+x_9 = 0, \]

pro prostřední vodorovný segment:

\[ x_2+x_3+x_4+x_5+x_6+x_8+x_9 = 0, \]

pro levý dolní segment:

\[ x_0+x_2+x_6+x_8 = 1, \]

pro pravý dolní segment:

\[ x_0+x_1+x_3+x_4+x_5+x_6+x_7+x_8+x_9 = 1, \]

a nakonec pro dolní vodorovný segment:

\[ x_0+x_2+x_3+x_5+x_6+x_8+x_9 = 0. \]

Budeme aplikovat sčítací metodu. Začneme tím, že první rovnici přičteme ke všem rovnicím obsahujícím $x_0$ a obdržíme soustavu šesti rovnic o devíti neznámých:

\begin{align*} x_2 + x_3 + x_4 + x_7 & = 1\phantom{x_5+x_6+x_8+x_9}\\ x_1 + x_4 + x_5 + x_6 & = 1\\ x_2 + x_3 + x_4 + x_5 + x_6 + x_8 + x_9 & = 0\\ x_3 + x_5 + x_7 + x_9 = & = 0\\ x_1 + x_2 + x_4 & = 0\\ x_7 & = 1\\ \end{align*}

Nyní se zbavíme $x_1$ tím, že druhou rovnici sečteme s předposlední (čímž nám předposlední rovnice zmizí):

\begin{align*} x_2+x_3+x_4+x_7 & = 1\phantom{x_5+x_6+x_8+x_9}\\ x_2+x_5+x_6 & = 1\\ x_2+x_3+x_4+x_5+x_6+x_8+x_9 & = 0\\ x_3+x_5+x_7+x_9 & = 0\\ x_7& =1 \end{align*}

Necháme zmizet $x_7$ dosazením jedničky za $x_7$ do všech rovnic, které $x_7$ obsahují (což není nic jiného než přičtení poslední rovnice):

\begin{align*} x_2+x_3+x_4 & = 0\phantom{x_5+x_6+x_8+x_9}\\ x_2+x_5+x_6 & = 1\\ x_2+x_3+x_4+x_5+x_6+x_8+x_9 & = 0\\ x_3+x_5+x_9 & = 1 \end{align*}

Teď přičteme první rovnici ke druhé a třetí (čímž se první rovnice zbavíme), takže odstraněním $x_2$ dostaneme soustavu 3 rovnic o 6 neznámých:

\begin{align*} x_3+x_4+x_5+x_6 & = 1\\ x_5+x_6+x_8+x_9 & = 0\\ x_3+x_5+x_9 & = 1 \end{align*}

Sečteme první s třetí rovnicí, čímž se nadobro zbavíme $x_3$:

\begin{align*} x_4+x_6+x_9 & = 0\\ x_5+x_6+x_8+x_9 & = 0 \end{align*}

Provedeme poslední sečtení, abychom se zbavili $x_6$:

\[ x_4+x_5+x_8 = 0 \]

Při posledním kroku nám krom $x_6$ vypadlo i $x_9$, takže se můžeme rozhodnout, že bude vždycky nulové. V poslední rovnici si zase můžeme říct, že pouze hodnotu $x_4$ přizpůsobíme pravé straně a proměnné $x_5$ a $x_8$ budou vždy nulové. Získáme tedy:

\begin{align*} x_4 & = 0\\ x_4+x_6 & = 0\\ x_3+x_4+x_6 & = 1\\ x_2+x_3+x_4 & = 0\\ x_2+x_3+x_4+x_7 & = 1\\ x_1+x_4+x_6 & = 1\\ x_0+x_2+x_3+x_6+x_7 & = 1 \end{align*}

Zpětná substituce nám postupně dá:

\[ x_4 = 0,\quad x_6 = 0,\quad x_3 = 1,\quad x_2 = 1,\quad x_7 = 1,\quad x_1 = 1,\quad x_0 = 0. \]

A opravdu! Z jedničky, dvojky, trojky a sedmičky vznikne náš požadovaný symbol. Nyní si všimněme, že na pravých stranách rovnic vlastně vůbec nezáleželo, protože jsme je jen mechanicky přičítali a projevily se až nakonec ve zpětné substituci. Kdybychom si zvolili jiné pravé strany, tak by nám jen vyšla odlišná čísla, ale postup našich úprav by byl stejný. Zejména tedy stále platí, že za $x_9$, $x_5$ a $x_8$ můžeme pořád dosazovat nulu. Znamená to tedy, že tlačítka pro pětku, osmičku a devítku nikdy nepotřebujeme použít a naše rovnice popíší, jak libovolný zadaný znak postavit z číslic 0, 1, 2, 3, 4, 6, 7.

Zjistili jsme tedy, že libovolný obrazec dokážeme sestavit s využitím sedmi tlačítek. S menším počtem tlačítek to už není možné, protože existuje $2^7$ různých obrazců, ale 6 tlačítek by nám dalo pouze $2^6$ kombinací, které lze namačkat.

Martin