The Trickster's Game

Question

While walking around the streets of your local city, you encounter a strange woman sitting atop a gigantic pile of dollar coins. "Would you like to play a game?" she asks. Intrigued by the strange sight you ask, "What kind of game?" She replies:

Well, I've got all these coins that I don't know what to do with. I'd really like to share them with someone. I love games, so let's do it in the form of a game. We'll take turns dividing the pile into two piles and giving the other player the larger half to keep, then continuing play analogously on the smaller pile. If you split the piles equally, then the other player may take either half and play will continue on the other half. It'll be great for our karma - so much giving and whatnot!

Skeptical, you ask her, "Well, there's got to be a catch - you're not just giving away free money, are you? (But I'm in if you are!)". She says,

Well, I'd love to just let you have this pile, but, for tax reasons, I can't just give away so much money. Therefore, you'll have to contribute to my pile before we play. But, if you contribute half as many coins as I have in my pile, I'll let you play (on the whole pile with both of our coins). I'll even let you go first!

That sounds like a fantastic deal, so you agree, and add exactly enough coins to the pile to increase its size by $50\%$. Then, you each play optimally, gaining as many coins as possible. At the end of the day, you count up the coins you earned, and find that you earned back $5 less than you contributed to the pile! At a minimum, how many coins did the woman have at the end of the game?

Answer 1

One rigorous solution to this problem is to write out a recursion relation for the total earnings $f(n)$ of the first player given a pile of $n$. It is clearly optimal to divide the pile as evenly as possible so the first player will give the other player $\lceil \frac{n}2\rceil$ coins and continue play on $\lfloor \frac{n}2\rfloor$ coins. Obviously, as this leaves them with no new coins and gives their opponent a pile of $\lfloor\frac{n}2\rfloor$ coins, they will earn however many their opponent does not. That is, we may write $$f(n)=\left\lfloor \frac{n}2\right\rfloor-f\left(\left\lfloor\frac{n}2\right\rfloor\right).$$ Together with the equation $f(0)=0$, this determines $f$ for all positive values. Notice that we may rewrite the above equation as: $$f(2n)=f(2n+1)=n - f(n)$$ Next, we are interested in the function which, given the total pile size, determines the net earning for the player - which is their earnings minus their contribution of a third of the pile: $$g(n)=f(n)-\frac{n}3.$$ Substituting $g(n)+\frac{n}3$ in for $f$ in the second recursion relation, we get: $$g(2n)+\frac{2n}3 = g(2n+1)+\frac{2n}3 +\frac{1}3 = n - g(n) - \frac{n}3$$ which, after simplification, becomes: $$g(2n)=g(2n+1)+\frac{1}3=-g(n).$$ This essentially says what has been noted in other answers - when a player has to "round down" (i.e. when they are given an odd pile), they are giving away $\frac{1}3$ dollars of their earnings. However, we can go a step further and give the following algorithm for calculating a player's loss given the total pile size using the above relation:

Let $n$ be the initial size of the pile. Write $n$ in binary. Starting at the one's place, color every other digit red and starting at the two's place, color every other digit blue. Starting with $n=141$ we would get: $$141=\color{blue}1\color{red}0\color{blue}0\color{red}0\color{blue}1\color{red}1\color{blue}0\color{red}1_2$$ Now, count the number $b$ of blue '1's and the number $r$ of red '1's. Your net earnings are $\frac{b-r}3$ - so in the above example, the player breaks even.

Then, the problem is easy: The smallest total pile size is $15$ red '1's with no blue '1's. So, the pile size is at least: $$10101010101010101010101010101_2=357913941.$$ We then multiply this by $\frac{2}3$ to get the strange woman's initial pile size and add $5$ to get her final pile size, yielding that she had $238,\!609,\!299$ coins at the end.

Answer 2

My answer is very close to the others, but slightly off.

238,609,294

Here is how the game plays out.

You contribute 50% of what she does, so you give $119,304,647$. This makes the pile $357,913,941$ in total.

Each round will be where you play and she plays. Thus, we get the following table. During each round, she will keep the larger of the two piles to herself and play with the smaller. You will get as profit the larger if the two piles she makes. The next round will start with the smaller of her two piles.

$$\begin{array}{lrrrrr} &&\text{Your turn}&&\text{Her turn}\\\text{Round}&\text{Pile}&\text{Small}&\text{Her profit}&\text{Small}&\text{Your profit}\\\hline 1&357,913,941&178,956,970&178,956,971&89,478,485&89,478,485\\2&89,478,485&44,739,242&44,739,243&22,369,621&22,369,621\\3&22,369,621&11,184,810&11,184,811&5,592,405&5,592,405\\4&5,592,405&2,796,202&2,796,203&1,398,101&1,398,101\\5&1,398,101&699,050&699,051&349,525&349,525\\6&349,525&174,762&174,763&87,381&87,381\\7&87,381&43,690&43,691&21,845&21,845\\8&21,845&10,922&10,923&5,461&5,461\\9&5,461&2,730&2,731&1,365&1,365\\10&1,365&682&683&341&341\\11&341&170&171&85&85\\12&85&42&43&21&21\\13&21&10&11&5&5\\14&5&2&3&1&1\\15&1&0&1&-&- \end{array}$$

