How to Pick Up the Bucks
You have 2N coins of varying denominations (each is a non-negative real number) in a line. Players A and B take turns choosing one coin from either end. Prove A always has a strategy that ensures he end up with at least as much as B.
Communicated by A. Roy
What’s your soln? Email me at sjm1 AT williams.edu
Nice one. I tried to solve this puzzle few years ago but I failed. Now I tried again and finally I got it 🙂
But the reasoning is not that simple as the solution. Probably the problem comes from fact that you can:
1. prove the statement – in that case “natural”, intuitive thought is an induction; or
2. point the strategy (constructive proof), but in such case “natural” thinking is greedy algorithm.
Both don’t work 🙂
Thank you Steve for you Puzzle page.
coins are given in a certain order
one player knows they are going first
they can both see the amounts
they can ONLY choose from an end
So for the rules: -both could start
– A could manipulate the order of the coins
-if the coins were ‘c1′,’c2′,’c3′,’c4’, they could choose between c1 and c4
am i right so far?
probably should be c_1 or c_{2n} as have to take an end — email me at sjm1 AT williams.edu to discuss in greater depth //s
One of your comments says. “they start by taking c1 or c2.” I thought that whoever goes first must take either c1 or cn (the first coin or the last coin). Can c2 be selected if c1 hasn’t been taken? Or, can c(n-1) be selected if cn hasn’t been chosen?
You might be on the right path but hard to follow. There is a one line answer. You can email me at [email protected]
Let 2N be divided into k denominations with n1, n2, …, nk be the number of coins in each denomination. It is clear that n1 + n2 + … + nk = 2N (n1 reads n_sub_1). Let index 1 represent the highest value of these denominations, 2 for the second highest, and so on. To ensure advantage, each player would intend to pick the coin whose value is highest (or one of) among the remaining coins. This makes clear that if n1, n2, …, nk are all even, then this will ensure that both players will have equal value (sum of the coins). Now suppose that at least one of these denominations have odd, say n_sub_i, the number of coins in the denomination i. It follows that there exist an n_sub_j (where i B1+B2+…+B_sub_i, where A_sub_i or B_sub_i is the total cost of coins picked by respective players in denomination i. Although this implies that B_sub_j>A_sub_j, still A has an advantage over B since the cost of denomination i is larger than i+1 or any of the succeeding denominations and that for the remaining even numbered denominations, both have equal cost picked up. Therefore, A has at least as much as B. They have equal if n1, n2, …, nk are all even. If at least two of them are odd (there can’t only be one or three or so on odd denomination since the sum of all are even), this would ensure A has more cost of coins picked up than B. Q.E.D. =)
That’s not the soln — how does going first force a win? You need to add a few details. //s
always go first
you’re right that with an odd number of coins whomever goes first MIGHT
lose
it’s important that there are an even number of coins
Is it 2N to ensure you have at least two coins? Could N be 0.5 giving a ‘line’ of 1 coin?
The case of 3 coins implies non-integer N? but I’m confused by the 2N (can’t it just be N?).
With $1 $999 $2 whoever goes first loses, so player A must have the decision on who goes first.
I think I’m nearly there other than the last case, I’ve sent an email to avoid spoiling for anyone else. Great puzzle 🙂
it doesn’t. email me (sjm1 AT williams.edu) if you want a hint. //s
For a1, a2, ………, a(n-1), a(n)
Say a1 > a(n). Choose a1 if :
1. a1>a2
2. a(n-1)>a2>a1
3. a2>a1>a(n-1) and a2-a1 a(n-1)>a1 and a2-a1 < a(n-1)-a(n)
Otherwise choose a (n)
What I do not understand is how it guarantees that player A will win
email me at sjm1 AT williams.edu — I see you went to Brown — spent 4 great years as a postdoc there.
Where can I check if I got the answer? I am pretty sure I did, but in general I’d like to be able to check (I will be coming here often because I have interviews coming up…) Thanks!
Bruno
you’re on the right track, but not there. imagine the coins are $1 $999 $2 — you can’t win. you need an explicit strategy…. Email me at sjm1 AT williams.edu if you want to chat more.
Assuming A goes first, then A sets the tone… a can look down the line to see what coins are the largest and will have to sacrifice by choosing smaller coins in order to set himself up for the bigger coins??
Not quite. The coins are in a line: c1, c2, c3, …, c_{2N}. You have to describe A’s strategy. They start by taking either c1 or c2. Which one? Why? Imagine there are just 2 coins, or 4 coins. What would the strategy be? Note that A does NOT always have a winning strategy (imagine there are only 3 coins).
Is it as simple as looking at the coins play A would potential unveil? If the potential coins are both similar in denomination then he takes the larger of the available coins. If the potentials are dissimilar then he would choose the coin that unveils the smaller option. I am not a student of math but very facinated by it. I have only a limited background as I have a degree in Biology. How close am I in a qualitative sense?
twig: correct, well done; not posting as it’s the soln
Try doing some special cases. start with fewer coins than 99, and try and get a feel. There IS a simple recipe for what you should do.
This is more complicated than it appears to be. I thought I can prove it easily by induction but there is a problem 🙁
My apologies — we had changed software and your reply was temporarily lost. If you contact me again I’ll respond.
Original post: Oh my…please help! I have a 142 IQ, yet I do NOT understand the function of ‘N’ in equations. Truth be told, I am a super creative visual artist and musician who does well with spacial math…yet the meaning of “n” eludes me. I have never studied math during my higher education years, yet I WANT so badly to understand …’n’!
I think, perhaps, the explanation of how to solve this riddle could help me…this could be the missing link I’ve been searching for. If anyone can help me, please visit my blog, and drop me an email. Seriously. Thank you.
PS It is a SERIOUS mental block with me! I’ve had a Rubik’s Cube for less than a week and I can solve it under 3 minutes already, yet I’ve been trying to figure out ‘n’ for a couple of years to no avail. Any good teachers out there willing to shed some light? I think maybe I was born without the part of the brain that comprehends ‘n’.