// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (9 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 301 Solution

Project Euler 301 Solution

Project Euler 301: Finding Nim positions consisting of heap sizes n, 2n and 3n for n ≤ 230 that result in a losing game


Problem Description

Nim is a game played with heaps of stones, where two players take it in turn to remove any number of stones from any heap until no stones remain.

We’ll consider the three-heap normal-play version of Nim, which works as follows:
– At the start of the game there are three heaps of stones.
– On his turn the player removes any positive number of stones from any single heap.
– The first player unable to move (because no stones remain) loses.

If (n1,n2,n3) indicates a Nim position consisting of heaps of size n1, n2 and n3 then there is a simple function X(n1,n2,n3) — that you may look up or attempt to deduce for yourself — that returns:

  • zero if, with perfect strategy, the player about to move will eventually lose; or
  • non-zero if, with perfect strategy, the player about to move will eventually win.

For example X(1,2,3) = 0 because, no matter what the current player does, his opponent can respond with a move that leaves two heaps of equal size, at which point every move by the current player can be mirrored by his opponent until no stones remain; so the current player loses. To illustrate:
– current player moves to (1,2,1)
– opponent moves to (1,0,1)
– current player moves to (0,0,1)
– opponent moves to (0,0,0), and so wins.

For how many positive integers n ≤ 230 does X(n,2n,3n) = 0 ?

Analysis

Classic use of the Fibonacci sequence. Just find the Fibonacci Number FL+2, where L is the 2’s exponent.

Project Euler 301 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 301 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|2178309|

Afterthoughts

Project Euler 301 Solution last updated

Discussion

No comments yet.

Post a comment