Problem 339

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.
qecc
Posts: 1
Joined: Sun May 22, 2011 5:03 am

Problem 339

Post by qecc » Sun May 22, 2011 5:07 am

Problem 339 (View Problem)

I am confused by the descriptor of "final" for the expected final number of black sheep. Is there any additional information about how long the process goes on for sheep to bleat and cross over? Would not a maximal number of black sheep be achieved by simply waiting (perhaps a very long time) until all of the sheep happen to be on the black side?

Thanks for any assistance/clarification.

Edit: removed extraneous spaces in above link
Last edited by qecc on Sun May 22, 2011 5:40 am, edited 1 time in total.

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

Re: Problem 339

Post by TripleM » Sun May 22, 2011 6:14 am

Agreed.. I can't see any reason for E(5) not to be 10.

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

Re: Problem 339

Post by jaap » Sun May 22, 2011 7:13 am

Clearly, if you wait long enough (and don't remove any white sheep), eventually all the sheep will be black or all the sheep will be white. So the number of black sheep is either 0 or 10, but the expected number will lie somewhere in between, depending on the probabilities of those two outcomes.

User avatar
BostonBear
Posts: 17
Joined: Thu Apr 28, 2011 3:48 am
Location: Saugus, MA

Re: Problem 339

Post by BostonBear » Sun May 22, 2011 7:42 am

I agree this could have been worded better. You are supposed to selectively remove some white sheep to ensure that you always have some black sheep. What I don't understand is the 2.1 kids type number that is given as E(5). I think you are supposed to cast the die, in essence a very large number of times to get an average, so you get 6871346 black sheep out of 10**7 games giving you an average of 6.871346. The problem I have with this is the random number generator used could affect the quality of the outcome. I am seriously shocked that so many people have answered this already.. there has to be a trick to it.

Susanne
Posts: 32
Joined: Sun Nov 08, 2009 7:39 am

Re: Problem 339

Post by Susanne » Sun May 22, 2011 7:49 am

Are there any books where optimal strategies are explained?
Image

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

Re: Problem 339

Post by TripleM » Sun May 22, 2011 7:53 am

jaap wrote:Clearly, if you wait long enough (and don't remove any white sheep), eventually all the sheep will be black or all the sheep will be white. So the number of black sheep is either 0 or 10, but the expected number will lie somewhere in between, depending on the probabilities of those two outcomes.
True, that explains why the answer isn't 10.

However, the problem statement doesn't say what happens when a sheep bleats and there is no sheep left of the other colour, nor does it say what 'final' means. Do sheep bleat infinitely until there are no sheep of one colour left, and then all the sheep become mute, or does 'final' mean 'at any point you choose'?

User avatar
BostonBear
Posts: 17
Joined: Thu Apr 28, 2011 3:48 am
Location: Saugus, MA

Re: Problem 339

Post by BostonBear » Sun May 22, 2011 8:28 am

You have to read this carefully and then do some guesstimating. you can REMOVE a number of white sheep so that the total is less than what you started with. if the first sheep that bleats is black you can remove the remaining four white sheep and end up with 6 every time. if the first sheep that bleats is white you can remove all 6 and end up with 4 black sheep every time. the trick is to figure out how many to remove. what my problem is, is how to *randomize* the bleating.. even when I don't remove any (which should give you 50 percent 10 black and 50 percent 10 white), my avg over many iterations is in the 4+ range every time which means pythons randint isn't all that random. I believe the question is worded that the final result is when there are no white sheep left.

mkch
Posts: 3
Joined: Sun Mar 13, 2011 5:30 am

Re: Problem 339

Post by mkch » Sun May 22, 2011 2:20 pm

I agree with others here that the problem is not clearly stated. When is final state achieved? Can a sheep, that already bleated once, bleat again, i.e. change colors repeatedly? From jaap's reply it seems that bleating stops when all sheep are of the same color, but it is not clear at all from the wording of the problem.

User avatar
hk
Administrator
Posts: 10482
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 339

Post by hk » Sun May 22, 2011 2:40 pm

If a black sheep bleats, a white one, if there are any white ones left, crosses over and turns black.
If a white sheep bleats, a black one, if there are any black ones left, crosses over and turns white.

So it is NOT the bleating sheep that changes colour.

If no sheep of the opposite colour remain the bleating obviously has no effect any more and the bleating goes on forever without any effect, so that obviously represents the final situation.
It seems all perfectly clear to me from the italicised text that isn't cited for nothing:

"And he came towards a valley, through which ran a river; and the borders of the valley were wooded, and on each side of the river were level meadows. And on one side of the river he saw a flock of white sheep, and on the other a flock of black sheep. And whenever one of the white sheep bleated, one of the black sheep would cross over and become white; and when one of the black sheep bleated, one of the white sheep would cross over and become black."
Image

mkch
Posts: 3
Joined: Sun Mar 13, 2011 5:30 am

Re: Problem 339

Post by mkch » Sun May 22, 2011 3:12 pm

Oops, indeed I am amazed at myself how I could have got it so wrong even after rereading it couple of times. Indeed, it is perfectly clear. Sorry for jumping to post and thank you for reply.

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 339

Post by quilan » Sun May 22, 2011 4:14 pm

Doh, I came here for the exact same reason. I have no idea how I passed over the opposite color distinction, even though I'd read the passage twice. Selective blindness I suppose.
ex ~100%'er... until the gf came along.
Image

wrongrook
Posts: 284
Joined: Sat Oct 17, 2009 9:39 pm

Re: Problem 339

Post by wrongrook » Sun May 22, 2011 4:36 pm

Does the optional removal of white sheep happen:
A) Once only, immediately after the first sheep has crossed?
B) Every time a sheep has crossed?

