### PROBLEM LINK:

**Author:** Lewin Gan

**Testers:** Kamil Dębowski

**Editorialist:** Lewin Gan

### DIFFICULTY:

Medium

### PREREQUISITES:

Linearity of expectation

### PROBLEM:

Find the expected value of an optimal strategy for a game involving cards and tokens.

### QUICK EXPLANATION:

The main observation is that all strategies are optimal strategies; all strategies will lead to the same expected value.

### EXPLANATION:

Using the observation above, we get a really simple solution. Let’s play all red tokens, then all blue tokens. By linearity of expectation, we can get the total expectation to be

.

Intuitively, you can guess this by noticing that the cards are played randomly. We can prove this more formally with induction.

Consider a O(r*b*p) dp solution as follows. Let f(r,b,p) denote the expected value given we have r red cards, b blue cards, p red tokens, and r+b-p red tokens.

We claim that

. We prove this by inducting on r+b.

We can check that the base cases f(1,0,1), f(0,1,1), f(1,0,0) and f(1,0,1) all make sense (i.e. f(1,0,1) = 1, since we have a red token and red card, so we get 1 point).

Now, for the inductive case, consider two cases: we either play a red token or blue token.

Play a red token:

This is a bit hard to simplify, but we can use wolfram alpha here.

Thus, we get

Play a blue token:

This can be simplified with wolfram alpha again [here][4].

Thus, we get

.

Thus, in both cases, we get the same expected value, so this completes the induction step. Thus, we’ve proven this formula works.

### AUTHOR’S AND TESTER’S SOLUTIONS:

[4]: http://www.wolframalpha.com/input/?i=((((p(r-1)+%2B+(r%2Bb-p-1)*b)+%2F+(r%2Bb-1))+*+r+%2B+(((p*r+%2B+(r%2Bb-p-1)*(b-1))+%2F+(r%2Bb-1))+%2B+1)+*+b)+%2F+(r%2Bb)