# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
Antrax
Posted: Tue Sep 21, 2010 6:23 am    Post subject: 1

Samadhi, your code won't be optimized until you a) stop using Java and b) use dynamic programming over recursion. This particular recursion is so simple that you could just use a stack to eliminate the function call, but that would still leave you with calculating the same input many times.
L'lanmal
Posted: Mon Sep 20, 2010 9:57 pm    Post subject: 0

I just noticed this thread was somewhat unfinished as far as the mathematical solution.

This game (credited to Robert E. Gaskell) is described in Chapter 13 of Martin Gardner's book Mathematical Circus, originally from his Scientific American columns. The generic solution given involves expressing the number as a sum of non-consecutive fibonacci numbers --- hense the name. In this case, the largest fibonacci number under 31 is 21, leaving 10. Largest under 10 is 8, leaving 2. So, 31=21+8+2 and 2 is a winning play. (8+2=10 is as well, as you found.)
Posted: Wed Apr 02, 2008 3:29 am    Post subject: -1

lostdummy, you got it. My program found those two answers.
Here's my code (slightly optimized):
Code:
public class blah {
public static void main(String[] args) {
for (int i = 10; i>0;i--){
if (checkMove(i, 31)) System.out.println(i);
}
System.out.println("done");  //Only here so you know the program did something
}
static boolean checkMove(int take, int remain){
if ((remain-=take)<=0) return true;
if (remain <= take<<1) return false;
int i = Math.max(1, Math.min((remain-1)/3, take<<1));
for (int j = i; j>0; j--)
if (checkMove(j, remain)) return false;
return true;
}
}

The recursive call is based on the fact that for your move to be good, all your opponents answering moves must fail, and for a move to fail at least one answering move must succeed.
You won't take more than a third unless it's the remainder.
L'lanmal
Posted: Tue Apr 01, 2008 9:09 pm    Post subject: -2

lostdummy
Posted: Tue Apr 01, 2008 5:51 pm    Post subject: -3

regarding problem, only thing that i see as problematic is one single word: ONLY should be removed from "what is the only move you can make...", since there are two moves that grant victory, 2 and 10 .

Quote:
I honestly don't know how to solve it mathematically but my CS solution was 7 lines.

As for method that I used to solve, I used two methods and both were computer calculations, although they are different in level of optimization.

If your "CS solution" means "Computer Simulation", that would be probably similar to my 1st method, where i recursivelly tried every possible move. very short to implement, but very unoptimized - for calculating position with 31 stones and 9 as last move (as in problem) it needed 23,485,165 calls to inner calculation (or 418,503 if i dont try to count number of different best moves).

But it is still "calculation" and not "simulation" since it return exact, mathematically correct number every time.

My 2nd method is what would probably pass as "how to solve it mathematically". There I implement modified Mexx/Grundy numbers approach, which is standard for bipartisan independend games like Nim. Basically, you start from losing position, and expand set of such positions that are "losing" for player to move next. Goal for player on move is to leave for next player one position from such set.

Calculation in this case is MUCH shorter, since there are about 820 possible positions in this game if we start with 40 stones. Basically I modified usual approach since position here is combination of number of stones and number of possible removals. Theoretically that would result in 40*40 "positions", but since you can not remove 40 if you have 7 stones, that is actually about 40*40/2 positions , which is around 800. Further optimization is possible, since there is no point in playing more than half of stones (unless winning move), since that would guarantee next player to win. So number of positions could be reduced to about 400 - but since difference between 800 and 400 could be ignored when solving by computer, I didnt implement that one ;p

And calculating which of those 800 positions are "losing" (having modified Grundy number 0) is very fast and even more straightforward than recursive calling. Another important benefit is that you only calculate once for entire game. So when you need to get next best move, ot to play entire game against opponent, you dont need to recalculate anything, while with first (recursive) approach it need to be calculated again on every move.

But this 2nd approach is still "calculation" just like first one, only it is better optimized - although every calculation is in essence "mathematical solution", only with several, usually repeating, steps ;p
Posted: Tue Apr 01, 2008 2:26 pm    Post subject: -4

Problem of the Fortnight! This one was for 2/15/2008.
Problem of the Fortnight wrote:

Fibonacci Nim is a two player game, played as follows. Players
take turns removing stones from a pile (and discarding the removed stones).
They must remove at least one stone, but no more than twice what their opponent
removed immediately before. Whoever removes the last stone(s) wins, and the
first player may remove any number of stones (except all of them).

Here's a sample game, starting with 10 stones:
A removes 2, leaving 8
B may remove between 1 and 4, chooses to remove 1, leaving 7
A may remove either 1 or 2, chooses to remove 1, leaving 6
B may remove either 1 or 2, chooses to remove 2, leaving 4
A may remove between 1 and 4, chooses to remove 4, A wins.

You are playing with your friend, starting with 40 stones. Your friend went
first, and removed nine (which was a mistake). There are now 31 stones. What is the only move you can make, to guarantee victory?

I honestly don't know how to solve it mathematically but my CS solution was 7 lines. And it suggests that something is wrong with the puzzle description. What might that be?