"Alien Love" Puzzle

Question

There is a group of 10 aliens and each alien is either male or female. You don't know how many male or female aliens are in the group, but you know that exactly one of them is a "hybrid" male alien.

Every alien loves him/herself. Every male alien loves all the female aliens, and every female alien loves all the male aliens. The only exception is that the "hybrid" male alien loves both the male and the female aliens.

You don't know how to tell male and female aliens apart. You are to do some investigations in order to find out the gender of each alien, and also to determine which one is the "hybrid" male alien. Questions of only one kind are allowed: you can ask a particular alien privately if he/she loves an another particular alien. The two aliens are your choice. The alien will answer your question truthfully.

Can you find out the gender of each alien and also determine which one is the "hybrid" male alien by asking no more than 20 questions?

Answer 1

Looks like there is a guaranteed solution with a worst case limit of

only 19 questions. You can then use the remaining question(s) to let the aliens know that their game is up: ask the hybrid if it loves itself.

Here's the strategy:

Label the aliens with numbers from 1 to 10. Tentatively separate the aliens into two groups, A and B by the following procedure:

Place alien 1 in group A. Then, starting with alien 1, ask alien N if it loves alien N+1.
* if no, place alien N+1 in the same group with alien N
* if yes, place alien N+1 in the other group.
Use the first 9 questions to repeat this with all aliens up to 9.

This will give you a graph looking something like this:

Every line crossing over to the other side is a "yes" answer.

Then ask 10 if it loves 1. Now each alien has been asked exactly one question, and there are two possible scenarios:

a) The hybrid male was asked if it loved a female.
b) The hybrid was asked if it loved another male.
You can tell which scenario it is by 10's answer to whether it loves 1: If the answer is consistent with alien 1 belonging to the A group, then we have scenario a). If the answer would place alien 1 in the B group, we have scenario b). This is because the only way the graph can become inconsistent is that the hybrid's "yes" answer was misinterpreted as meaning that the hybrid and the other alien have different genders.

We need to handle each scenario separately. For scenario a)

The grouping is already correct, each group only contains aliens of one gender. If we can find the hybrid, we automatically also identify the groups' genders, since the hybrid is a male. You need at most 9 questions to identify the hybrid: ask each alien that hasn't already answered "no" if it loves an alien in the same group. The alien that answers ”yes” is the hybrid. If you get only "no" answers, and you have only one alien left, you can skip the final question, since the remaining alien is guaranteed to be the hybrid.

Special cases:
If there is no "other alien in the same group" that you could ask about, the case is much easier: there is only one member in one of the groups, so there have already been 8 "no"s. The special case where all the aliens are in the same group cannot occur, since the hybrid always answers yes. (even if the hybrid would be alien 10, the "yes" would make the graph inconsistent, which isn't possible in this scenario).

In the sample graph of above, if 10 answers ”yes”, we can save a couple of questions, since 2 and 9 have already answered ”no”, and are therefore ineligible.

Scenario b) takes more cleverness to solve, but maybe a bit surprisingly, not nearly as many questions.

In scenario b we have a clear inconsistency in the graph. We can isolate the inconsistency into a progressively smaller graph by doing a sort of binary search. Let's consider the worst case scenario, where every alien said yes except alien 10 (anyone who said "no" cannot be the hybrid; and there needs to be at least 1 "no" for the graph to become inconsistent). This can be solved as follows:

Ask 10 whether it loves 6. (We need to direct this question, and all the following ones, to a known non-hybrid alien to make sure we don’t introduce any new inconsistencies.) If the answer is inconsistent with the tentative grouping, then the hybrid must be one of the aliens 6-9. If, on the other hand, the answer is consistent with the grouping, we know that aliens 6-10 cannot be hybrid. Let's assume the answer is consistent. Next we ask 10 whether it loves 3, and again check if the answer is inconsistent. In the worst case, it is. In that case, the hybrid is either 3, 4 or 5. Two more questions will pinpoint the inconsistent answer, and thereby, the hybrid male.

With this method, we can isolate the hybrid surprisingly quickly. Once the hybrid is identified,

Change the grouping so that the hybrid's "yes" answer points to the hybrid's group, and swap all aliens with a number greater than the hybrid's number to the other group. This fixes the grouping, all answers should now be consistent, and the group with the hybrid is the male group.

Here's a sample solution (somewhat suboptimal but still way under the claimed worst case limit) from earlier with this method applied.

In this case, the aliens were originally
hybrid: 6
other males: 1, 4, 7, 9, 10
females: 2, 3, 5, 8

