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.
pelensing
Posts: 1
Joined: Tue Dec 31, 2013 3:17 pm

Re: Problem 151

Post by pelensing »

daniel.is.fischer wrote: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?
Can someone explain why? Somehow I think the chance is only .25. There are only two ways to put the unused sheets back in the envelope?

batch 1 a3 (take a3, cut in a4, a4 then a4 a5 a5, take a5, put a4 and a5 back
batch 2 a4 a5 (take a4, cut in a5 a5, put a5 back)
batch 3 a5 a5
batch 4 a5

or

batch 1 a3
batch 2 a4 a5 (take a5)
batch 3 a4 (cut in 2, place a5 back)
batch 4 a5

So 0.25 of the batches that count the envelope will contain 1 sheet?
mdean
Posts: 171
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 151

Post by mdean »

pelensing wrote:
daniel.is.fischer wrote: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?
Can someone explain why? Somehow I think the chance is only .25. There are only two ways to put the unused sheets back in the envelope?

batch 1 a3 (take a3, cut in a4, a4 then a4 a5 a5, take a5, put a4 and a5 back
batch 2 a4 a5 (take a4, cut in a5 a5, put a5 back)
batch 3 a5 a5
batch 4 a5

or

batch 1 a3
batch 2 a4 a5 (take a5)
batch 3 a4 (cut in 2, place a5 back)
batch 4 a5

So 0.25 of the batches that count the envelope will contain 1 sheet?
You listed 2 cases. In the first case, you didn't find a single sheet in the envelope except for the first and last jobs. In the second case, you found a single sheet once.
Image
demongolem
Posts: 6
Joined: Mon Nov 02, 2015 12:31 am

Re: Problem 151

Post by demongolem »

I am having trouble with the problem definition for some reason. I have not started the problem, but i want to understand what is to be included first. So the first batch does involve 1 piece of paper (A1) but that is discarded. The next batch is the second batch which starts with One A2, one A3, one A4, and one A5 which can be sort of seen from the diagram. This is included. Do I have my start conditions correct? Then the last batch (and I hope I don't say too much in this regards) would always be 1 A5 and that is the 16th and final batch which is also discarded.

If this is in fact correct as stated, I really don't think I should have any problem getting the actual answer.
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 151

Post by TripleM »

I'm not sure what you mean by 'included'.

At the start of day two the envelope contains four pieces of paper, like you say - A2, A3, A4, and A5.

That doesn't count towards the final answer however; you want to count days where the envelope starts with one piece of paper (excluding the first where there is always one A1, and the last where there is always one A5).
harshits2808
Posts: 1
Joined: Sat Jan 20, 2018 9:34 am

Re: Problem 151

Post by harshits2808 »

daniel.is.fischer wrote: Tue May 19, 2009 2:07 pm 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?

That actually helped me solve it!
For some reason i thought the answer would be 1/3, then i looked carefully and banged my head on the wall for a few minutes :D

After that it was just a bit of change in my code and correct answer!

Thank you!
Image
woega
Posts: 2
Joined: Fri Sep 06, 2019 11:51 am

Re: Problem 151

Post by woega »

harshits2808 wrote: Sat Jan 20, 2018 9:40 am
daniel.is.fischer wrote: Tue May 19, 2009 2:07 pm 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?

That actually helped me solve it!
For some reason i thought the answer would be 1/3, then i looked carefully and banged my head on the wall for a few minutes :D

After that it was just a bit of change in my code and correct answer!

Thank you!
ah that sounds promising, my code for A3 also returns 0.33333 . banged my head against the wall a few times but didn't work ;) what am I doing wrong?

when starting with A3 you basically start with 1 piece A4 and 1 piece A5, leaving 2 possible options:
- pick A4 first -> cut in half, now you have 2 A5 pieces (outside the envelope, the other one is still inside), pick 1 and put the rest back, so the envelope contains only two A5 pieces. Next step you take 1 of 2 -> 2 choices. So this 'branch' delivers a total of 2 paths without occurrences of single paper in the envelope.
- pick A5 first, remove it, next step only A4 (single!), cut it in half, pick an A5 and put the other one back. So here is 1 branch with a single occurrence.

total 3 branches possible, 1 of which has an occurrence of 1 paper. So expected value would be 1/3 * 1 + 2/3 * 0 = 1/3
where am I going wrong?
mdean
Posts: 171
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 151

Post by mdean »

woega wrote: Fri Sep 06, 2019 12:03 pm when starting with A3 you basically start with 1 piece A4 and 1 piece A5, leaving 2 possible options:
- pick A4 first -> cut in half, now you have 2 A5 pieces (outside the envelope, the other one is still inside), pick 1 and put the rest back, so the envelope contains only two A5 pieces. Next step you take 1 of 2 -> 2 choices. So this 'branch' delivers a total of 2 paths without occurrences of single paper in the envelope.
- pick A5 first, remove it, next step only A4 (single!), cut it in half, pick an A5 and put the other one back. So here is 1 branch with a single occurrence.

total 3 branches possible, 1 of which has an occurrence of 1 paper. So expected value would be 1/3 * 1 + 2/3 * 0 = 1/3
where am I going wrong?
Are each of those branches equally likely?
Image
woega
Posts: 2
Joined: Fri Sep 06, 2019 11:51 am

Re: Problem 151

Post by woega »

mdean wrote: Fri Sep 06, 2019 4:27 pm Are each of those branches equally likely?
yeah thanks, got me thinking and I was finally able to solve it. gracias!
Circling
Posts: 10
Joined: Wed Sep 16, 2020 7:33 am
Location: Earth
Contact:

Re: Problem 151

Post by Circling »

So here is how I understand how the "cut in half" procedure works:
Step one: Pull out a paper from the envelope. In this case, it is an A2 paper.
Step two: Cut the A2 to get two A3's
Step three: Cut one of the A3's to get two A4's
Step four: Cut one of the A4's to get two A5's
Step five: Take one of the A5's, put everything else in the envelope.

So in this case, if we had 1 A2 and 1 A5, we end up with 1 A3, 1 A4, and 2 A5's.

If this interpretation is correct, then my code should work. And yet, it returns 23 / 9 when starting with 1 A3 paper (5 / 9 if the 2 batches are excluded)
Problem 54 is terrible
mdean
Posts: 171
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 151

Post by mdean »

Your interpretation of the procedure is correct. The conclusion is not correct.
Image
Post Reply