From a4d473bfe1d1b77ebc0a6b061d4a126779f48c31 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc55.atis-stud.uni-karlsruhe.de>
Date: Mon, 24 Nov 2014 14:11:14 +0100
Subject: Grundy

---
 math/math.tex | 8 ++++++++
 1 file changed, 8 insertions(+)

(limited to 'math/math.tex')

diff --git a/math/math.tex b/math/math.tex
index 973103a..71f9c0e 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -31,3 +31,11 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$.
 
 \subsection{Primzahlsieb von Eratosthenes}
 \lstinputlisting{math/primeSieve.cpp}
+
+\subsection{Satz von \textsc{Sprague-Grundy}}
+Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
+\[
+	g\left(X\right) := \min\{ \mathbb{Z}_0^+ \textbackslash \{g\left(Y\right)~|~Y \text{ von } X \text{ aus direkt erreichbar}\}\} 
+\]
+$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\\\
+Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
-- 
cgit v1.2.3

