Cherry-picking question

Cerebral distractions of every kind, mostly but not exclusively Countdown-related.

Moderator: Michael Wallace

Post Reply
Gavin Chipper
Post-apocalypse
Posts: 13215
Joined: Mon Jan 21, 2008 10:37 pm

Cherry-picking question

Post by Gavin Chipper »

There's a tube of yellow and orange sweets, and you prefer the yellow ones. There's an equal number of each and they're distributed randomly. It is a very long tube and it's transparent so you can see all the colours coming up. When you visit the tube, you can take as many sweets as you want, but it has to be at least one and you can only take them in the order that they're in - you can't skip any. If you go away and come back, loads of other people would have visited the tube in the meantime so everything is reset. If you play optimally, what proportion of your sweets would be yellow? And what is the optimum strategy?

I don't know the answer to this by the way.
User avatar
Charlie Reams
Site Admin
Posts: 9494
Joined: Fri Jan 11, 2008 2:33 pm
Location: Cambridge
Contact:

Re: Cherry-picking question

Post by Charlie Reams »

I'll look at this properly later, but at first glance it seems similar to the secretary problem.
Bob De Caux
Enthusiast
Posts: 265
Joined: Wed Sep 09, 2009 3:18 pm

Re: Cherry-picking question

Post by Bob De Caux »

Although it has some similarities to the secretary problem, the way Gev has phrased it seems to imply that you have perfect information, i.e. you'd never have to make a decision without knowing what is coming next. Assuming that the tube is not infinitely long (as you could surely then just wait for whatever proportion you want) and that you are under some time pressure for your decision, a good strategy would be to ignore the first sweet (you have to take it anyway), then:

i) if the next sweet is yellow, keep taking yellow sweets until the next orange sweet
ii) if the next sweet is orange, walk away in disgust


This is of course assuming that you play the game over and over again. I reckon you get 1.5 yellows to 0.5 oranges on average (see below). Maybe not optimal, but I think optimality may depend on interpretation of the question...

PROOF: Ignoring the first sweet, chance of exactly one yellow in a row is 1/2 (chance of yellow)*1/2 (chance of orange)=1/4, chance of two yellows is 1/2*1/2 (two yellows) *1/2 (orange)=1/8, three yellows is 1/2*1/2*1/2*1/2=1/16. Assuming the number of sweets is very large, your expected number of yellow sweets is 1*1/4+2*1/8+3*1/16+....=1. As the first sweet is 50:50, on each trip I would expect to pick 0.5 oranges and 0.5+1=1.5 yellows
Gavin Chipper
Post-apocalypse
Posts: 13215
Joined: Mon Jan 21, 2008 10:37 pm

Re: Cherry-picking question

Post by Gavin Chipper »

Some good thinking, but I'm not sure I'd always walk away at the first orange. If it went yellow, orange, yellow*10, I'd definitely take all 12. Regarding interpretation, maybe it would have a more definite answer if there was a set end point. So you have to take 100 overall, with as many visits to the tube as you like (well, it would be no more than 100). Although having said that, there should be an optimum strategy to maximise your long-term mean yellow percentage over the long term I would have thought, with no definite end point.
Bob De Caux
Enthusiast
Posts: 265
Joined: Wed Sep 09, 2009 3:18 pm

Re: Cherry-picking question

Post by Bob De Caux »

Sure - I can see that there is no way mine is optimal, but I think you do need some sort of cap, otherwise you could just keep looking ahead to see if you can improve ad infinitum - then it may start to look more like a variant of the secretary problem. To follow on from your idea of obviously taking the x yellows after the orange, (I think) you would do this if it gave you a better ratio than 3:1 (which is what you get with my original method)

EDIT: So on that note, if you can only take 100 sweets then I think the idea of taking an amount that "beats" 3:1 by as much as possible on any particular go is a better strategy than before (assuming you can see up to x sweets ahead, when you have x sweets remaining of your cap) - if you can't beat 3:1 then you walk away at the first orange. The 3:1 ratio would apply for any total cap and any residual amount as well, i.e. if you have taken 76 sweets, you would expect to average 3:1 for the remaining 24 sweets. Still not convinced this is optimal though...
Mark James
Kiloposter
Posts: 1771
Joined: Sat Oct 23, 2010 3:21 pm
Location: Dublin

Re: Cherry-picking question

Post by Mark James »

Just take all the sweets and give the orange ones away or eat them anyway. They're sweets, they can't be that bad.
User avatar
Jon O'Neill
Ginger Ninja
Posts: 4545
Joined: Tue Jan 22, 2008 12:45 am
Location: London, UK

Re: Cherry-picking question

Post by Jon O'Neill »

Post Reply