Project Euler Forum

I'm almost sure I got it and monte carlo gives very close results to what I get, but still the answer is wrong. :\ If anyone who solved it can PM me and help out it will be very much appreciated, thanks

stuck on it too.

would anyone please verify the following results:

after n turns, the expected value of |L-R|:

5 => 0.76117662
10 => 1.32713803
20 => 2.21853778
40 => 3.35951846

are these values even close?

TIA

No, they're not

After 5 turns the expected difference is 0. Good luck!

stijn263 wrote:No, they're not

After 5 turns the expected difference is 0. Good luck!

Thank you. I know what was wrong with my old method.

Now i have an hopefully correct but inefficient method:

7 => 0.00000000
8 => 0.01209600

Going crazy to compress states.. any hints?

Yeah, that's good. You're halfway through now.

So if I'm running monte carlo on this and it is not coverging, does it mean that I'm just not trying it fast enough? Or could it be that my random numbers are flawed?

In my opinion the wording of this problem is terrible.

Waldovski wrote:In my opinion the wording of this problem is terrible.

Okay...do you have anything constructive to say?

All right, I need a little help in understanding, because my program gives me zero as a result.

I've tried to check myself by calculating result after 8 steps by brute-force and i've got zero aswell. I guess i simply don't understand something.

What i'm doing wrong?

Oh my, i got it.

We have to sum not difference, but Abs(difference)!

I totally agree that wording of this problem is terrible. I've have to search the whole internet, including some solution discussion just for understanding the problem. This is not what Project Euler is about.

ffff0 wrote:I've have to search the whole internet, including some solution discussion just for understanding the problem.

Does this ipso facto mean that the wording is terrible?

Oh and please remove your spoilers in your but last post.

hk wrote: Does this ipso facto mean that the wording is terrible?

Oh and please remove your spoilers in your but last post.

If you look at my frustrations - yes. If you look at number of people, that have solved this problem - no.

Don't see how my post can help to count up to 50, but okay, removed.

I don't understand why the answer isn't 0. I'm thinking: after each turn L and R have 5 distinct numbers. 1 random number is chosen out of 10, so for each of them there is a 1/2 chance to get a point, so after 50 turns they would have on average 25 points each. I don't get why their algorithm for picking a number matters , as long as the called number is random and their 5 numbers are distinct?

You're asked for the expected value of |L-R|. Not the expected value of L-R. Since there is at least some chance they do not have the same score, the expected absolute value cannot be 0.

Even though there's a chance they have different scores, should there be equal chances that L gets A and R gets B, and L gets B and R gets A?

Suppose you have a coin that you flip twice times, with a 50/50 chance of heads/tails on each flip.
Let H be the number of heads in your two flips, T the number of tails.
The possible outcomes are:
H=0, T=2: probability 25%
H=1, T=1: probability 50%
H=2, T=0: probability 25%

The expected value of H-T is 0: every possible positive result with H>T is matched by an equally probable negative result with the values swapped.
E(H-T) = (2-0)*25% + (1-1)*50% + (0-2)*25% = 0.5 + 0 - 0.5 = 0

The expected value of |H-T| is not 0: Every possible result is 0 or positive, and the latter has non-zero probability.
E(|H-T|) = |2-0|*25% + |1-1|*50% + |0-2|*25% = 0.5 + 0 + 0.5 = 1

Thank you

Typo in the first sentence of the problem statement. The word 'of' doesn't belong there.

Thanks for flagging. This is now fixed.