## 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

Don't post any spoilers
fatcatfan
Posts: 5
Joined: Fri Nov 21, 2008 9:25 pm

### Problem 151

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.
ed_r
Posts: 1009
Joined: Sun Jul 29, 2007 10:57 am

### Re: Problem 151

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

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

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 Eigenray
Posts: 62
Joined: Mon Jul 14, 2008 5:20 pm

### Re: Problem 151

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

I haven't. I'll read up on it to see how I could apply it in this case. Thanks.
Expand
Ikcelaks
Posts: 28
Joined: Wed Oct 15, 2008 9:08 pm

### Re: Problem 151

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

Thank you, I did finally discover my error.
Expand
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

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

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)" daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

### Re: Problem 151

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&egrave;tes sont l&agrave;.
axelbrz
Posts: 51
Joined: Mon Sep 08, 2008 5:34 am

### Re: Problem 151

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)" daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

### Re: Problem 151

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

### Re: Problem 151

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 ?
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 11:15 pm
Location: Bremen, Germany

### Re: Problem 151

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

### Re: Problem 151

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)" harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

### Re: Problem 151

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

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 ? oleglyamin
Posts: 39
Joined: Mon Aug 08, 2011 8:49 am

### Re: Problem 151

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

Disregard the last post. Problem solved.