15
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I don't understand - you put $x$ dollars in the pile, and you go first. So just take back the $x$ you put in as your first move. That can't be more than half the entire pile, so you get to keep it. $\endgroup$ – Jack M Jul 23 '15 at 9:44
  • 1
    $\begingroup$ @JackM Play continues on the smaller 'half' of the pile. So if you've put in a third of the coins (x), then immediately taken out a third of the coins, she gets her original pile back, and her next move will involve her directly cutting into the money you put in. $\endgroup$ – LogicianWithAHat Jul 23 '15 at 10:57
  • $\begingroup$ Nice question, and it only really requires 1 calculation. I used Wolfram Alpha on my phone to do it $\endgroup$ – qwertylpc Jul 23 '15 at 20:17
  • $\begingroup$ Can one assume that all coins involved are dollar coins? $\endgroup$ – Matthew0898 Jul 23 '15 at 21:53
  • 1
    $\begingroup$ @Matthew0898 Yes. $\endgroup$ – Milo Brandt Jul 23 '15 at 22:29
11
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I believe you slightly misread the question: At a minimum, how many coins did the woman have at the end of the game? Your number is the amount she starts with. After that fix, we have the same answer. $\endgroup$ – isaacg Jul 23 '15 at 14:46
  • $\begingroup$ @isaacg Yes, I minimized the coins at the start (her pile and your contribution). If the initial pile is $357,913,941$ and you win $119,304,642$, then she would have the difference, which is $238,609,299$, the same answer as you have. Sorry about that! $\endgroup$ – Trenin Jul 23 '15 at 14:57
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ For a starting pile of 447392412 the maximum winnings is 149130807. You should be +3 in this situation. +1 for your "real question" though. $\endgroup$ – LeppyR64 Jul 23 '15 at 15:05
  • $\begingroup$ @LeppyR64 Thanks :) . You're right about the winnings, the starting figure should be odd. The problem comes from the player getting even numbers of coins, contrary to the design intent. Back to the drawing board. I'll leave this answer up for the time being while I take another look at this. $\endgroup$ – Lawrence Jul 23 '15 at 15:39
  • $\begingroup$ @LeppyR64 I was just going to just brute-force an answer, but saw that you beat me to it; +1 for the memoization. $\endgroup$ – Lawrence Jul 23 '15 at 16:25
  • $\begingroup$ @LeppyR64 I've corrected the formula (out by 1) and our answers now agree. $\endgroup$ – Lawrence Jul 24 '15 at 9:10
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is that $2$ at the end of the number a typo? Because I'm fairly certain that $238609294$ is the minimum number of coins she can start with and it seems too odd to be a coincidence that you have that number, with a bonus digit at the end. $\endgroup$ – Milo Brandt Jul 23 '15 at 2:47
  • $\begingroup$ hmmm. I misunderstood something! haha this is slightly larger than what i got $\endgroup$ – JLee Jul 23 '15 at 2:48
  • $\begingroup$ @Meelo I believe that 238609294 is a multiple of 3 while mine is not and the adding one half rule causes the issue. $\endgroup$ – Going hamateur Jul 23 '15 at 2:51
  • $\begingroup$ also can you check, cause the extra digit seems right to me. $\endgroup$ – Going hamateur Jul 23 '15 at 2:55
  • $\begingroup$ Though I am using the calculator I used in 3rd grade. $\endgroup$ – Going hamateur Jul 23 '15 at 2:56
1
$\begingroup$

@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;
}
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

protected by Aza Jul 24 '15 at 17:40

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.