?? nim-value -- from wolfram mathworld.htm
字號:
title="Created, developed, and nurtured by Eric Weisstein with contributions from the world's mathematical community"
height=49
alt="Created, developed, and nurtured by Eric Weisstein with contributions from the world's mathematical community"
src="Nim-Value -- from Wolfram MathWorld.files/created-by.gif"
width=120 border=0 name=Image1></A>
</DIV></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><MAP id=SideMap
name=SideMap><AREA shape=RECT alt="Wolfram Research" coords=11,31,97,46
href="http://www.wolfram.com/"><AREA shape=RECT alt="Eric W. Weisstein"
coords=3,3,118,30 href="http://mathworld.wolfram.com/author.html"></MAP><!-- End Sidebar --></TD>
<TD><IMG alt="" src="Nim-Value -- from Wolfram MathWorld.files/spacer.gif"
width=30></TD>
<TD>
<TABLE width="100%">
<TBODY>
<TR>
<TD vAlign=top align=left width="100%">
<DIV class=navbar><A
href="http://mathworld.wolfram.com/topics/RecreationalMathematics.html">Recreational
Mathematics</A> > <A
href="http://mathworld.wolfram.com/topics/Games.html">Games</A> > <A
href="http://mathworld.wolfram.com/topics/GeneralGames.html">General
Games</A> <BR><A
href="http://mathworld.wolfram.com/topics/AppliedMathematics.html">Applied
Mathematics</A> > <A
href="http://mathworld.wolfram.com/topics/GameTheory.html">Game
Theory</A> <BR></DIV><BR>
<TABLE cellSpacing=0 cellPadding=0 border=0>
<TBODY>
<TR>
<TD class=title vAlign=baseline><SPAN
class=nowrap>Nim-Value</SPAN></TD></TR>
<TR>
<TD vAlign=top><SPAN class=nowrap><IMG height=3 alt=""
src="Nim-Value -- from Wolfram MathWorld.files/underline.gif"
width="100%"><IMG height=3 alt=""
src="Nim-Value -- from Wolfram MathWorld.files/underline.gif"
width=20></SPAN></TD>
<TD><IMG height=15 alt=""
src="Nim-Value -- from Wolfram MathWorld.files/spacer.gif"></TD></TR></TBODY></TABLE></TD></TR>
<TR vAlign=top>
<TD width="100%"><A href="http://mathworld.wolfram.com/contact/"
target=_blank><IMG height=25 alt="COMMENT On this Page"
src="Nim-Value -- from Wolfram MathWorld.files/comment.gif" width=98
border=0></A><A
href="http://mathworld.wolfram.com/notebooks/Games/Nim-Value.nb"><IMG
height=26 alt="DOWNLOAD Mathematica Notebook"
src="Nim-Value -- from Wolfram MathWorld.files/dnld-nb.gif"
width=119 border=0></A>
<P class=Text>Every position of every <A class=Hyperlink
href="http://mathworld.wolfram.com/ImpartialGame.html">impartial
game</A> has a nim-value, making it equivalent to a <A
class=Hyperlink
href="http://mathworld.wolfram.com/Nim-Heap.html">nim-heap</A>. To
find the nim-value (also called the Sprague-Grundy number), take the
<A class=Hyperlink
href="http://mathworld.wolfram.com/Mex.html">mex</A> of the
nim-values of the possible moves. The nim-value can also be found by
writing the number of counters in each heap in <A class=Hyperlink
href="http://mathworld.wolfram.com/Binary.html">binary</A>, adding
corresponding binary digits (mod 2), and interpreting the resulting
<A class=Hyperlink
href="http://mathworld.wolfram.com/Binary.html">binary</A> string as
a <A class=Hyperlink
href="http://mathworld.wolfram.com/Decimal.html">decimal</A> number.
</P>
<P class=Text>If at any point in the game, the nim-value is 0 for a
given player, the position is <A class=Hyperlink
href="http://mathworld.wolfram.com/Safe.html">safe</A> (i.e., he
will always win if he plays correctly); otherwise, it is <A
class=Hyperlink
href="http://mathworld.wolfram.com/Unsafe.html">unsafe</A> (i.e., he
will always lose if the other player plays correctly). With two
heaps in the game of <A class=Hyperlink
href="http://mathworld.wolfram.com/Nim.html">nim</A>, the only safe
positions are <IMG class=inlineformula height=15 alt=(x,x)
src="Nim-Value -- from Wolfram MathWorld.files/inline1.gif" width=32
border=0>. With three heaps (assuming nim-heaps of maximum size 7),
the safe positions are (1, 2, 3), (1, 4, 5), (1, 6, 7), (2, 4, 6),
(2, 5, 7), (3, 4, 7), and (3, 5, 6). For four nim-heaps of maximum
size 7, the safe positions are <IMG class=inlineformula height=15
alt=(x,x,x,x)
src="Nim-Value -- from Wolfram MathWorld.files/inline2.gif" width=62
border=0>, <IMG class=inlineformula height=15 alt=(x,x,y,y)
src="Nim-Value -- from Wolfram MathWorld.files/inline3.gif" width=62
border=0>, and (1, 2, 4, 7), (1, 2, 5, 6), (1, 3, 4, 6), (1, 3, 5,
7), (2, 3, 4, 5), (2, 3, 6, 7), and (4, 5, 6, 7). The position (1,
3, 5, 7) corresponds to the beginning state for the game <A
class=Hyperlink
href="http://mathworld.wolfram.com/Marienbad.html">Marienbad</A>,
which is therefore an <A class=Hyperlink
href="http://mathworld.wolfram.com/UnfairGame.html">unfair game</A>.
</P>
<FORM name=SearchLinks action=http://mathworld.wolfram.com/search/
method=post>
<P class=CrossRefs><SPAN class=crosslinkheader>SEE ALSO:</SPAN> <A
class=Hyperlink
href="http://mathworld.wolfram.com/GrundysGame.html">Grundy's
Game</A>, <A class=Hyperlink
href="http://mathworld.wolfram.com/ImpartialGame.html">Impartial
Game</A>, <A class=Hyperlink
href="http://mathworld.wolfram.com/Marienbad.html">Marienbad</A>, <A
class=Hyperlink
href="http://mathworld.wolfram.com/Mex.html">Mex</A>, <A
class=Hyperlink
href="http://mathworld.wolfram.com/Nim.html">Nim</A>, <A
class=Hyperlink
href="http://mathworld.wolfram.com/Safe.html">Safe</A>, <A
class=Hyperlink
href="http://mathworld.wolfram.com/Unsafe.html">Unsafe</A>. <INPUT
type=hidden value=http://mathworld.wolfram.com/Nim-Value.html
name=as_lq><A
href="javascript:document.forms.SearchLinks.submit();">[Pages Linking Here]</A>
</P></FORM>
<P><IMG height=3 alt=""
src="Nim-Value -- from Wolfram MathWorld.files/underline.gif"
width=300> </P><SPAN class=crosslinkheader>REFERENCES:</SPAN>
<P class=Reference>Ball, W. W. R. and Coxeter, H. S. M. <I><A
class=Hyperlink
href="http://www.amazon.com/exec/obidos/ASIN/0486253570/ref=nosim/weisstein-20">Mathematical
Recreations and Essays, 13th ed.</A></I> New York: Dover, pp. 36-38,
1987. </P>
<P class=Reference>Grundy, P. M. "Mathematics and Games."
<I>Eureka</I> <B>2</B>, 6-8, 1939. </P>
<P class=Reference>Sprague, R. "躡er mathematische Kampfspiele."
<I>T鬶oku J. Math.</I> <B>41</B>, 438-444, 1936. </P>
<DIV><IMG height=3 alt=""
src="Nim-Value -- from Wolfram MathWorld.files/underline.gif"
width=300><BR><BR>
<DIV><SPAN class=crosslinkheader>LAST MODIFIED:</SPAN><SPAN
class=citation> <A
href="http://mathworld.wolfram.com/whatsnew/2002/04.html#26">April
26, 2002</A></SPAN> </DIV><BR><SPAN class=crosslinkheader>CITE THIS
AS:</SPAN><BR>
<P class=citation><A
href="http://mathworld.wolfram.com/about/author.html">Weisstein,
Eric W.</A> "Nim-Value." From <A
href="http://mathworld.wolfram.com/"><I>MathWorld</I></A>--A Wolfram
Web Resource. <A
href="http://mathworld.wolfram.com/Nim-Value.html">http://mathworld.wolfram.com/Nim-Value.html</A>
</P><IMG height=3 alt=""
src="Nim-Value -- from Wolfram MathWorld.files/underline.gif"
width=300><BR>
<P class=copyright>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -