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

Don't post any spoilers
qecc
Posts: 1
Joined: Sun May 22, 2011 5:03 am

### Problem 339

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

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

jaap
Posts: 544
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Problem 339

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.

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

### Re: Problem 339

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

Are there any books where optimal strategies are explained?

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

### Re: Problem 339

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

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

### Re: Problem 339

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

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.

hk
Posts: 10638
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

### Re: Problem 339

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

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

### Re: Problem 339

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

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.

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

### Re: Problem 339

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.

hk
Posts: 10638
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

### Re: Problem 339

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

jaap
Posts: 544
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Problem 339

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

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.

hk
Posts: 10638
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

### Re: Problem 339

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.

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

### Re: Problem 339

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.

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

### Re: Problem 339

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?

hk
Posts: 10638
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

### Re: Problem 339

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.