11
$\begingroup$

(I discovered this in high school, sent it off to a journal, never heard back, and forgot about it. I've never found anyone else who appeared to know about it; the combinatorial game theorists I've mentioned it to have all been surprised.)

It turns out that the set of second-player wins in $d$-pile Nim (P-positions), considered as a point in $d$-space, has a Sierpinski structure.

This is only obvious in dimensions greater than 2. With $d=3$, the set of P-positions is a Sierpinski pyramid; in higher dimensions it's a demihypercube.

Since P-positions are those with coordinates which xor to 0, I figure this has got to be related to other relationships between Sierpinski's triangle and xor - for example, the fact that the Sierpinksi triangle is generated by taking $\{(x, y) \in \mathbb{N}^d \mid x+y = x \oplus y\}$ (where $\oplus$ denotes xor) (*). I haven't seen that fact mentioned anywhere, come to think, although it's an easy consequence of a paper by Fraenkel and Kontorovich; that paper is also the only other to relate Nim and the Sierpinski triangle that I know of, but in a very different way that I do, as far as I can tell.

(*) In fact this is easily implied by my result by considering just the plane $x+y=z$, but it feels like there should be something deeper here, some connection in the other direction.

So my question is: does anyone know anything about this relationship between the Sierpinski gasket and Nim? Is anyone even aware of it? Can anyone draw connections between this relationship and other known facts about the Sierpinski gasket?

Improve this question
$\endgroup$
3
  • $\begingroup$ The paper I mentioned. Don't have enough rep to post the link inline; someone should feel free to edit it in. $\endgroup$
    – Bakkot
    Commented Oct 16, 2014 at 6:22
  • 1
    $\begingroup$ You might perhaps be interested in this: arxiv.org/abs/1408.5937 Not nim-related, but sierpinski-related. Note that the sierpinski triangle appear in many plases: Pascals triangle, and also in the Tower of Hanoi. $\endgroup$
    – Per Alexandersson
    Commented Oct 16, 2014 at 7:41
  • $\begingroup$ $x+y=x\oplus y$ iff adding $x$ and $y$ has no carries, so the fact that you mention about that is -- if I'm understanding correctly what you mean by it -- a direct consequence of Kummer's theorem. $\endgroup$
    – Harry Altman
    Commented Jun 24, 2015 at 17:11

2 Answers 2

Reset to default
7
$\begingroup$

Besides Fraenkel and Kontorovich, some relationships between the Sierpinski gasket and Nim are discussed in the papers: https://www.rose-hulman.edu/mathjournal/archives/2009/vol10-n2/paper12/v10n2-12pd.pdf (Variants of the Game of Nim that have Inequalities as Conditions, by Toshiyuki Yamauchi, Taishi Inoue and Yuuki Tomari -- published in http://www.rose-hulman.edu/mathjournal/v10n2.php) and http://www.mi.sanu.ac.rs/vismath/miyaderasept2009/index.html (Combinatorial Games and Beautiful Graphs Produced by them, by Masakazu Naito et al., -- published in Visual Mathematics, Volume 11, No. 3, 2009).

Improve this answer
$\endgroup$
1
  • $\begingroup$ As far as I can tell, they just plotted the P-positions for their variant of Nim and noticed it was Sierpinski ish, without providing proof or reasoning (or noticing that it applied to regular Nim or higher dimensions). The second link is the same thing as the first, as far as I can tell (the authors of the first are coauthors on the second). Still, nice find! I hadn't seen anyone else discussing this. $\endgroup$
    – Bakkot
    Commented Oct 16, 2014 at 7:39
1
$\begingroup$

Although the connection between Nim and the Sierpinski Gasket has not been explicitly proven (or I have not seen it), I would hesitate to believe that no one has thought of it before. The reason being the obvious connection Nim and the bitwise xor.

It turns out that the bitwise xor is intricately connected with Sierpinski Gasket. I am going to just briefly overview a few links that I happen to know of:

Rule 90 Cellular Automata

The rule 90 cellular automata is an elementary cellular automata (ECA). An ECA is essentially an evolving array of 0s and 1s with a set rule for the evolution. In the case of rule 90 each cell is determined by the xor of the two cell to the immediate left and right (in the previous generation). Anyways, this automata forms a Sierpinski Gasket. I think that Wikipedia has a good article on this.

Pascals Triangle

This connection is really because of Pascal's triangle. It is very well known that Pascal's triangle in mod 2 creates a Sierpinski Gasket. Pascal's triangle is generated by writing the sum of every consecutive pair of elements in the bottom row. Summing in mod 2 is equivalent to the xor. This website had some nice pictures.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .