Take the last chip

[BMAD]

Turkey Sandwich was worried about an upcoming test in Discrete Mathematics and was finding it hard to get to sleep. Turkey awoke early in the morning, aroused by devilish laughter, only to see an impish looking homunculus sitting at the bottom of the bed next to a seemingly infinite pile of chips. Hello Turkey it said, would you like to play a little game? This pile contains 43546758343209876 chips and the bottom chip represents your immortal soul. The rules are quite simple. The first player takes some chips, but not all of them. After that we take it in turns to take some chips.

The only rule now is that a player cannot take more in their turn than the previous player took. The winner is the player who takes the last chip. If I win I get to keep your soul and if you win, you get an A in the test. Would you like to go first or second? This seemed a reasonable bet to Turkey. Can you give Turkey a strategy for playing no matter how many chips there are?

Was that too easy? What if a player can take up to twice the number of chips that the previous player took. What is the best strategy now?

[BMAD]

On 12/18/2015 at 5:28 AM, bubbled said:

I think I figured out the first question:

  Hide contents

Define N (even number) to be the number of chips in the pot. As long as N is not equal to a number  2^n (n = integer), then Turkey (T) should go first. Otherwise go second. If N is odd, the game is trivial. T takes 1 on the first move and wins.

If N is not equal to 2^n, then search for the smallest number 2^a where (N / 2^a) is an odd number. Start by taking 2^a from N. If the homunculus (H), takes an odd number next, the game is over. T takes 1 next and will win. So, to keep things interesting, H must take an even number next.

(N - 2^a) will be divisible by all numbers 2^b where b <= a. And (N - 2^a) / 2^b will be an even number. Therefore, if H takes 2^b next, (N - 2^a - 2^b) will be divisible by 2^b and will be odd. So, whatever even number, 2^b, H takes from (N - 2^a), T should next just take 2^b. H can now take 2^c where c <= b, and T continues with the same strategy above until he wins.

If N = 2^n, then N / 2^a (a <= n) will be even. So no matter what even number H takes from N, T can go second and take 2^a next, and continue the strategy above to win.

In the specific game with 43546758343209876 chips in the pot, T should go first and take 4. 43546758343209876 - 4 = 43546758343209872. That number is divisible by 2 and 4, and those divisions result in an even number. So, no matter whether H takes 4 or 2 next, he will leave an odd number of 4's or 2's for T.

Here's one concrete example. If N is 20:

T takes 4, H 4, T 4, H 4, and T wins with 4. Or T takes 4, H 4, T 4, H 2, T 2, H 2, T wins with 2. Or T takes 4, H 2, T 2, H 2, T 2, H 2, T 2, H 2, T wins with 2.

 

 

12 hours ago, bubbled said:

I think have the answer to the second part:

  Hide contents

Turkey (T) should go first unless the starting chips are in the set of losing (L) starting conditions.

L = {L1 = 2, L2 = 3, L3 = L1 + L2, L4 = L2 + L3, L5 = L3 + L4....}. So it's the Fibonacci sequence without the 1, 1 at the start as those numbers don't make sense given the problem.

My logic is a bit convoluted, but it's the only way I've managed to get anywhere. Basically, the key numbers are the ones in L. There are two ways to win.

1. Ideally, on your first play, take as many chips as necessary to leave a number in L. However, you can only do this if the number of chips you take is strictly less than 1/2 of the number of chips you leave. For example, if your starting chips is 7, you can take 2, and leave the homunculus (H) with 5, and since 2 < (5/2) and 5 is in L, you win. However, you lose on 8, because if you take 3 leaving 5, H can win by taking the rest of the chips. So you must take either 1 or 2, but either way, H will leave you with 5 next, and you lose.