If you add up the far right column, you get $119,304,642$. This is exactly $5$ less then you contributed to the pile.

Answer 3

I got that the woman must have at least:

238609299

coins at the end of the game.

Reasoning:

First, the value of a pile is weakly monotonically increasing, because additional coins can always just be given to the other person - you will never get less money. Thus, giving the other person as few coins as possible is always optimal. The only asymetry is the odd vs. even giveaway. Thus, for the woman to gain money, she must be splitting odd piles, while you must be splitting even piles. If we set up a series of odd/even splits, we get the following: http://pastebin.com/PQssUcvh At the link, the format is as follows: inital pile, amount you get, amount she gets. The lines alternate you start, she starts, etc. The line Loss: _ is printed after each amount you could actually start with, because if you contribute half as much as she has, the stating amount must be a multiple of 3. The amount lost reaches 5 on the last line.

Answer 4

You only need a big calculator to do 1 calculation in this.

The answer is in fact (as others have pointed out)

238609299

Explaination:

Observe that you start the game, thus she wants the total amount to start on an odd number (so you have to give her the strictly bigger half). In return she wants an even number so she can give you exactly half. This however has to yield another odd number (so you again give her more than half) etc.

Now starting piles can be calculated backwards from 1. Double it, then double and add 1 to maintain her getting strictly bigger portions. We get 1, 5, 21, 85, 341...

Calculating amount you win:

First consider the case with a game of size 1. You would win \$0. (You give her a dollar and it is over.)

Second consider the case with game of size 5. You give her 3, she gives you 1, and now we are left with a game of size 1 (your turn and \$1 left.) Since we know that case, you make \$1+\$0 = \$1.

Third consider the case with game of size 21. You give her 11, she gives you 5, and now we are left with a game of size 5. Since we know that case, you make \$5+\$1 = \$6.

We can say that in starting with \$n, you will make the amount you made in game n-1 + the starting size of n-1. Our winnings are thus: 0, 1, 6, 27, 112...

The last thing to note is our cost in each game is 1/3 of the total size at the start of the game. So our games of size 1, 5, 21, 85, 341 cost us .333, 1.666, 7, 28.333, and 113.666. Notice this versus our winnings: Every increase in game size, and we lose \$0.33. Thus our 15th game will lose us \$5.

Now we just need to find $$\dfrac{2}{3}\sum_{i=0}^{14}{4^i} = \dfrac{2}{3}357913941 = 238609294 $$

But we must add the \$5 you won for a total of 238609299

Answer 5

Building from isaacg's reasoning of odd and even splits, we require the woman to start her turns with an even number of coins so that you get half of that pile, and you start with an odd number of coins so she gets more than half of that pile. This means the woman ends up with 2 coins in her last iteration, giving one to you and keeping the other herself.

Building backwards from the last coin paid out, and bracketing the amounts you get, we end up with a payouts sequence $[1, (1), 3, (5), 11, (21), 43, \dots]$. It goes $[n, (2n-1)]$ from her turn to your preceding turn and $[(n), 2n+1]$ from your turn to her preceding turn. (Note that we are counting payout-to-payout, not remainder-to-payout.)

Since she gets the first and last payout, we want an odd number of turns in this sequence. We also need to start the game with a multiple of 3 as the number of coins, so the sum of the series must be a multiple of 3. Finally, you need to pocket 5 coins less than you started, so the sum of the bracketed amounts must be 5 less than the sum of the series.

Putting this all together in a spreadsheet, I get a starting figure of $357,913,941$, of which you contributed $119,304,647$ and finished with $119,304,642$, leaving her with $238,609,299$ coins after 29 turns.

Here are some spreadsheet formulae for verification in case I've made a mistake:

A1=1, A2=2*B1+1 (her payouts in reverse order)
B1=2*A1-1       (your payouts in reverse order)
C1=SUM($A$1:A2) (her cumulative total payout in reverse order)
D1=SUM($B$1:B1) (your cumulative total payout in reverse order)
E1=C1+D1        (number of coins at the start)
F1=D1+5-E1/3    (your payout + 5 (D1+5) minus your contribution)

Copy the formulae down in each column, and look for the first row where column F is zero.

The real question is ... what were you doing lugging that much change around before you met this strange woman?

Answer 6

I'm lazy and don't have a big enough calculator so here is a bad answer

2386092942

reasoning..

