# Can you find and capture a shapeshifter?

A town was invaded by aliens, and some of its residents were kidnapped and replaced by shapeshifters. You're tasked with capturing one of the shapeshifters. Here's the setup:

• There are 7 residents of the town.
• At least 4 of the residents are humans, and the remainder are shapeshifters. Everyone knows everyone else's type.
• Humans always tell the truth. Shapeshifters can answer however they want.
• If you ask anyone (whether human or shapeshifter) a question that a human couldn't truthfully answer yes or no to (e.g., "is the answer to this question 'no'?"), their head explodes and you die in the resulting explosion.

You can only ask each resident a single yes-no question. Once you get answers from all 7 residents, you need to pick someone to capture. Is it possible to guarantee you'll capture a shapeshifter?

Bonus 1: What if the alien story was a hoax, and everyone in the town is a human? Will you realize this with your strategy, so that you don't accidentally capture a human?

Bonus 2: Can you adapt your answer to towns with arbitrary numbers of residents, as long as there's always a majority of humans?

I came up with this myself. It was inspired by Kill the jokers! - Part 1 and Part 2, but designed so that the strategies given in their answers won't work for this puzzle.

Hint:

Follow one strategy until someone accuses someone else of being a shapeshifter, then follow a second strategy for the rest of your questions.

• Would an answer which addressed neither bonus be acceptable? Apr 16 at 2:52
• @bobble Yes, but I recommend you try for them anyway. The first one in particular is rather easy, and I expect that you might even "accidentally" solve it with your solution to the main puzzle. Apr 16 at 2:53
• Hmm, bonus #2 is tricky for me :/ Everything crumbles once I hit n=9... Apr 17 at 21:08
• @LukasRotter If you have the main portion of the problem solved, post that as an answer and I'll give you a hint how to modify it to reach bonus #2. Apr 17 at 21:09

Okay, I've been breaking my head for several days already but found a solution for 7. Your tip helped a lot!

Lets denote:

• S - shapeshifter, H - human
• ?x - unknown person number x, * - any person
• ?-? or ?+? - when person on the left was asked "Is next person is Human?" and got Yes(+) or No(-)

We will ask question "Is next person a Human?" in a chain, like some person ask another, then this another person ask yet another and so on. And stop as soon as somebody will say "No". Observation: when the answer is "No", then it could be only H-S or S-*, i.e. there is 100% a shapeshifter in this pair.

There could be multiple situations.
1) We got answer "No" on 4th person or later. ?+?+?+?4-?5 ??. Then the person 4 is H and person 5 is S. Proof(negation): If person 4 is S, then all people before him are also S (because otherwise we will get at least one more "No") but that means we have >=4 shapeshifters which contradicts the setup.
2) We got "No" on 3rd person. ?+?+?3-?4 ???. Then we ask 4 remaining people about person 3. Here could be 2 situations: everybody says "No" -> then he is S. If some say "No" and some "Yes", then he is H. Proof(negation): if he was actually S, then all people before him are also S (see proof above), but that would mean that we already have found 3 shapeshifters, and those 4 remaining people are H, which means they should've answered all "No", thus contradiction => person 3 is H and person 4 is S.
3) Situation when we have "No" on 1st or 2nd person - here approach is the same. Lets assume following situation: ?1+?2-?3 ?4?5?6?7. We know, that there are no more than 3 shapeshifters, and one of them either person 2 or 3. That means among people 1,4,5,6,7 there are at most 2 shapeshifters. Lets ask persons 1,4,5,6,7 same question about person 2. Then majority wins, because shapeshifters are less than half of those people.
Bonus 1: If all people said "Yes", then there are no shapeshifters

EDIT for Bonus 2:

Without loss of generality, let's assume we have 2n + 1 people, among whom at most n shapeshifter.
$$\underbrace{?~+?~+\!\ldots~+?}_{n-x~people}~-?~~\underbrace{??\!\ldots??}_{n+x~people}$$
Corner case where x < 0(i.e. we asked already more than half people) its similar to 1) above.
Strategy: ask all remaining n+x people question "Is this person a Human?" about the one who gave us "No" answer. Observation: There are at most n-1 shapeshifters among the remaining people and thus at least x+1 humans. Here could be couple of situations:
1) Everybody said "No", except maybe x people who said "Yes". Then target person is S, because we know there are at least x+1 humans, so they all answered "No".
2) If we got more than x "Yes" answers. Then target person is H. Proof(negation): If target was S, then all people before him are also S (n-x people) and thus there are at most x shapeshifters among the remaining people. But that would mean that only those x shapeshifters could've said "Yes", although we have more than x "Yes" answers. Contradiction!

