Sudoku v štvorprvkovom poli

[Martin Sleziak]

Zámerom bolo sčasti aj ukázať, že existuje štvorprvkové pole. (A teda existujú aj konečné polia iné ako $\mathbb Z_p$.)

Zostaňme pri tom, že sa pozrieme na tabuľku, ktorá bola v zadaní a rozmyslime si, čo o nej vieme povedať. Neskôr sa na iných predmetoch dozviete o konečných poliach viac:

• Pre každé prvočíslo $p$ a celé číslo $n\ge1$ existuje pole, ktoré má $p^n$ prvkov.
• Naučíte sa, ako sa takéto pole dá skonštruovať.
• Uvidíte aj to, že takéto pole existuje práve jedno (až na izomorfizmus).

Ak by sa náhodou niekto z vás trochu chcel pozrieť na niečo o tejto téme, tak ako obvykle, pridám aj linku na Wikipédiu: Finite field (tu je linka na súčasnú revíziu). Článok na Wikipédii má aj časť venovanú štvorprvkovému poľu: Finite field § Field with four elements.

Ale tu naozaj nechceme spraviť nič viac, iba skúsiť, či vieme doplniť tabuľku. (A potom sa môžeme zamyslieť nad tým, či vyšlo naozaj pole - aj keď toto už nebolo súčasťou zadania.)$\newcommand{\Z}{\mathbb Z}
\newcommand{\sm}{\setminus}$

Majme štvorprvkovú množinu $F=\{0,1,a,b\}$ a binárne operácie $+$, $\cdot$ na tejto množine.
Ak viete, že $(F,+,\cdot)$ je pole, tak doplňte zvyšok zadaných tabuliek:

$$\begin{array}{cc}
\begin{array}{c|cccc}
+ & 0 & 1 & a & b \\\hline
0 & 0 & 1 & a & b \\
1 & & 0 & & \\
a & & & 0 & \\
b & & & & 0
\end{array}
&
\begin{array}{c|cccc}
\cdot & 0 & 1 & a & b \\\hline
0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & a & b \\
a & & & & \\
b & & & &
\end{array}
\end{array}$$

T.j. v tabuľkách máme zadané, že $0+x=x$ a $x+x=0$ pre všetky $x\in F$. A tiež to, že $0\cdot x=0$ a $1\cdot x=1$ pre všetky $x\in F$.

Zdôvodnite, prečo váš výsledok je jediná možnosť, ako sa tieto tabuľky dajú doplniť. (To, či na konci naozaj vyšlo pole, overovať nemusíte.)

Ako sa dá doplniť tabuľka?
V poli o operáciách $+$ a $\cdot$ vieme, že sú komutatívne - takže z toho môžeme doplniť symetrické prvky, ktoré chýbajú.
$$\begin{array}{cc}
\begin{array}{c|cccc}
+ & 0 & 1 & a & b \\\hline
0 & 0 & 1 & a & b \\
1 & 1 & 0 & & \\
a & a & & 0 & \\
b & b & & & 0
\end{array}
&
\begin{array}{c|cccc}
\cdot & 0 & 1 & a & b \\\hline
0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & a & b \\
a & 0 & a & & \\
b & 0 & b & &
\end{array}
\end{array}$$
Súčasne z toho, čo máme zatiaľ vyplnené, už vidíme, že neutrálny prvok pre sčitovanie je $0$ a pre násobenie to je $1$. (Takže označenie nuly a jednotky je také, na aké sme zvyknutí.)

Môžeme napríklad skúsiť využiť to, že $(F,+)$ je grupa - a teda v riadkoch a stĺpcoch sa nesmú opakovať prvky. (Využívame zákony o krátení.)
Teda napríklad $a+1$ nemôže byť $0$, $1$ ani $a$, zostáva nám iba možnosť
$$a+1=1+a=b$$
a po doplnení máme
$$\begin{array}{c|cccc}
+ & 0 & 1 & a & b \\\hline
0 & 0 & 1 & a & b \\
1 & 1 & 0 & b & \\
a & a & b & 0 & \\
b & b & & & 0
\end{array}$$
Teraz nám už v druhom i treťom riadku (aj v zodpovedajúcich stĺpcoch) zostalo jediné voľné políčko - tam už máme jedinú možnosť ako tabuľku doplniť.

Dá sa to teda iba takto:
$$\begin{array}{c|cccc}
+ & 0 & 1 & a & b \\\hline
0 & 0 & 1 & a & b \\
1 & 1 & 0 & b & a \\
a & a & b & 0 & 1 \\
b & b & a & 1 & 0
\end{array}$$

Podobnú techniku môžeme využiť na doplnenie tabuľky komutatívnej grupy $(F^*,\cdot)$. Napríklad z toho, že $ab$ nemôže byť ani $a$ ani $b$ dostaneme $ab=ba=1$.
$$\begin{array}{c|cccc}
\cdot & 0 & 1 & a & b \\\hline
0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & a & b \\
a & 0 & a & & 1 \\
b & 0 & b & 1 &
\end{array}$$
A vieme už vyplniť aj zostávajúce voľné miesta:
$$\begin{array}{c|cccc}
\cdot & 0 & 1 & a & b \\\hline
0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & a & b \\
a & 0 & a & b & 1 \\
b & 0 & b & 1 & a
\end{array}$$

