# Tag Info

## Hot answers tagged nim

16

TL;DR The rest of the post describes how I came to the conclusion above. Closer look Changing the rules Winning position How to win?

13

Call a position even if for every positive integer $n$, there are an even number of piles with exactly $n$ rocks. Call the position odd otherwise. Claim 1: If a position is odd, there is a move which results in an even position. From an odd position, find the largest $n$ such that there are an odd number of piles of size $n$, remove that pile, and for each $... 10 Alice wins if and only if Proof By induction. Firstly,$n=2$is obviously a winning position, while$n=3$is a losing position because the only allowed move is to remove one pebble, leaving the winning position$n=2$for Bob. Now assume that for all$n<2N$,$n$is a winning position if and only if$n$is even. Now$n=2N$is a winning position since ... 8 Let losses be on$F(x). F(1) = 3; F(2) = 5, F(x) = F(x-1) + F(x-2)$Suppose there are k marbles, and that all previous marbles N < k this Fibonacci formula decides correctly. The person to reduce the marbles to a Fibonacci number wins, as long as they remove less than half of that number to do so. If they cannot, then they treat the game as if the ... 8 This game is So in this case If we take "rational" to mean that when either player had a winning move they took it then Now So 8 Answer to the non-bonus part: Proof: Bonus part: From 12 Hence 7 Here's a little Python program to test it yourself: https://repl.it/repls/ScientificIdenticalPixels And here's C++ code written by user @im_so_meta_even_this_acronym https://ideone.com/SfMHqC 7 My answer offers no proof, only truth. This puzzle is related to the base Fibonacci representation of numbers. In base b, the nth digit represents$b^{n-1}$. In base Fibonacci, the nth digit represents the Fibonacci number$F_{n+1}$. For example,$101101_F$represents$F_{6+1}+F_{4+1}+F_{3+1}+F_{1+1}=13+5+3+1=22$. A number can have several equivalent base-... 7 You should To prove, let us first do the following 6 Even though the question says I'm Bob, I'd like to start by stating my intention to be the Quetzalcoatlus, thanks very much. I believe that the key to this game is that Example game: However, there is a major issue with this... Let me look at this from a different angle. 6 Partial strategy up to 11 candies. A is the player whose turn is next, B is the next player, and C is last. Don't think I can do it for 40 without turning this into a novel. But I have to say that, based on the name alone, Quetzalcoatlus sounds like a mean logician. (Much later:) Humm. The shortcut escapes me, even after solving the winning percentages for ... 6 Sprague-Grundy theory gives an algorithm for determining the winning strategy. First, we need to compute the nimbers of various pile sizes. This is a finite computation if$validmove[]$is finite. We will recursively define an array$nimber[]$. To start, define$nimber[0]=0$. For$n\geq 1$, we define $$nimber[n]=\mathrm{mex}\big\{nimber[n-k]: 1\leq k\in ... 6 This game is the famous NIM game: http://en.wikipedia.org/wiki/Nim The game has been fully analysed at the end of the 19th century. It has been discussed in some of the Martin Gardner books and in many other books on recreational mathematics. It might be the most popular mathematical game known all over the world. Google shows 300.000 pages that describe ... 6 As with pretty much all the nim variants, this one can be solved by starting from the end and working backwards. With the original total number of stones being an odd number (15, as given in the title) the players will have the same parity whenever there's an odd number of pebbles left, so it's easy to work out the best strategies: they are the ones that put ... 5 The strategy is to do a move that In particular, for 15 pebbles, your first move would be The reason this works is more interesting than with other single-pile nim variants. 4 The human ambassador cannot win. If either player moves to (0,x) where x>1, they lose because their opponent moves to (0,1). Similarly, (x,0) loses. (1,x) and (x,1) where x>0 also lose for the same reason. If the human ever moves to (2,2), the alien can move to (1,0), so the human loses. But if the alien moves to (2,2), the human has no move that doesn't ... 4 Here's a clearer statement of the rules. Each player has two options: Remove a stone on this turn. Remove a stone on the next turn. This is because not removing a stone causes one to be removed next turn. We now see that the game will last at most N+1 turns, because by then every player has removed a stone, whether or not they decided to delay or not. If ... 4 Using the same assumption as @Oray, Now 4 With this information: To be perfectly rational and impartial, only wanting to maximise their own chance of winning. and it is assumed that If there were 5 candles If there were 6 candles, If there were 7,8,9,10 candles, If there were 11 candles, If there were 12 candles, if there were 13-15 candles, if there were 16 candles, after this, I am ... 4 1. Proof that all games will end after a finite number of steps Proof by induction: Induction hypothesis H: (not known to be true yet) All games of exactly N piles will end in a finite number of steps. Induction step: If H is true for some N, it is also true for N+1. This is because out of the N+1 piles, one is the rightmost one. When a chip is removed ... 4 Let’s see: I assume that all numbers must be greater than or equal to zero, otherwise the possibilities become too painful. If that was the intention, I’ll look harder. 1 2 3 4 5 6 7 8 9 10 11 Therefore the only starting numbers that win for Alice are Bonus Part: 12 4 Code to find the pattern: https://ideone.com/O5S4Qu (The third number printed out on each line is the winning move if the player to move is in a winning position) 3 We have a winning strategy for: The first move is: 3 Any permutation of the rows and columns is treated as an "equivalent" board. Part 1: Matt chooses to go second. (Case A) If Ben takes 2 or 3 tokens, then Matt can turn it into a 2x2 board and win. (Case B) If Ben takes 1 token:$$\begin{array}{ccc} O & O & O \\ O & O & O \\ \_ & O & O \end{array}$$then Matt can take 2 tokens to ... 3 If you have to take exactly 5: If you can take a number from 1 up to 5 (which is what I'm assuming) If you can take a number from 0 up to 5 For the alternate game (which actually isn't too much harder) 3 Reasoning: 3 I will assume that Given several equally desirable options, the players will randomly choose one. Doing so, it is easy to work out what happens when there are$n$candies; If$n=1$, then player 1 certainly loses. If$n=2$, then player 2 certainly loses. If$n=3\$, then player 1 is indifferent between taking one and two candies, so player 2 or 3 loses ...

3

Second (but completed) answer, once again building of Sleafar's answer. How?

3

User hexomino already figured out the puzzle, and managed to actually find the very complicated path that was exactly how I came up with the game. To recap: The game itself is a lot easier to play than that, though, so I'm posting this self-answer to show how. First, it's very useful to note that in a given board position, every move is uniquely defined by ...

2

I'm not sure this answer works, but I think that We first determine a list of losing numbers. We draw a table with 2 columns and start with a number 3. Losing Previous 3 Now we write the greatest number less than half this number on the right hand side. Losing Previous 3 1 Now we add both of them and find the next number to use in the new ...

Only top voted, non community-wiki answers of a minimum length are eligible