Well, Optimal strategy is you split halvsies as they get the least number of coins. if you have a stack of 32, the split is 16, 16, they get 16. any other split (17/15) they would get 17. When they split a 17, the best they can do is 9,8 where you get 9. So with this idea going in lets look at the original problem. She has 2X money, you contribute X. So 3X money. If we follow the 32 example all the way through, It goes 16, 8, 4, 2, 1, 1. Or 21 to 11. The original put in would be 11.33 and pay out 11 so net loss .33. It will be like this for all powers of 2 (I think). So The strange woman is using the odd vs even splitting. Lets follow the 17 example. It goes 9,4,2,1,1. Or 12 to 5. Initial put in was 5.67 so loss was .67. It seems the 9/8 split worked as a gain. So lets optimize the path for the which. Lets make the last split a 2,1 split from 3 coins. then the which would want a 3,3 split so 6. then by the odd favoring the which logic a 6,7 13, 26, 53, 106, 213. Lets see what the advantage is now. 107, 53, 27, 13, 7, 3, 2, 1. Well this is 143 to 70. Well the initial pay in was 71, so this person lost a dollar. One more iteration upwards we get 426 and 853. so add 427 and 213 respectively we get. 570 and 283 from 853 total. Pay in was 284 1/3 lost 1.3333. It seems each iteration loses 1/3 more dollars this looks like a big stack of coins indeed. (3 was 0, 13 was 1/3 ...) so we just need to iterate 11 more times... Well the basic step is double from here then double and add one so 4n+1 so... 4^11 more to go roughly. that is roughly 2^22 or 4 million ish... the 1's get annoying so i will come back with a calculator. 3579139413 is the number of initial coins so she has 5 more than 2/3. 2386092942. I don't have enough significant digits on my calculator so I think it is actually not a whole number. But one you have 3 billion coins you can lose some rounding. upon further inspection this seems divisible by 3. All is well.

Answer 7

@isaacg had this answer first, this is just another way to get there.

The woman had to have at least

238609299

at the end of the game.

I used a dynamic programming solution to calculate the winnings for pile sizes up to 100000000 (10^8). This didn't yield any results.

From there I used a memoized recursive solution for all possible woman starting pile values from 2 up to 1000000000 (10^9) stepping by 2 (assuming that coins are not fractional). In the worst case the recursive solution would have to go four layers deep before it hit a memoized answer. This is negligible making the algorithmic complexity O(size of woman's starting pile).

This actually yielded 29 results of which the posted answer was the minimum.

#include <iostream>
using namespace std;

int win[100000001];

long long get_winnings(long long pile) {
    if(pile <= 100000000)
        return win[pile];
    return (pile / 2) - get_winnings(pile / 2);
}

int main() {
    win[0] = 0;
    for(int pile = 1; pile <= 100000000; pile++) {
        int small_half = pile / 2;
        win[pile] = small_half - win[small_half];
    }
    for(long long woman = 2; woman <= 2500000000; woman += 2) {
        long long investment = woman / 2;
        long long winnings = get_winnings(investment + woman);
        if(investment - winnings >= 5)
            cout << woman << " " << investment << " " << winnings << " " << woman + investment - winnings << endl;
    }
    return 0;
}

Answer 8

Strategy:

The first player is always at a disadvantage that gets worse for greater values, because the second player gets the first coins. After the first move, the second player will be the disadvantaged "first" player of a smaller game. Keeping this game as big as possible by dividing the pile as equally as possible (while also avoiding losing extra coins right off the bat) is the right strategy.

About the minimum number of coins:

The woman wins 15 more than twice our earnings. Letting the money gained in a move equal $x$, the money gained in the previous move can be $2x-1$, $2x$ or $2x+1$. If we write those amounts backwards, we get a series whose first and last terms belong to the second player (the woman) and that progresses like $x, 2x-1, 4x-1, 8x-3, 16x-5$, ... . The series must start from 1, so we can write 14*2+1 = 29 terms to fulfill the conditions. If we add up all of them, we'll get the minimum number of coins. When the series progresses like $x, 2x+1$, the next term also makes 1 more than the sum of all the previous terms. When the series progresses like $x, 2x-1$, it equals their sum. Therefore, the sum of all the terms would be the 30th term if the series continued. The even-ordered terms start with 1 and progress like $x, 4x+1$, ... . The 30th term would be the 15th even-ordered term and equal 4^14 + (4^14-1)/3 = 268435456 + 89478485 = 357913941. We win 119304642 and she wins 238609299.

Answer 9

Strategy:

Treat the problem as a binary tree where the root node is the last splitting of the pot (1 coin), and its two children are composed of the previous pot and the previous split (split is either equal to the pot or the pot plus one coin), then perform either a breadth first search or depth first search for the solution (brute force). Take the minimum value found in the set.

Result:

I'd written some code in C# and found that the solution is found at a height of 28, where her split is 238609299 and your split is 119304642. Other solutions were once again found at a height of 30 (and so on), but were closer to 1 billion (and up) for her split of the pot. The first time I tried writing it as a breadth first search, but ran out of memory. The second time was depth first and provided the solution. I capped the height to 32 to give me a bearable run-time. That solution is the only one found at the height of 28, and the first solution found.