Project Euler Forum

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

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

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.

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.

Are there any books where optimal strategies are explained?

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'?

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.

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.

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:

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.

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.

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.

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..."

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 ..."

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?

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).

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.

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?

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.

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