Problem 298

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
zwuupeape
Posts: 189
Joined: Tue Jun 09, 2009 6:11 pm

Problem 298

Post by zwuupeape »

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

kendavid
Posts: 2
Joined: Mon Jun 28, 2010 9:30 am

Re: 298

Post by kendavid »

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

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: 298

Post by stijn263 »

No, they're not :(

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

kendavid
Posts: 2
Joined: Mon Jun 28, 2010 9:30 am

Re: 298

Post by kendavid »

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? :-)

zwuupeape
Posts: 189
Joined: Tue Jun 09, 2009 6:11 pm

Re: Problem 298

Post by zwuupeape »

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

meshko
Posts: 3
Joined: Mon Jan 14, 2008 4:23 pm

Re: Problem 298

Post by meshko »

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?

Waldovski
Posts: 27
Joined: Thu Jul 08, 2010 11:11 am

Re: Problem 298

Post by Waldovski »

In my opinion the wording of this problem is terrible.

User avatar
elendiastarman
Posts: 410
Joined: Sat Dec 22, 2007 8:15 pm

Re: Problem 298

Post by elendiastarman »

Waldovski wrote:In my opinion the wording of this problem is terrible.
Okay...do you have anything constructive to say?
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Image

ffff0
Posts: 50
Joined: Sun Aug 21, 2011 6:26 am
Location: Moscow, Russian Federation

Re: Problem 298

Post by ffff0 »

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?
Last edited by ffff0 on Tue Jan 24, 2012 12:29 pm, edited 2 times in total.
Image

ffff0
Posts: 50
Joined: Sun Aug 21, 2011 6:26 am
Location: Moscow, Russian Federation

Re: Problem 298

Post by ffff0 »

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.
Image

User avatar
hk
Administrator
Posts: 10811
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 298

Post by hk »

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.
Image

ffff0
Posts: 50
Joined: Sun Aug 21, 2011 6:26 am
Location: Moscow, Russian Federation

Re: Problem 298

Post by ffff0 »

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.
Image

Ramiel
Posts: 5
Joined: Thu May 30, 2013 9:39 pm

Re: Problem 298

Post by Ramiel »

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?
Image

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 298

Post by TripleM »

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.

Ramiel
Posts: 5
Joined: Thu May 30, 2013 9:39 pm

Re: Problem 298

Post by Ramiel »

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?
Image

User avatar
jaap
Posts: 550
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 298

Post by jaap »

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

Ramiel
Posts: 5
Joined: Thu May 30, 2013 9:39 pm

Re: Problem 298

Post by Ramiel »

Thank you :)
Image

Junglemath
Posts: 54
Joined: Fri Sep 20, 2019 1:25 pm
Location: Minsk

Re: Problem 298

Post by Junglemath »

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

User avatar
RobertStanforth
Administrator
Posts: 1292
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 298

Post by RobertStanforth »

Thanks for flagging. This is now fixed.

Post Reply