General analysis for heap game, arbitrary number of piles

117 Views Asked by At

Here is a problem from my textbook:

Here is the general analysis for Heaps with an arbitrary number of piles.

Let $A$ be the number of $2$-chip piles, and let $B$ be the number of piles with either an even number (greater than $2$) of chips or a single chip. The winning positions are those in which either $A$ or $B$ is odd.

Prove that it is correct, and describe the winning strategy.

I have the bad luck of my copy of the textbook being defective and missing most of the pages from that particular chapter, so I don't even know the background/what's being referred to. Can someone tell me what this problem is even asking for, what it's saying? I'm not asking for someone to solve this problem for me, but rather just what this problem is even asking for in the first place, what all the terms being used mean.

1

There are 1 best solutions below

0
On BEST ANSWER

While I don't know exactly what the book is talking about, here is my best guess: The problem is most likely about the game Nim or one of its many variants. In Nim, two players take turns removing chips from piles, and the player that makes the last move wins. Each turn, a player selects a non-empty pile and removes a positive number of chips from it.

But there is a problem: The statement "The winning positions are those in which either $A$ or $B$ is odd" is not true for Nim. For example, a game with piles of sizes $4$, $8$, and $12$ is a losing position, but $A=0$ and $B=3$, so it should actually be a winning position. This makes me come to the conclusion that it can't be Nim, but maybe it's a variant of Nim. Variants may include restricting the number of chips a player is allowed to remove from a pile or allowing the player to remove chips from more than one pile.

Anyway, it would be great if you could provide some more context about this problem. For example, you could post an image of the book page on which the problem was written.