The questions asked after the first 9 were
"does 10 love 1" (no, inconsistent, enter scenario b)
(10 has said ”no”, so we can use it for the follow-up questions)
"does 10 love 6" (no, inconsistent -> the 10-6-7-8-9-10 loop contains the inconsistent answer)
"does 10 love 7" (no, consistent -> the 10-7-8-9-10 loop doesn't contain the inconsistent answer)
Therefore, the inconsistency was necessarily in 6's answer, so 6 is the hybrid. Swapping the group for 7,8,9 and 10 restores consistency to all answers. 6 is in group A, so group A is the male group. (It is now entirely up to your own judgement, whether or not you should next ask ”does 6 love 6” up to eight times.)

The worst case scenario for the whole method is 10 "yes" answers in the beginning,(scenario a), followed by 8 ”no” answers. As described above, this takes at most the mentioned number of questions to solve.

Answer 2

edit: as pointed out in comments, there's a flaw in this solution. I'll leave it up for now in case anybody else finds something useful in the approach; meanwhile I'll try to find a fix.

The following strategy guarantees finding a solution within at most 15 questions. Apologies for formatting, I'm still learning the ropes.

Let F stand for female, H for hybrid, and M for non-hybrid male. Note that if Alien Jo loves Chris but Chris does not love Jo, then Jo must be the hybrid and Chris must be a non-hybrid male. Note also that once we identify the hybrid, we can work backwards to identify any alien who's answered about the hybrid, and any alien who's answered about them, and so on.

We start by:

Splitting the aliens into four groups: A = aliens 1-3, B = aliens 4-6, C = aliens 7-9, with one alien (#10) in group D all by itself.

The basic strategy will be:

to ask questions within each of the groups of three and use the answers to narrow down the possible suspects, then ask a couple of further questions to confirm who the hybrid is. Once we know who the hybrid is, we'll pick one member from each of the other groups and ask their feelings about the hybrid; this tells us their gender, and we will then be able to identify the genders of their other group members by using the answers from the first round of questioning.

We start this by:

Within each of groups A-C, ask each alien about the next within that group e.g. we ask #4 about #5, #5 about #6, and #6 about #4. This takes 9 questions. Within each group of 3, there are four possible answer patterns (Y = yes, N = no):

1:

NNN: implies that this group must be MMM or FFF, cannot contain hybrid.

2:

NNY: can only be MMH, and the hybrid must be the one who answered yes.

3:

NYY: could be MMF, or FFM, or MHF. If MHF, then the N was the M referring to the H, so the only possible hybrid in this group is the one who was the subject of the "no". We can confirm or eliminate the hybrid with one more question: we ask our suspect how they feel about the one who gave them a "N", and if they answer "yes" they are confirmed as the hybrid, otherwise they're ruled out.

4:

YYY: can only be HMF. Note we can identify the hybrid in this group with at most two further questions, by reversing the direction of the questions. If Jo loves Chris but Chris doesn't love Jo, then Jo must be the hybrid; if Chris loves Lou but Lou doesn't love Chris, then Chris must be the hybrid; if Jo loves Chris loves Lou loves Chris loves Jo, then neither Jo nor Chris can be the hybrid, so it must be Lou.

Note that

We can't get both YYY and NNY, since that would imply two hybrids.

Case 1:

All of groups A-C give responses of NNN. None of them can contain the hybrid, therefore alien #10 must be the hybrid. We then pick one member from each of groups A-C (e.g. aliens #1, #4, and #7) and ask these three how they feel about #10 (the hybrid). Their answers will tell us their genders, and we can then work back within each group to deduce the gender of all other aliens. Total 9+3 = 12 questions.

Case 2:

One of our three groups A-C gives a NNY, so this group must contain the hybrid and the hybrid must be the one who answered yes. We then use the same method as for case 1 to get one identification within each of the other groups, and work backwards for the rest. Again, 9+3=12 questions total.

Case 3:

One of our three groups A-C gives us a YYY. We know the hybrid must be in this group, and we can find which one it is by asking at most two more questions (bringing the total to 10 or 11). We then need three more questions to identify one member of each of the other groups, for a total of 13-14 questions.

Case 4:

None of the groups gave us a YYY or NNY, and exactly one gave us NYY. We have one suspect within the NYY group, and as noted above it takes one question to confirm them or eliminate them as the hybrid. If eliminated, then #10 is the hybrid. Either way, we now know who the hybrid is, and three more questions give us the rest in the usual way. Total: 9+1+3 = 13 questions.

Case 5:

None of the groups gave us a YYY or NNY, and exactly two gave us NYY. This plays out exactly like Case 4, except that we may need to test two possible suspects to confirm who the hybrid is. Total: 9+(1 or 2)+3 = 13 or 14 questions.

Case 6:

All three of groups A-C gave us NYY. We now have one "suspect" from each of groups A-C (the ones who were the subjects of the "no"s), as well as #10 who is also a suspect. This plays out the same as case 5, except we might need a third test. Total: 9+(1, 2, or 3)+3 = 13 to 15 questions.

It can be proven that there is no method that will guarantee finding the answer in fewer than 13 questions:

Given 12 questions with yes-no answers, we can distinguish at most 2^12 = 4096 possible scenarios. With 10 possibilities for the identify of the hybrid alien, and then 2 possibilities for the gender of each of the other nine aliens, there are 10*2^9 = 5120 possible scenarios, so any strategy with only 12 questions cannot guarantee finding the correct answer.

So this leaves open the question of whether there's a strategy that guarantees a solution in 13 or 14 questions.

Answer 3

The answer given by Bass has a worst case which takes 19 questions to identify the hybrid. With some difficulty I managed to prove that this is pretty close to the best possible worst-case performance for this problem. For the problem given, any strategy has a worst case that takes at least 18 questions. More generally, if we have n aliens, the worst case for any particular strategy is at least 2n-2 questions.

Since asking an alien how it feels about itself never gives useful information, I will ignore that kind of question in the following discussion; all questions are assumed to be between two different aliens.

Some terminology:

The "solution" is identification of the genders of all aliens.

A "network" is a group of aliens who are all linked to one another, directly or directly, by a chain of questions, such that none of the aliens is linked to anybody outside that network. (The direction of the questions doesn't matter. If we ask A about B and B about C, then A, B, and C form a network; likewise if we ask C about both A and B.)

Initially, each of our n aliens forms a tiny network of size 1. As we ask questions, we will start merging small networks together into bigger networks. Any question asked between two aliens in different networks will merge those networks together; this kind of question will be termed a "network merging question" or NMQ for short.

Note that as long as we have a network N that does not contain the hybrid, it will not be possible to identify the gender of the aliens in that network. For any solution that's consistent with the answers for N, we could find another, different solution by switching the genders of all the aliens within N (female to non-hybrid male and vice versa).

Hence, in order to identify all aliens, we must merge all the networks together into one big network containing all n aliens. Since every NMQ reduces the count of networks by 1, it follows that we will need to ask exactly n-1 NMQs as part of getting all the information required.

With that out of the way, let's assume you have a strategy that would give you the solution in 2n-3 questions. Because the worst case depends on what questions you're asking, I'll define it as you go along, based on the questions that you ask. (You can think of it as playing against a jerk who gets to choose the answers as you go, subject only to the requirement that they're consistent with what you already know.)

Before we start, let's obtain n reversible hats, each with red on one side and blue on the other. We give each alien a hat and ask them to put it on (doesn't matter which way out, just pick one). The hats don't actually do anything, they're just a handy way of tracking what information we've obtained within each network.

You may now start asking questions, one at a time. When you ask Alien X whether they love Alien Y, the answers follow these rules:

• If X and Y have opposite-coloured hats, the answer will always be "Yes".
• If X and Y have same-coloured hats, and they are already within the same network, the answer is "No".
• If X and Y have same-coloured hats, and they are in different networks, all the aliens in Y's network reverse their hats (so X and Y now have opposite-coloured hats), and the answer is "Yes".

Three things to note:

• Any time you ask a NMQ, the answer will be "Yes".
• If X has answered "No" about Y, they must have same-coloured hats. (You only get a "No" from two same-hatted aliens who are already in the same network, and once they're in the same network, any hat reversals affect both of them, so they end up with the same colour again).
• If X has answered "Yes" about Y, they must have opposite-coloured hats. (Again, a "Yes" only happens between aliens with opposite-coloured hats, and any future reversals would affect both of them, so they remain opposite.)

Suppose that you have asked 2n-3 questions and connected all the aliens into one network (as noted above, this is a prereq for finding the required information). This means you've asked exactly n-1 NMQs; since NMQs will always be "Yes", that means there will be at most n-2 "No" answers.

From this, it follows that there must be at least two aliens in your network who have never given a "No" answer - let's call them Pat and Lee.

There are at least two different solutions that are consistent with all the questions you've asked:

1: Pat is the hybrid. Everybody else who has the same hat colour as Pat is male; everybody who has the other hat colour is female.

2: Chris is the hybrid, everybody who has the same hat colour as Chris is male, everybody who doesn't is female.

Hence the worst case requires at least 2n-2 questions (18 for the case where n=10).

Also, thanks for a very challenging and interesting puzzle!