CS Problem

Pre-College Issues High School Life
1

<p>Hi,</p>

<p>In the game of Nim, we have multiple "stacks" of "coins." Two players take turns taking as many coins as they please (at least one, though) from a single stack. The object is to take the last coin. It turns out that the (time-efficient) solution to a particular configuration deals with the parity of the binary representation of the number of coins in each stack. </p>

<p>I chewed on this problem for a while, and came up with my one problem: consider an m x n lattice of coins. Two players take turns taking as many coins as they please from a single row OR column. How can one determine whether an arbitrary board is a "winning" board or a "losing" board? (The empty board is considered a losing board.) </p>

<p>I've "solved" the problem in Prolog using recursive descent, but that's a ridiculous way to solve a board (solving a 15 x 15 board would take until the Second Coming). Dynamic programming promises a faster solution, but it uses an excessive amount of memory: 2 ^ (m x n) bits.</p>

2

<p>sorry...typo: "came up with my OWN (not ONE) problem"</p>

<p>just to note, taking different coins from the same row or column results in different board configurations, making this an evil recursive descent problem</p>

3

<p>Hm... I thought it was Nihm... Hm...</p>

<p>:)</p>

4

<p>Nim...Nihm...either way, the point in question is the algorithm, not the game's name :)</p>