Problem 151

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.
fatcatfan
Posts: 5
Joined: Fri Nov 21, 2008 9:25 pm

Problem 151

Post by fatcatfan »

My initial solution is apparently incorrect. After reviewing my code, adding various levels of intermediate output to verify program flow, I feel it correctly represents and calculates my interpretation of the problem.

So my interpretation is apparently wrong.

When a sheet is selected from the envelope, if there are, for example, two size A4 sheets, I consider them each unique branches in the path to reach a state where only one sheet is in the envelope as well as the path to the last batch.

However, when any sheet larger than an A5 is selected from the envelope and cut, I consider either A5 produced at the end of the cutting as identical. That is, I make no distinction between the A5 that gets used and the A5 that is replaced in the envelope. Should I? and by extension should I make a similar distinction for larger sizes? For example, which of two A4 produced from an A3 gets cut in half and which gets placed in the envelope.
User avatar
ed_r
Posts: 1009
Joined: Sun Jul 29, 2007 10:57 am

Re: Problem 151

Post by ed_r »

Why don't you just try it and see?
!647 = &8FDF4C
fatcatfan
Posts: 5
Joined: Fri Nov 21, 2008 9:25 pm

Re: Problem 151

Post by fatcatfan »

Well, I'd initially thought it would add considerably more complexity to my algorithm, but after additional thought I realized it only requires adding additional scalars to a few lines, since those additional choices don't affect the state of the envelope at the beginning of each batch.

So I did that, and my answer still appears to be wrong. Perhaps my code needs further checking.
fatcatfan
Posts: 5
Joined: Fri Nov 21, 2008 9:25 pm

Re: Problem 151

Post by fatcatfan »

After further checking, I feel confident that my code accurately simulates the problem. I'm think maybe I'm just not extracting the right data from the model to calculate the expected answer. Presently my result is calculated as ( N1 + 2*N2 + 3*N3 ) / ( N0 + N1 + N2 + N3 ) where Ni represents the number of paths of random choice in which a single sheet of paper is found in the envelope i times in a week. Essentially I calculate a weighted average (expected value!).

I've run the simpler case of a 4 batch week starting with various combinations of A3, A4, and A5 and compared the results to manual calculation, indicating accurate modeling. I've checked the case of starting with a single A2 and verified that N2 = 3 by code output and manual tree drawing.

With the assumption that my code works and my weighted average is the wrong approach to the answer, I'm just looking for a gentle nudge to help me see why I'm wrong. Perhaps the category of mathematics/probability/statistics that I should consult further. Or maybe an earlier/simpler problem that I should try first before revisiting problem 151. It's all about learning, right? (for reference, I'm a Civil Engineer)

And if you feel I've revealed too much about the problem's solution in this post I'll edit it out so others won't be spoiled to the problem. Somehow I doubt I've revealed too much since I'm getting the wrong answer :wink:
Eigenray
Posts: 62
Joined: Mon Jul 14, 2008 5:20 pm

Re: Problem 151

Post by Eigenray »

Have you tried running Monte Carlo simulations to confirm your results?
fatcatfan
Posts: 5
Joined: Fri Nov 21, 2008 9:25 pm

Re: Problem 151

Post by fatcatfan »

I haven't. I'll read up on it to see how I could apply it in this case. Thanks.
Expand
I did locate a sort of "off by one" error in my calc. The problem doesn't care which sheet of paper is randomly chosen out of the envelope for the next to last batch, but I was adding that choice into the calc, ending my recursive function only when there was a single A5 in the envelope by itself, even though I didn't count the last single A5. I've fixed that and got a different result, of course, but it is still not the expected answer.
Ikcelaks
Posts: 28
Joined: Wed Oct 15, 2008 9:08 pm

Re: Problem 151

Post by Ikcelaks »

The problem description specifies that you are to exclude the first and last batches, so altering the code to count the last single sheet of A5 may have actually introduced an off-by-one error.

From what you've revealed about how you calculate the final expected value and how you perform the calculation by hand, I have a strong hunch that your model is incorrect. Do you weight every path equally? Should you?

I think it might be helpful for you to run through some actual small-scale simulations by hand to get a feel for how this problem works. Or, run a monte-carlo simulation as previously suggested. Either way, be sure to run through the actual process of the problem, not your model. That way, you can see how your model compares with reality.
fatcatfan
Posts: 5
Joined: Fri Nov 21, 2008 9:25 pm

Re: Problem 151

Post by fatcatfan »

Thank you, I did finally discover my error.
Expand
The off-by-one wasn't counting the last sheet as a single, but there are three potential paths (two unique) from the next to last batch to the last batch, so that was scaling all my results needlessly and disproportionately.