Ak sa teda dá naozaj dostať pole doplnením voľných miest, tak jediná možnosť je:
$$\begin{array}{cc}
\begin{array}{c|cccc}
+ & 0 & 1 & a & b \\\hline
0 & 0 & 1 & a & b \\
1 & 1 & 0 & b & a \\
a & a & b & 0 & 1 \\
b & b & a & 1 & 0
\end{array}
&
\begin{array}{c|cccc}
\cdot & 0 & 1 & a & b \\\hline
0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & a & b \\
a & 0 & a & b & 1 \\
b & 0 & b & 1 & a
\end{array}
\end{array}$$

[Martin Sleziak]

Je to naozaj pole?$\newcommand{\Z}{\mathbb Z}
\newcommand{\sm}{\setminus}$

Toto síce nebolo súčasťou úlohy, ale môžeme sa skúsiť zamyslieť aj nad tým, či sme skutočne dostali pole.

Niektoré časti vieme skontrolovať pomerne ľahko.
Vidíme, že $+$ a $\cdot$ sú binárne operácie - do tabuľky sme vždy dopĺňali iba prvky z $F$.

Mali by sme si rozmyslieť, či $(F,+)$ a $(F\sm\{0\},\cdot)$ sú grupy.
Našťastie máme už dosť skúseností s malými grupami: Vieme si všimnúť, že keď porovnáme $(F,+)$ s tabuľkou jednej známej štvorprvkovej grupy, tak to je v podstate to isté. A vieme nájsť aj trojprvkovú grupu, ktorá vyzerá rovnako ako $(F\sm\{0\},\cdot)$.

Spoiler:

Doteraz sme ako štvorprvkové grupy stretli v podstate iba $(\Z_4,+)$ a $(\Z_2\times\Z_2,+)$.
Ak sa pozrieme na tabuľku $(F,+)$ tak vidíme, že je rovnaká ako $\Z_2\times\Z_2$ až na "premenovanie prvkov". (T.j. tieto grupy sú izomorfné.)
$$\begin{array}{cc}
\begin{array}{c|cccc}
+ & 0 & 1 & a & b \\\hline
0 & 0 & 1 & a & b \\
1 & 1 & 0 & b & a \\
a & a & b & 0 & 1 \\
b & b & a & 1 & 0
\end{array}
&
\begin{array}{c|cccc}
+ & (0,0) & (0,1) & (1,0) & (1,1) \\\hline
(0,0) & (0,0) & (0,1) & (1,0) & (1,1) \\
(0,1) & (0,1) & (0,0) & (1,1) & (1,0) \\
(1,0) & (1,0) & (1,1) & (0,0) & (0,1) \\
(1,1) & (1,1) & (1,0) & (0,1) & (0,0)
\end{array}
\end{array}$$

Pre $(F\sm\{0\},\cdot)$ je úloha ešte jednoduchšia - jediná trojprvková grupa, ktorú sme stretli, je $(\Z_3,+)$. Tak iba porovnáme, či je to to isté.
$$
\begin{array}{cc}
\begin{array}{c|cccc}
\cdot & 1 & a & b \\\hline
1 & 1 & a & b \\
a & a & b & 1 \\
b & b & 1 & a
\end{array}
&
\begin{array}{c|cccc}
\cdot & 0 & 1 & 2 \\\hline
0 & 0 & 1 & 2 \\
1 & 1 & 2 & 0 \\
2 & 2 & 0 & 1
\end{array}
\end{array}$$

Distributívnosť.
Ostatné podmienky z definície poľa máme teda skontrolované, zostáva nám ešte distributívnosť. Pýtame sa, či pre ľubovoľné $x,y,z\in F$ platí
$$x\cdot(y+z)=x\cdot y+x\cdot z.\tag{D}$$
(Násobenie je komutatívne - stačí teda overovať jedno poradie.)

Pre štvorprvkovú množinu je azda ešte aj predstaviteľné, že by sme prešli všetky možnosti. Ale rýchlo si uvedomíme, že viaceré z nich vieme overiť naraz:

• Určite to funguje pre $x=0$ a $x=1$.
• Je to pravda aj v prípade, že $y=0$ alebo $z=0$.
• Pre sčitovanie zadané našou tabuľkou by sme mohli vidieť, že táto rovnosť platí aj pre $y=z$.

Spoiler:

• Ak $x=0$, tak $0\cdot(y+z)=0$ aj $0\cdot y=0\cdot z=0$. A máme teda rovnosť $0=0+0$, ktorá platí.
• Ak $x=1$, tak sa rovnosť $(D)$ zmení na $y+z=y+z$, čo tiež je evidentne pravda.
• Ak $y=0$ tak vlastne máme na jednej strane $x\cdot(0+z)=x\cdot z$ a na druhej strane $x\cdot 0+x\cdot z=0+x\cdot z=x\cdot z$. Prípad $z=0$ je podobný.
• Ak si uvedomíme, že pre každý prvok z našej množiny $F$ máme $a+a=0$, tak pre $y=z$ dostaneme
  \begin{align*}
  x(y+z)&=x(y+y)=x\cdot0=0\\
  xy+xz&=xy+xy=0
  \end{align*}