• You're really, really close to the bonus 2 solution. Apr 21 at 23:30
• @JosephSible-ReinstateMonica I've updated the answer with general solution Apr 22 at 13:47
• Let's say that the chain is SSSHHHH . Then everybody can answer "yes" to, "Is the next person a human?" How then will your strategy work for the first question ? May 10 at 19:48
• @HemantAgarwal last H will say "no" about first S May 11 at 9:52

This only works with n=7 and n=8 yet....

Arrange them in a circle, everyone facing to the center. Ask each person if the person to the left of them is human. After you got their answers, you can safely kill someone with the below logic.

Logic:

Find the longest "chain" of consecutive "Yes" answers in a row. When this chain breaks, i.e. someone answers "No", kill the one next to that person (clockwise/their left). If there are multiple longest chains: If the amount of same-sized chains is even (i.e. equal to 2 in this case), pick any of them and do the same. If it is odd (i.e. equal to 3 in this case), pick the person who "stands between two NOs", i.e. they answered No and the person to the right of them answered No.

This works because:

In the case that there is a single longest chain:
Humans are in the majority, and will always (help) build the longest chain we'd look out for. Obviously, if all humans stand next to each other, they will have the largest chain. If there are spread out as widely as possible, let's say in the case of 4 humans, there will still be 2 humans standing next to each other. If the shapeshifters were to answer "Yes" all the time in that scenario, the humans in between them would break that chain, not making it the longest one. If a shapeshifter "latches" on to the start of a human chain by answering Yes, it doesn't matter. It just makes the already correct chain longer. If shapeshifters happen to build a chain on their own and also end it with a "No", it will always be shorter or equal to the correct chain

If there are multiple chains of the same size:
Well, that was just pattern recognition and "no other arrangement would fit, so it must be ..." reasoning on my part. Don't really understand why that works yet, but it definitely does. Probably the key to bonus #2 as well.

Bonus #1

Everbody would answer Yes. Not possible with any other arrangement

Bonus #2

No idea yet. Everything crumbles once I hit n=9

• As promised, a hint towards bonus 2: rot13(Lbh fnl "Neenatr gurz va n pvepyr, rirelbar snpvat gb gur pragre. Nfx rnpu crefba vs gur crefba gb gur yrsg bs gurz vf uhzna." Lbhe nafjre sbyybjf gung dhrfgvbavat fgengrtl gb gur raq ab znggre jung. Gb trg obahf #2, fjvgpu gb n arj dhrfgvbavat fgengrtl evtug nsgre gur svefg "ab".) Apr 17 at 21:29
• @JosephSible-ReinstateMonica That indeed gives me some ideas, but I unfortunately should really go get some sleep now before I come up with something completely stupid :). Maybe that hint should also be edited into the question itself so everyone definitely sees it. Apr 17 at 21:51
• so ... after the first "no" start asking if non-human? Apr 22 at 4:33
• Ahem... You're tasked with capturing one of the shapeshifters. Bloodlust on your own time. Apr 22 at 15:37
• @BuhBuh Lol. I genuinely didn't even notice that. Apr 22 at 15:57

Note: the question was answered before this edit. Whether it's good to edit questions after a loophole has been found or not is still undecided, as far as I can see.

Maybe this is a bit of cheating (but I believe that it's still no ), but it easily works when

asking every resident a question involving some future event whose outcome is not known in advance (i.e. a random variable), e.g. "If I roll a fair die, will the outcome be 4?" or "If I ask you and a shapeshifter the same question, would you both give the same answers?" (aka "head-exploding questions" in The Hardest Logic Puzzle Ever). A human cannot answer this kind of question at all, since he/she does not know the outcome and so cannot tell the truth. On the other hand, a shapeshifter has no problem upon answering "yes" or "no", because both true and false answer is acceptable for him/her.
P.S. Obviously, this strategy works for both bonuses 1 and 2, since there's nothing special.

• I do indeed consider this cheating. I've clarified that causing head-explosions is a failure condition. Apr 17 at 21:06