I have 1000 cards on the table, R1 are red and B1 are blue.

You have 1000 tokens on the table, R2 are red and B2 are blue.

Each turn, you get to pick a token, and I randomly choose a card with uniform distribution. If they have the same color, you get 1 point.

Either way, the chosen token and card are both thrown away.

The game continues until nothing is left on the table. The question is what is expectancy of points you can get with an optimal strategy?


I calculated this out with dynamic programming, and it turns out there is no optimal strategy and you might as well just put all blue tokens first and then all red ones! Why is that? How come there's no edge you can get by seeing the cards I have left on the table and optimally choose a token?

It's because the numbers R2 and B2 are fixed. If I have unlimited tokens of either color, then the result might be different. But... imagine you only have blue cards left, by some fluke of chance. By this time, I have a certain number of blue tokens and red tokens left. No matter which order I play them the result will equal the number of blue tokens I have left.

Similarly, if you only have red cards left, no matter what order I play my remaining red tokens, the score will equal the number of red tokens I have left at this point.

The issue is that, I cannot predict in what order you will play your cards, therefore by the time I know that I should have more red tokens ideally, or more blue tokens ideally, it's too late.

Let's do reductio ad absurdum, and let's say there is just 1 token of each color, and 1 card of each color.

If I know you will play red then blue, then I should play red then blue.

But, at the time I play, e.g., red, I don't know whether you will play red or blue. Perhaps you play red, perhaps you play blue. By the time it gets to my second token, well, I know what you played, but I can no longer control the fact that my second token is now blue ;-)

Now, going back to my very first sentence: if I had unlimited tokens, then I can look at what you have left, and play the color you have most of. But since my own tokens are fixed, and I have exactly the same number of tokens that you have cards, then the order I play them makes no difference. Summary is:

  • from where I am, I can control the order that I play my remaining tokens, but I cannot control the proportion of the color of my remaining tokens. If I had unlimited tokens of either color, I could look at your cards, and see you have more blues, then I could play more blue tokens, and win. But I don't.

Oh, I see, you mean, imagine during the first third of moves, you play only red, so you have more blue than red, but still have some blue left. Then, I could play red for a bit, until such time as you switch to have more blue than red, and then I play blue for a bit.

The problem is, that this means that you have to play more blue in proportion to your remaining red, followed by more red. If I know you're going to do that, then I can play more blue first, and then more red. But since you're playing randomly, for all I know, you're going to play more red first, and then more blue later.

Basically:

  • I can see you have proportionally more of one color now, but I can't control what proportion I have now, it's too late
  • I can't guess whether you're now going to play first more red, and then more blue; or first more blue and then more red
    • if you play evenly, same proportion of blue/red, for the rest of the match, it matters not whether I play my reds first, or my blue first
    • if I know you will play blues first, then reds; or reds first then blue; I could change my sequence accordingly
    • but without that prior knowledge, changing my own sequence might increase my score, or it might decrease my score, and I won't know which, until I've already played, by which time it's too late.
  • great - thanks for this! I'm not marking this as accepted yet as I still want to wait a couple of days for a miraculous answer along the lines of "there's a different way to look at this problem..." – ihadanny Mar 28 '17 at 15:36

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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