The real problem though, was as you suspected: Even though my code efficiently iterated over only unique paths (40040) and factored in how many ways you could follow each, I had failed to realize that each path does not have the same probabilty, because the envelope doesn't always contain the same number of sheets.
How would/did you apply Monte Carlo methods to this problem? It's a new concept to me, but after some thought, I believe the right approach would be to rewrite the code to follow a random path, instead of iterating over all paths. Then tally the results of a large sample of runs to approximate the answer. Another step could be to tally how often each unique path is followed, thus identifying their relative probabilities and shedding light on the mistake in my thinking.
Ikcelaks
Posts: 28
Joined: Wed Oct 15, 2008 9:08 pm

Re: Problem 151

Post by Ikcelaks »

It's a new concept to me, but after some thought, I believe the right approach would be to rewrite the code to follow a random path, instead of iterating over all paths. Then tally the results of a large sample of runs to approximate the answer.
That's it. The general concept with a Monte-Carlo simulation is to write code that uses a pseudo-random number generator to simulate the random event and repeat the simulation many times, aggregating the results.

In all honesty, I've never actually written a Monte-Carlo simulation, because it is often more complicated to simulate these problems than to directly compute the expected value (This problem is definitely one of those cases.). However, it's definitely a useful technique for the cases where it's either very difficult to compute the probabilities directly or you have a bug in your logic that you can't track down.
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

Re: Problem 151

Post by axelbrz »

Hi, can someone tell me what were the expected number of times (excluding the first and last time) if I were started with a paper of A3 size? (then I'll have one A4, and two A5, but as I'll use an A5, I'll have one A4 and one A5, etc.)

Thank you so much!
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"

Image
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 151

Post by daniel.is.fischer »

For four jobs, starting with an A3 paper, the expected number of times to find exactly one sheet in the envelope (excluding first and last) is 0.5, but that doesn't help you much, does it?
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

Re: Problem 151

Post by axelbrz »

Lol, no :) I just wanted to know if I understood the problem,

Thanks!
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"

Image
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 151

Post by daniel.is.fischer »

Did you?
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
pwan
Posts: 1
Joined: Tue Mar 25, 2008 1:22 am

Re: Problem 151

Post by pwan »

Does each piece of paper in the envelope have an equal chance of being picked by the foreman, or do the relative sizes of the paper come into play ?

For example, if the envelope contained an A4 and A5 pieces, would it be twice as likely the foreman would pick the A4 piece instead of the A5 piece, given the A4 piece is twice as big as the A5 piece, or would there be an equal chance the foreman would pick either piece ?
User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

Re: Problem 151

Post by daniel.is.fischer »

Each piece is picked with equal probability (1/(number of sheets in the envelope)).
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

Re: Problem 151

Post by axelbrz »

Hi, I'm getting a wrong answer.

I want to know if the probability to get one sheet of paper once from the envelope in a week, rounded to 4 decimals, is 0.3042, and if the probability to get a sheet of paper twice, rounded to 4 decimals too, is 0.0386.

Thank you!
"think(O(n))+O(n) sometimes is better than think(O(1))+O(1)"

Image
harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 151

Post by harryh »

No, I'm afraid that the values you posted are wrong :(
During each week, and excluding the first and last batch:
- the probability that he finds a single sheet in the envelope exactly once is 0.3100 (rounded to 4 dec.pl.)
- the probability that he finds a single sheet in the envelope exactly twice is considerably higher than 0.0386.
rockstome
Posts: 17
Joined: Tue Sep 06, 2011 3:54 pm

Re: Problem 151

Post by rockstome »

if he start from A3 size, expected number of times = a
if he start from A2 size, expected number of times = b
if he start from A1 size, expected number of times = c

daniel.is.fischer said that a=0.5
can anyone confirm that b>a>c ?
Thanks for reply
Image
oleglyamin
Posts: 39
Joined: Mon Aug 08, 2011 8:49 am

Re: Problem 151

Post by oleglyamin »

Could you confirm the following for the case of starting with a sheet of A2-size?

Probability of having one sheet in the envelope exactly 0 times = 0.5714 (rounded to 4 decimal places).
Probability of having one sheet in the envelope exactly 2 times = 0.0714 (the same).
Expected number of times that the envelope has one sheet = 0.5 (exact).

Thanks.
oleglyamin
Posts: 39
Joined: Mon Aug 08, 2011 8:49 am

Re: Problem 151

Post by oleglyamin »

Disregard the last post. Problem solved.
Post Reply