-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathkap01.tex
173 lines (138 loc) · 8.96 KB
/
kap01.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
\chapter{Pravidla hry Mastermind}
\subsubsection{Značení:}
V práci budeme používat následující značení:
\begin{itemize}
\item Nechť $S$ je konečná množina. Potom $|S|$ značíme její mohutnost, tedy počet prvků.
\item Formulí $\arg$ myslíme funkci, která vrátí prvek nabývající extrémní hodnoty popsané v navazujícím vzorci. Např $1 = \arg\max \{-x \mid x \in \mathbb{N}\}$.
\item Nechť $K$ je množina. Symbolem $\mathcal{P}(K)$ značíme množinu všech podmnožin $K$.
\end{itemize}
Zavedeme definice potřebné pro vysvětlení průběhu hry Mastermind. Nejprve vymezíme prostor, se kterým pak dále budeme pracovat.
%množinu \[ \{ u = u_1u_2 \dots u_n \hspace{2px} \mid \hspace{2px} u_i \in \{1, 2, 3, \dots, k\}, \hspace{2px} i \in \{1, 2, 3, \dots, n\} \}\]
\begin{definice}[Prostor kódů]\label{def01:1}
Nechť $n \in \N $, $k \in \N $. Potom prostor kódů o $n$ pozicích a $k$ barvách definujeme jako množinu $H_{n,k} = \{1, 2, 3, \dots, k\}^n$. Prvek $u = u_1u_2\dots u_n \in H_{n,k}$ nazýváme kód.
\end{definice}
%Číslo $n \in \N $ budeme nazývat počet pozic a $k \in \N $ počet barev. Číslu $u_i \in \{1, 2, 3, \dots, k\}$ budeme říkat barva.
Pro nějaké dva kódy z $H_{n,k}$ zavedeme definici ohodnocení bílými a černými kolíčky inspirovanou D. Knuthem \cite{donald_e__knuth_1977} a D. Greenwellem \cite{greenwell}. Ohodnocení dává určitou informaci o tom, jak se dva kódy podobají.
% Označíme-li dále $N = \sum_{j = 1}^k \min(n_j, m_j)$.
% Množinu všech ohodnocení v $H_{n,k}$ značíme $S$.
\begin{definice}[Ohodnocení]\label{ohodnoceni}
Nechť $u,v \in H_{n,k}$ jsou kódy, potom ohodnocením kódů $u$ a $v$ myslíme uspořádanou dvojici $(b,w) \in \N_0 \times \N_0$, kde $b$ a $w$ jsou počty černých a bílých kolíčků definované následovně. Počet černých kolíčků je počet prvků množiny $\{i \in \{1,\dots, n\}\mid u_i = v_i \}$. Označme $n_j$ počet výskytů barvy $j$ v kódu $u$, $m_j$ počet výskytů barvy $j$ v kódu $v$. Počet bílých kolíčků je hodnota $w = \sum_{j = 1}^k \min(n_j, m_j)-b$.
Dále definujeme funkci $s \colon H_{n,k} \times H_{n,k} \to \mathbb{N}_0\times \mathbb{N}_0$, která dvojici kódů přiřadí jejich ohodnocení.
\end{definice}
Počet černých kolíčků pro nějaké dva kódy značí počet pozic, na kterých mají tyto kódy shodnou barvu. Bílé kolíčky značí počet zbývajících pozic v prvním kódu, které se shodují s nějakou jinou pozicí v druhém kódu v barvě. Nejprve se vyhodnotí počet černých kolíčků a potom až počet bílých tak, aby každá pozice v obou kódech přispívala maximálně k jednomu kolíčku. K popisu hry Mastermind se nám bude hodit definice, která kódu $u$ přiřadí ohodnocení vzhledem k neznámému kódu $v$.
\begin{definice}[Ohodnocení vzhledem ke kódu]
Nechť $v \in H_{n,k}$ je kód. Definujeme funkci
\begin{align*}
s_v \colon H_{n,k} &\to \mathbb{N}_0\times \mathbb{N}_0 \\
u &\mapsto s(u,v)
\end{align*}
Pro $u\in H_{n,k}$ definujeme ohodnocení $u$ vzhledem k $v$ jako $s_v(u)$.
\end{definice}
Triviálním pozorováním je fakt, že pro libovolné dva kódy je součet černých a bílých kolíčků v jejich ohodnocení maximálně $n$. To plyne z toho, že hodnota $\sum_{j = 1}^k \min(n_j, m_j)$ je menší nebo rovna $n$. Zároveň v prostoru $H_{n,k}$ neexistuje ohodnocení $(n-1,1)$. Pokud se totiž kódy schodují právě na $n-1$ pozicích, musí se na zbývající pozici lišit.
\begin{tvrz}\label{tvrzohodnoceni}
Nechť $n \in \N$, $k \in \N, k>2$. Potom pro všechna $(b,w)\in \mathbb{N}_0 \times \mathbb{N}_0,\hspace{5px} b + w \leq n$ existuje dvojice kódů $u,v \in H_{n,k}$ taková, že jejich ohodnocení je $(b,w)$.
\end{tvrz}
\begin{dukaz}
%Ukážeme, že pro každé $b$ a $w$, $b+w \leq n$ existují dva kódy $u,v \in H_{n,k}$, takové, že $s(u,v) = (b,w)$.
Situaci rozdělíme na dva případy podle parity $w$. Nechť napřed $w$ je sudé. Kódy $u$ a $v$ zvolíme následovně:
\[
u =
\underbrace{11\dots1}_{b}
\underbrace{11\dots1}_{\frac{w}{2}}
\underbrace{22\dots2}_{\frac{w}{2}}
\underbrace{11\dots1}_{n-b-w}
\]
\[
v =
\underbrace{11\dots1}_{b}
\underbrace{22\dots2}_{\frac{w}{2}}
\underbrace{11\dots1}_{\frac{w}{2}}
\underbrace{22\dots2}_{n-b-w}
\]
Vidíme, že počet černých kolíčků kódů $u$ a $v$ je $b$. Počet bílých kolíčků $w'$ je potom
\begin{align*}
w' &= \min\left(n - \frac{w}{2}, b + \frac{w}{2}\right) + \min\left(\frac{w}{2}, n - b - \frac{w}{2}\right) - b \\
&= \min\left(n - b - \frac{w}{2}, \frac{w}{2}\right) + \min\left(\frac{w}{2}, n - b - \frac{w}{2}\right) \\
&= 2\cdot\min\left(\frac{w}{2}, n - b - \frac{w}{2}\right) = w
\end{align*}
V poslední rovnosti jsme využili předpokladu, že $b+w \leq n$, a tedy $\frac{w}{2} \leq n - b - \frac{w}{2}$
Pro $w$ liché zvolíme kódy následovně:
\[
u =
\underbrace{11\dots1}_{b}
\underbrace{11\dots1}_{\frac{w-1}{2}}
\underbrace{22\dots2}_{\frac{w-1}{2}-1}
2
3
\underbrace{11\dots1}_{n-b-w}
\]
\[
v =
\underbrace{11\dots1}_{b}
\underbrace{22\dots2}_{\frac{w-1}{2}}
\underbrace{11\dots1}_{\frac{w-1}{2}-1}
3
1
\underbrace{22\dots2}_{n-b-w}
\]
Počet černých kolíčků je $b$. Počet bílých kolíčků $w'$ kódů $u$ a $v$ je potom
\begin{align*}
w' = \min\left(n-w+\frac{w-1}{2}, b + \frac{w-1}{2}\right) + \min\left(\frac{w-1}{2}, \frac{w-1}{2} + n-b-w\right) + \\ +\min(1,1) - b
= b + \frac{w-1}{2} + \frac{w-1}{2} + 1 - b = w
\end{align*}
\end{dukaz}
Silnější tvrzení platí pro případ se dvěma barvami.
\begin{tvrz}\label{tvrzohodnoceni2}
Nechť $n \in \N, k=2$. Nechť dále $u, v \in H_{n,k}$ jsou kódy s ohodnocením $(b,w)$. Potom $b + w \leq n, \hspace{5px} (b,w) \neq (n-1,1)$ a $w$ je sudé.
\end{tvrz}
\begin{dukaz}
$b + w \leq n, \hspace{5px} (b,w) \neq (n-1,1)$ platí obdobně jako v důkazu tvrzení \ref{pozmozneohodnoceni}. Kódy $u$ a $v$ lze permutací pozic dostat do následujícího tvaru
\[
u =
\underbrace{11\dots1}_{c}
\underbrace{22\dots2}_{d}
\underbrace{11\dots1}_{x}
\underbrace{22\dots2}_{y}
\]
\[
v =
\underbrace{11\dots1}_{c}
\underbrace{22\dots2}_{d}
\underbrace{22\dots2}_{x}
\underbrace{11\dots1}_{y}
\]
kde $b = c + d$.
Potom
\begin{align*}
w &= \min(c + x, c + y) + \min(d + y, d + x) - b =\\
&= \min(x, y) + \min(y, x) = 2\cdot \min(x, y)
\end{align*}
\end{dukaz}
%Nyní dokážeme, existenci ohodnocení pro nějaké $(b,w)$. Nechť napřed $w = 0$. Zvolme prvních $b$ pozic v obou kódech na barvu $1$. Protože $k>2$, můžeme pro zbylé pozice v prvním kódu zvolit barvu $1$ a pro zbylé pozice ve druhém kódu zvolit barvu $2$. Snadným ověřením z definice zjistíme, že tyto dva kódy mají ohodnocení $(b,0)$. Nechť nyní $w > 0$ a $b+w < n$. První kód vytvoříme takto. Položme prvních $b$ pozic na barvu $1$. Položme dále dalších $w$ pozic v prvním kódu střídavě $1212\dots$ a zbylé pozice v prvním kódu vyplníme třetí barvou. Druhý kód vyplníme následovně. Položme prvních $b$ pozic na barvu $1$. Dalších $w + 1$ pozic zvolíme jako $212121\dots$ a kód doplníme barvou dva. Pokud $b+w = n$ a $w$ je sudé. Náš postup bude fungovat s jedinou obměnou a to, že posledních posledních $w$ pozic druhého kódu $2121\dots$. Pokud $w$ je liché, zvolíme poseldních $w$ pozic prvního kódu $1212\dots3$ a posledních $w$ pozic druhého kódu $3121\dots$.
%V příkladu níže je ukázka konstrukce kódů s daným ohodnocením.
%\begin{prikl}
% Pro ohodnocení $(b,w), w > 0, b+w < n$ kódy mohou vypadat například takto:
% \[111111,1212121,33333\]
% \[111111,21212121,2222\]
% Pro případ $b+w = n$ a $w$ liché lze kódy sestavit takto:
% \[111111,1212123\]
% \[111111,3121212\]
%\end{prikl}
Nyní jsme připraveni definovat hru Mastermind.
\section{Průběh hry Mastermind}
Nechť $n \in \N $, $k \in \N$. [n,k]-Mastermind je hra pro dvě osoby, zadavatele a hráče,
% Šlo by oba hráče pojmenovat
% Cílem hry je nalézt tajný kód na co nejmenší počet pokusů.
probíhající podle následujícího schématu.
\begin{enumerate}
\item Zadavatel vytvoří tajný kód $v \in H_{n,k}$.
\item Hra dále probíhá po kolech $i = 1,2,3,\dots$
\begin{enumerate}
\item Hráč určí kód (tah, pokus) $u_i \in H_{n,k}$.
\item Zadavatel ohodnotí pokus $u_i$ vzhledem k tajnému kódu $v$.
\end{enumerate}
\item Hra končí v případě, že pokus je ohodnocen $n$ černými kolíčky (zadaný kód se shoduje s tajným kódem).
\end{enumerate}
Cílem hry [n,k]-Mastermind je nalézt tajný kód na co nejmenší počet pokusů. V případě, že hráč neopakuje kódy v pokusech, hra jistě skončí.
% vyčerpáním všech možností pro tajný kód.
% přidat různé varianty hry mastermind??? např statická verze, hra pouze s kandidáty atd.