You are sent on a mission to buy two new chicks. The mandate is clear – return with two chicks; one male, and one female.
You enter the supply store and the shopkeeper points you to a cage in which there are a dozen chicks. He tells you that half of them are male, half are female, and to help yourself. The problem, however, is that you are not an ornithologist, and all the chicks look the same to you. You can’t tell which are male and which are female.
You ask for assistance, and the shopkeeper (who happens to be an expert in the gender classification of chickens) offers to help. He says that you can bring any set of chicks to him and he will tell you how many males are in that batch (without individually identifying any of them; just telling you the count of males in that set).
What strategy should you employ to efficiently obtain a pair of chicks (one male, and one female) using the smallest number of identification events? Using this strategy, what is the worst case for the number of times that you will need to ask the shopkeeper for help?
What strategy should you employ to efficiently obtain a pair of chicks?
Sure, you could bring them out individually, and the first chicken is a gimmie, but finding the opposite gender for the second chick is down to luck. You could get it on your first try, but it might take up to another six tries to find an opposite.
If you brought half to the shopkeeper, unless you were very lucky and picked all the same gender, you’d then have to worry about how to identify a pair from the six you had.
There has to be a better (and more predictable) way …
Advertisement:
Answer
The answer is that is always possible to do it with just two trials.
Solution
The key to the solution is to select four chicks for your first test batch. The shopkeeper will give you one of five possible answers: No males, One male, Two males, Three males, All males. These responses are depicted in the five rows below (without loss of generality, I’ve put the males on the left, even though we can’t individually identify them). In these diagrams I’ve given the male chicks red plumage so it’s easier to follow along.
Let’s go through each case in order.
No Males
If we have no males, then sample #1 must contain all females. What we do next is pull out two more chicks for the second sample.
One of three results will happen:
You pull out two more females. If this happens, we have identified all the chicks! All the chicks remaining in the cage must be males. We simply take any chick from the six we pulled out (all females), and any chick still in the cage (all males), and we are done!
If the shopkeeper tells us that there is one male in the pair we have, again we are done! We are already holding in sample #2 exactly what we need; one of each.
If the shopkeeper tells is there are two males in sample #2, then we take one chick from sample #2, and one chick from sample #1.
One Male
If the shopkeeper tells is that there is one male in the batch, we split sample #1 in half, and present two of the chicks as sample #2.
We don’t know, specifically, the gender of the chicks we’ll select for the second sample, but for sample #2, there are only two possible outcomes {FF, MF}:
If the shopkeeper tells you there are no males in sample #2. This means the two chicks from sample #1 that you did not select for sample #2 must be an opposite pair, and you can purchase those two.
If the shopkeeper tells you there is one male, you are holding exactly what you need in sample #2.
(There is no possibility of sample #2 containing two males, as there was only one male in sample #1).
Two Males
If the shopkeeper tells you that there are two males (and thus two females) in sample #1, then again you split this first batch in half and present a subset of two chicks as sample #2.
This time there are three possible outcomes:
If sample #2 contains no males, then you have partitioned sample #1 into females (which are in the new sample), and males (which are the two from sample #1 that you did not reselect). Simply take one chick from sample #2, and one chick from the complement of sample #2.
If you are told that sample #2 contains one male, then your job is done. You have the two chicks you need.
If sample #2 contains two males, then it’s simply the inverse of the first possibility. Again, take one from sample #2, and one from the complement set.
Three males, All Males
With a little thinking we can see that the three male, and all males (four males), possibilities are just reflections of the one male and no male answers (respectively), and the solution is just the same but with the genders reversed, and we can apply the same strategies.
We’ve shown that every possible case can be accounted for in just two samples.
Update
The above solution minimizes the maximum regret of solving the puzzle. The solution always requires two moves; never more, never less. It is possible to solve with a lower expected value than two, but a downside is that occasionally a configuration can be encounted that takes more than two moves. You can read about this solution here.
Image: Lorna Mitchell