EDIT
Trying B gives the matching answer for the N=5 case.

User avatar
hk
Administrator
Posts: 10482
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 339

Post by hk » Sun May 22, 2011 6:26 pm

wrongrook wrote:Does the optional removal of white sheep happen:
A) Once only, immediately after the first sheep has crossed?
B) Every time a sheep has crossed?

EDIT
Trying B gives the matching answer for the N=5 case.
Yep
"And whenever one of the white sheep bleated..."
Image

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

Re: Problem 339

Post by jaap » Sun May 22, 2011 6:38 pm

hk wrote:
wrongrook wrote:Does the optional removal of white sheep happen:
A) Once only, immediately after the first sheep has crossed?
B) Every time a sheep has crossed?
Yep
"And whenever one of the white sheep bleated..."
I think the wording on this is not so clear. The sentence you quote does not mention the removal of sheep. The only one that does is:
After a sheep has bleated and a sheep from the other flock has crossed over, Peredur may remove a number of white sheep in order to maximize the expected final number of black sheep.
This can easily be interpreted as "After one sheep has ...". Especially as it comes so soon after "Initially each flock consists of n sheep.", so it can feel like it only applies to the situation immediately following the start.
I think the wording could be improved slightly. Maybe it should say "Each time a sheep has ..."

decaf
Posts: 3
Joined: Sun May 22, 2011 7:10 pm

Re: Problem 339

Post by decaf » Sun May 22, 2011 7:17 pm

never mind - had a stupid error.
Whoa. The formulation I found quite clear. Though I struggle on finding the optimal strategy.

So far the best I get is around 6.05 for the E(5). I obtain this by simulation. I am curious - did go obtain the proper value by a similar strategy - or is there some theory I'm unaware of?
Last edited by decaf on Sun May 22, 2011 8:38 pm, edited 1 time in total.
Image

User avatar
hk
Administrator
Posts: 10482
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 339

Post by hk » Sun May 22, 2011 8:30 pm

jaap wrote:This can easily be interpreted as "After one sheep has ...". Especially as it comes so soon after "Initially each flock consists of n sheep.", so it can feel like it only applies to the situation immediately following the start.
Each time a sheep has ..."
That wouldn't give you the value for E(5) that is given.
Example values are given to rule out misinterpretations.
(See also wrongrook's post).
Image

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

Re: Problem 339

Post by TripleM » Sun May 22, 2011 9:06 pm

hk wrote:If no sheep of the opposite colour remain the bleating obviously has no effect any more and the bleating goes on forever without any effect, so that obviously represents the final situation.
The problem statement says every single time a sheep bleats, a sheep from the other flock crosses over.

While it may be obvious to you what is intended, there is no denying that is simply not a true statement, and it certainly wasn't obvious to me that having all sheep of one colour was the 'final' situation talked about. I had to guess what the problem intended to solve it, which I've never had to do for any other Project Euler problem.

User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 9:43 am
Location: Netherlands

Re: Problem 339

Post by Lord_Farin » Mon May 23, 2011 5:47 am

Just a small wording problem: The problem description says 'Peredur vab Efrawc', while the text talks about 'Peredur, son of Evrawc'. I take it that 'vab' means 'son of', but could the spelling of 'Evrawc' please be applied consistently?
Image

User avatar
hk
Administrator
Posts: 10482
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 339

Post by hk » Mon May 23, 2011 10:43 am

I've changed the title into "Peredur fab Efrawg" which is the spelling of the Welsh wikipedia: http://cy.wikipedia.org/wiki/Peredur_fab_Efrawg
However, according to that wikipedia in Middle Welsh it should be spelled: "Peredur vab Efrawc".
I removed the name from the link to the English source we are citing.
If you would google on something like Peredur son of ... you'd be astonished by the numerous spellings you would encouter.
So any further inconsistencies are not our fault but are caused by the fact that there doesn't seem to be a consistent spelling.
In fact that's not so strange as it concerns a medieval text.
In fact I'm thinking people shouldn't be so nitpickingish about this problem.
Image

Junuxx
Posts: 4
Joined: Thu May 12, 2011 10:50 pm

Re: Problem 339

Post by Junuxx » Mon May 23, 2011 1:46 pm

Well, finding the optimal strategy was easy. Now for finding the answer for big n...
Image

Post Reply