# Tag Info

15

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 Answer to the non-bonus part: Proof: Bonus part: From 12 Hence 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 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 You should To prove, let us first do the following 7 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 ... 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$. 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 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 ... 5 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-... 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 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 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 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 ... 2 One approach to this problem whereby we can deduce the answer without any initial guessing is to calculate the nimber$f(n)$of a game starting with$n\$ pebbles in a single pile. This is helpful because our game has the property that, when we have two piles, its the same as if we had two games simultaneously, where each player chose to play in one, and the ...

1

Jafe posted something very close to my intended answer, and it may be that he is correct, and I've made a mistake somewhere. To compare notes, here's my intended solution: (the tick has gone to a completely different answer, because it was very good, and fit every requirement given, although in a much more clever way that I had intended. Intended optimal ...

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