|
|
|
|
| View previous topic :: View next topic |
| Author |
Message |
Samadhi
+1
|
 Posted: Tue Apr 01, 2008 2:26 pm Post subject: 1 |
 |
|
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?
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between. |
|
| Back to top |
|
 |
lostdummy
Daedalian Member
|
| Posted: Tue Apr 01, 2008 5:51 pm Post subject: 2 |
|
|
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 |
|
| Back to top |
|
|
L'lanmal
Daedalian Member
|
| Posted: Tue Apr 01, 2008 9:09 pm Post subject: 3 |
|
|
| Martin Gardner told me about this one some time ago. Good names are descriptive. |
|
| Back to top |
|
|
Samadhi
+1
|
| Posted: Wed Apr 02, 2008 3:29 am Post subject: 4 |
|
|
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.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between. |
|
| Back to top |
|
|
L'lanmal
Daedalian Member
|
| Posted: Mon Sep 20, 2010 9:57 pm Post subject: 5 |
|
|
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.) |
|
| Back to top |
|
|
Antrax
ESL Student
|
| Posted: Tue Sep 21, 2010 6:23 am Post subject: 6 |
|
|
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.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick! |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
