×

## Expected Value

If you play roulette, are you going to break-even? Maybe sometimes, but not if you play forever, because the expected value is negative. The expected value finds the average outcome of random events.

# Level 4

You have 10 men and 10 women. Each man is married to one of the women (and no woman is married to more than one man). However, you don't know who is married to who; your job is to determine this.

To do this, you make several attempts. In an attempt, you match each man with some woman such that each woman is paired with exactly one man. Then, you are told which couples you guessed correctly. If you haven't guessed all couples correctly, you make another attempt. You repeat this until you get all correct.

Because you don't know anyone, your strategy is simple. You pick the couples at random. When you get a couple correct, in all future attempts, you will pair up that couple. For the other incorrect couples, you guess them at random again; this might mean you repeat a couple you previously attempted.

On average, how many attempts does it take for you to get all couples correct?

One day, you decide to play a game with your friend out of sheer boredom. Your friend picks out an integer randomly from the range $$[1,1023]$$ and you try to guess it.

You can guess an infinite number of times. Let $$n$$ denote the integer your friend chose and let $$k_i$$ denote the integer you chose on the $$i^\text{th}$$ try. If $$n > k_i$$ your friend will tell you "higher", if $$n < k_i$$ your friend will tell you "lower" and if $$n = k_i$$ then you win the game.

But then, your friend decides this is too boring. He decides to give you 1023 dollars. Every time you make a guess, right or wrong you have to give him $$x$$ dollars, even if you already gave him back the original 1023 dollars or even if you already have negative profits. Since your friend knows that you will play optimally, he sets $$x$$ such that your expected profit after playing the game is 0. Find $$\lfloor x \rfloor$$.

Notation: $$\lfloor \cdot \rfloor$$ denotes the floor function.

Tamara chooses an integer $$x$$ uniformly at random from $$1$$ to $$425.$$ She then chooses an integer $$y$$ uniformly at random from $$1,2,\ldots ,x.$$ What is the expected value of $$y?$$

Sarah the squirrel is trying to find her acorn, but she can't remember where she left it! She starts in the lower-left corner of the $$2\times 2$$ grid, and at each point, she randomly steps to one of the adjacent vertices (so she may accidentally travel along the same edge multiple times). What is the expected value for the number of steps Sarah will take before she finds her acorn in the top-right corner?

Spongebob loves square numbers. So, he decides to keep rolling a fair six-sided die, until any consecutive substring represent(s) a perfect square less than 100. e.g. If his last two rolls were first a 2 and then a 5, he would be done since 25 is a perfect square. Or, for example, any time he rolls a 4 he would also be done since 4 is a square number.

If the expected number of rolls he must make is $$\dfrac{a}{b}$$, where $$a$$ and $$b$$ are coprime positive integers, what is $$a+b$$?

×