Problem 151
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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 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.
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.
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.
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.
So I did that, and my answer still appears to be wrong. Perhaps my code needs further checking.
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 ( N_{1} + 2*N_{2} + 3*N_{3} ) / ( N_{0} + N_{1} + N_{2} + N_{3} ) where N_{i} 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 N_{2} = 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
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 N_{2} = 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
Re: Problem 151
Have you tried running Monte Carlo simulations to confirm your results?
Re: Problem 151
I haven't. I'll read up on it to see how I could apply it in this case. Thanks.
Expand
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 offbyone 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 smallscale simulations by hand to get a feel for how this problem works. Or, run a montecarlo 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.
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 smallscale simulations by hand to get a feel for how this problem works. Or, run a montecarlo 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.
Re: Problem 151
Thank you, I did finally discover my error.
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.
Expand
Re: Problem 151
That's it. The general concept with a MonteCarlo simulation is to write code that uses a pseudorandom number generator to simulate the random event and repeat the simulation many times, aggregating the results.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.
In all honesty, I've never actually written a MonteCarlo 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.
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!
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ètes sont là.
Re: Problem 151
Lol, no I just wanted to know if I understood the problem,
Thanks!
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ètes sont là.
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 ?
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ètes sont là.
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!
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)"
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.
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.
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 ?
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

 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 A2size?
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.
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.

 Posts: 39
 Joined: Mon Aug 08, 2011 8:49 am
Re: Problem 151
Disregard the last post. Problem solved.