problem 394

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
gelatine1
Posts: 4
Joined: Sun Sep 16, 2012 4:12 pm

problem 394

Post by gelatine1 »

i believe there is no rule how big he cuts his pieces. so that means his remaining part can always be lower then F after the first cut. so i don't really get what's E(x) is supposed to do and how it can be a non-integer value.
so i believe that i am misunderstanding the question or that there's missing a part in the question.
Image

wrongrook
Posts: 396
Joined: Sat Oct 17, 2009 10:39 pm

Re: problem 394

Post by wrongrook »

I wonder if you are thinking about the problem like a game where Jeff is choosing where to make the cuts?

In this case you are correct, and Jeff can "win" the game on his first move by cutting off most of the cake.

However, this is not the intention of the problem. It is better to think of it as a simulation where Jeff chooses his cuts by generating a (uniformly distributed) random number that points somewhere along the remaining pie border. It can therefore take 1 or 2 or more goes to eat the pie depending on what random numbers are chosen. The average number of goes is the expected value that you need to find as the answer.

I hope this helps, but apologies if I have misunderstood your misunderstanding!

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

Re: problem 394

Post by jaap »

Also, as I said in this thread, expected value has a specific mathematical meaning that you need to know to be able to answer questions like this.

User avatar
Marcus_Andrews
Administrator
Posts: 1517
Joined: Wed Nov 09, 2011 5:23 pm

Re: problem 394

Post by Marcus_Andrews »

gelatine1 wrote:i believe there is no rule how big he cuts his pieces. so that means his remaining part can always be lower then F after the first cut. so i don't really get what's E(x) is supposed to do and how it can be a non-integer value.
so i believe that i am misunderstanding the question or that there's missing a part in the question.
Expected value is basically "the average you get if you conduct the experiment infinitely many times" or "the average across all possible outcomes weighted by their probabilities."

For example, the expected value of a 6-sided die is 3.5. If you were to roll a single die, repeatedly, all day long, while taking the average, you'd get a number pretty close to 3.5. However, in this case you can calculate the EV directly by noting that (1/6)*1 + (1/6)*2 + (1/6)*3 + (1/6)*4 + (1/6)*5 + (1/6)*6 = 3.5.

3.5 is a decimal (i.e. it's not a whole integer value that you can roll on a die) but it is still technically the value of the expectation.

Hopefully this clarifies things a bit more. Keep in mind, though, that in the case of Problem 394, there are infinitely many ways to make the cuts.
Image

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

Re: problem 394

Post by ffff0 »

Can someone suggest reading materials for this problem? I hope that I simply don't know something obvious regarding continuous random variables.
Image

User avatar
Marcus_Andrews
Administrator
Posts: 1517
Joined: Wed Nov 09, 2011 5:23 pm

Re: problem 394

Post by Marcus_Andrews »

ffff0 wrote:Can someone suggest reading materials for this problem? I hope that I simply don't know something obvious regarding continuous random variables.
I hope this is not considered too much of a spoiler, but I would advise looking into probability density functions.
Image

kruzulis
Posts: 1
Joined: Tue Sep 18, 2012 8:55 am

Re: problem 394

Post by kruzulis »

Could somebody please confirm that problem described below is equal to #394
Given n=1 and F=1/x repeat following procedure:
(
slice1 gets random value from range (0..n)
slice2 gets random value from range (0..n)
n gets new value: n=n-max(slice1,slice2)
if n is less that F then stop the procedure otherwise start with slicing again
)

Should find the expected value of number of times procedure is called before it stops.

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

Re: problem 394

Post by jaap »

kruzulis wrote:Could somebody please confirm that problem described below is equal to #394
Yes, that seems correct.

Post Reply