2. You also win if the (starting chips) - (the largest member of L that's less than starting chips) is not in L. For example, let's look at 20 chips to start. The key number is 13, as that's highest number in L that is less than 20. Ideally, we'd like to get right down to 13, but if we take 7, H wins by taking the rest of the chips. But, we are in luck as 20 - 13 = 7, and 7 in not in L. This means we can play the game as though the starting chips were 7. Once we take the last chip above 13, we will leave H with 13 and win.

If the number of starting chips gets really large as in the problem, the only way I can think solving it is recursively. The idea is, you need to keep leaving H with various numbers in L, all the way down the ladder. To do that, you may need to examine how you win from smaller numbers and build up. In example 2 above, I know that 7 is a winner. I also know that 5 is a loser, so I'd take 2, leaving 18 which is 5 more than 13. H can take any number from 1-4, but none of those will get him to 13. The most interesting is 1, leaving T with 17. 17 is 4 more than 13, so all still good. We know 3 is in L, so T takes 1, leaving H with 16, which is 3 more than 13. H can take 1 or 2, but either way, T's next play will leave H with 13. Next, T just needs get to the next stop which is 8. He will repeat the above process, stopping at 11 and/or 10 to get there. Then he'll go from 8 to 5, 5 to 3, and then win.

 

 

 

Well done! 

[bubbled]

I think I figured out the first question:

Spoiler

Define N (even number) to be the number of chips in the pot. As long as N is not equal to a number  2^n (n = integer), then Turkey (T) should go first. Otherwise go second. If N is odd, the game is trivial. T takes 1 on the first move and wins.

If N is not equal to 2^n, then search for the smallest number 2^a where (N / 2^a) is an odd number. Start by taking 2^a from N. If the homunculus (H), takes an odd number next, the game is over. T takes 1 next and will win. So, to keep things interesting, H must take an even number next.

(N - 2^a) will be divisible by all numbers 2^b where b <= a. And (N - 2^a) / 2^b will be an even number. Therefore, if H takes 2^b next, (N - 2^a - 2^b) will be divisible by 2^b and will be odd. So, whatever even number, 2^b, H takes from (N - 2^a), T should next just take 2^b. H can now take 2^c where c <= b, and T continues with the same strategy above until he wins.

If N = 2^n, then N / 2^a (a <= n) will be even. So no matter what even number H takes from N, T can go second and take 2^a next, and continue the strategy above to win.

In the specific game with 43546758343209876 chips in the pot, T should go first and take 4. 43546758343209876 - 4 = 43546758343209872. That number is divisible by 2 and 4, and those divisions result in an even number. So, no matter whether H takes 4 or 2 next, he will leave an odd number of 4's or 2's for T.

Here's one concrete example. If N is 20:

T takes 4, H 4, T 4, H 4, and T wins with 4. Or T takes 4, H 4, T 4, H 2, T 2, H 2, T wins with 2. Or T takes 4, H 2, T 2, H 2, T 2, H 2, T 2, H 2, T wins with 2.

 

[bubbled]

I think have the answer to the second part:

Spoiler

Turkey (T) should go first unless the starting chips are in the set of losing (L) starting conditions.

L = {L1 = 2, L2 = 3, L3 = L1 + L2, L4 = L2 + L3, L5 = L3 + L4....}. So it's the Fibonacci sequence without the 1, 1 at the start as those numbers don't make sense given the problem.

My logic is a bit convoluted, but it's the only way I've managed to get anywhere. Basically, the key numbers are the ones in L. There are two ways to win.

1. Ideally, on your first play, take as many chips as necessary to leave a number in L. However, you can only do this if the number of chips you take is strictly less than 1/2 of the number of chips you leave. For example, if your starting chips is 7, you can take 2, and leave the homunculus (H) with 5, and since 2 < (5/2) and 5 is in L, you win. However, you lose on 8, because if you take 3 leaving 5, H can win by taking the rest of the chips. So you must take either 1 or 2, but either way, H will leave you with 5 next, and you lose.

2. You also win if the (starting chips) - (the largest member of L that's less than starting chips) is not in L. For example, let's look at 20 chips to start. The key number is 13, as that's highest number in L that is less than 20. Ideally, we'd like to get right down to 13, but if we take 7, H wins by taking the rest of the chips. But, we are in luck as 20 - 13 = 7, and 7 in not in L. This means we can play the game as though the starting chips were 7. Once we take the last chip above 13, we will leave H with 13 and win.

If the number of starting chips gets really large as in the problem, the only way I can think solving it is recursively. The idea is, you need to keep leaving H with various numbers in L, all the way down the ladder. To do that, you may need to examine how you win from smaller numbers and build up. In example 2 above, I know that 7 is a winner. I also know that 5 is a loser, so I'd take 2, leaving 18 which is 5 more than 13. H can take any number from 1-4, but none of those will get him to 13. The most interesting is 1, leaving T with 17. 17 is 4 more than 13, so all still good. We know 3 is in L, so T takes 1, leaving H with 16, which is 3 more than 13. H can take 1 or 2, but either way, T's next play will leave H with 13. Next, T just needs get to the next stop which is 8. He will repeat the above process, stopping at 11 and/or 10 to get there. Then he'll go from 8 to 5, 5 to 3, and then win.