Zostalo nám teda už len pár možností - stačí sa pozerať na $x\in\{a,b\}$, $y,z\in\{1,a,b\}$ a súčasne $y\ne z$. (A navyše niektoré z nich si vieme ušetriť vďaka komutatívnosti. Prípadne nejakými ďalšími úvahami.)

Dá sa teda postupne prejsť ostatné možnosti, kde $x=a$.

Spoiler:

Pre $y=1$, $z=a$ máme
\begin{align*}
a(y+z)&=a(1+a)=ab=1\\
ay+az&=a\cdot1+a^2=a+b=1
\end{align*}

Pre $y=1$, $z=b$ máme
\begin{align*}
a(y+z)&=a(1+b)=a^2=b\\
ay+az&=a\cdot1+ab=a+1=b
\end{align*}

Pre $y=a$, $z=b$ máme
\begin{align*}
a(y+z)&=a(a+b)=a\cdot1=a\\
ay+az&=a^2+ab=b+1=a
\end{align*}

Zostávajúce tri možnosti sú symetrické - vyplývajú z komutatívnosti sčitovania.

Podobne by sme mohli prejsť všetky možnosti pre $x=b$. Prípadne tam si vieme nejako ušetriť robotu.

Spoiler:

Už vieme, že
$$a(y+z)=ay+az$$
platí pre všetky $y,z\in F$.

Vďaka tomu, že $a^2=b$ si môžeme uvedomiť, že ak vynásobíme obe strany $a$-čkom zľava, tak dostaneme
\begin{align*}
a^2(y+z)&=a^2y+a^2z\\
b(y+z)&=by+bz
\end{align*}

Pri istotu explicitne upozorním, že platnosť distributívnosti s $x=a$ sme v tomto odvodení použili ešte na jednom mieste. (Nielen ako rovnosť $a(y+z)=ay+az$, s ktorou sme začali.)

Spoiler:

Konkrétne sme ju použili tak tak, že sme prepísali pravú stranu vynásobenú $a$-čkom ako:
$$a(ay+az)=a^2y+a^2z.$$
Takýto krok je v poriadku - pretože pre násobenie prvkom $a$ už máme overenú distributívnosť.

Alebo ak to isté poviem ešte inak, tak sme začali s rovnosťou $a(y+z)=ay+az$. Ľavá resp. pravá strana vynásobená prvkom $a$ sa dajú upraviť takto:
\begin{align*}
a(a(y+z))&=(aa)(y+z)=a^2(y+z)=b(y+z)\\
a(ay+az)&\overset{(*)}=a(ay)+a(az)=a^2y+a^2z=by+bz
\end{align*}
Rovnosť označená $(*)$ je miesto, kde sme využili platnosť distributívnosti pri násobení $a$-čkom

Samozrejme, riešenie cez vyskúšanie všetkých možností nie je veľmi elegantné. Ako som už spomínal, neskôr budete vidieť spôsob definície takýchto polí, kde distributívnosť vyjde "zadarmo" resp. z toho, ako bude takéto pole skonštruované.

[Martin Sleziak]

Nejaké ďalšie poznámky
Drobnosti k veciam, ktoré sa vyskytli v odovzdaných riešeniach.

Rôzne písmenká nemusia nutne znamenať rôzne hodnoty
V zadaní som nevyžadoval, aby ste aj overili, či sme naozaj dostali pole. Niektorí ste sa o to pokúsili.
Takéto veci by asi už teraz (keď sme strávili veľa času s grupami a poľami) mali byť jasné, ale aj tak napíšem, že:

• Pri overovaní nejakej vlastnosti sa pýtam, že platí pre ľubovoľné prvky z $F$; nestačí si to vyskúšať pre jednu konkrétnu voľbu.
• Ak sú v nejakej rovnosti označené prvky rôznymi premennými $x$, $y$, $z$; zahŕňa to aj prípady, keď $x=y$ alebo $y=z$. Rôzne označené premenné nemusia nutne predstavovať rôzne objekty.

T.j. napríklad ak sa pýtame, či platí asociatívnosť násobenia, t.j.
$$(\forall x,y,z\in F) x\cdot(y\cdot z) = (x\cdot y)\cdot z$$
a ideme to overovať skúšaním jednotlivých možností, tak určite nestačí prekontrolovať či to funguje pre $x=a$, $y=b$, $z=1$; a ak áno, tak hneď prehlásiť, že je to asociatívna operácia.

A ak chceme preskúšať všetky možnosti, tak to zahŕňa napríklad aj prípad $x=y=a$, $z=b$. (T.j. $x$, $y$ môžu predstavovať ten istý prvok.)