5
$\begingroup$

It is the year 10,000,000,000, and materalisation has been invented. At the same time, Nintendo has materialised every single Pokémon (countably infinitely many now!) to fight against finitely many lions (neither the Pokémon nor the lions are hostile to any other species). You don't know exactly how many lions there are, only that it is a finite number (it could even be 0).

It is now the break before the fight. All the lions and Pokémon are standing in a line, but you have no way of telling who are the lions and who are the Pokémon.

You can ask anyone in the line a boolean combination of these questions:

  • Are you a lion?
  • Is the n-th in line from the left a lion?

The Pokémon and lions all know the identites of everyone in the line (first one on the left). All Pokémon tell the truth and only the truth, while all lions say yes or no randomly.

It will take you an infinitesimal amount of time to ask a question, so you can ask as many questions as you want (finitely or infinitely many) before the fight starts.

Question: How can you identify one Pokémon, asking the fewest questions possible?

(If infinitely many questions are asked, they are counted by order type, Asking positions from the left [1, 1, 2, 2, 3, 3...] would be $\omega$ questions, but asking [1, 2, 3, ..., 1, 2, 3, ...] would be $\omega \times 2$ questions)

$\endgroup$
1
  • 3
    $\begingroup$ I'll take my chances and say that the first guy on the left is a pokemon. After all, there's a 100% chance I'm right. $\endgroup$
    – Bass
    Commented Feb 20 at 9:13

2 Answers 2

7
$\begingroup$

I think the answer is

$\omega$

Proof of lower bound

For any given $N$, no matter who we ask or what questions we ask, it is always possible that we will just be questioning lions in the first $N$ questions and therefore cannot discern any information about where a pokemon might be.

Proof of upper bound

Consider the following sequence of asking positions [1,1,2,1,2,3,1,2,3,4,...] (we go down the line, increasing by one each time).
For a particular creature, the $N$th question we ask to that creature is "Is the $N$th in line from the left a lion?"

This set is in one-to-one correspondence with the integers and so has size $\omega$.
Note: As Bass pointed out in the comments this line of reasoning may not be so solid. Instead, we should say that as our set extends to infinity just once, this justifies the size to be $\omega$. I agree with Florian F that measuring set size using ordinals seems a little odd.

If the creature at any index is identified as a lion infinitely many times, they are a lion, otherwise a pokemon.

$\endgroup$
9
  • $\begingroup$ I'm not sure your last sentence works. A lion certainly has a probability of 0 of answering no infinitely many times, but when you're dealing with an infinite sample space that doesn't mean its impossible, just almost impossible. Isn't this essentially the same as Bass's comment under the question? The probability of the first creature in the line being a lion is also 0 but it seems intuitive that we can't just say it's a pokemon and call it a day. $\endgroup$ Commented Feb 20 at 15:21
  • $\begingroup$ @GoblinGuide Hm, I think you're right actually. There may, however, be a way to alter the approach. Let me think on it. $\endgroup$
    – hexomino
    Commented Feb 20 at 15:34
  • $\begingroup$ @GoblinGuide Okay, I've changed it to what I think is a better answer. $\endgroup$
    – hexomino
    Commented Feb 20 at 15:37
  • $\begingroup$ I'm by no means a mathologist, but I don't think you can equate ordinality to cardinality like that. $\endgroup$
    – Bass
    Commented Feb 21 at 21:10
  • $\begingroup$ As an example (and please correct me if I'm completely wrong here), if you ask every creature in an even-numbered position a question, you have asked $\omega$ questions. If you then follow up by asking the rest of the guys a question, that's another $\omega$ questions, for a total of $\omega \cdot 2$ questions, even though you have asked everyone only one question each. $\endgroup$
    – Bass
    Commented Feb 21 at 21:31
5
$\begingroup$

Here is an improvement over hexomino's answer. I.e. a simpler one.

You still need a countably infinite number of questions.

That this is minimal has been explained by hexomino.

This is how it is achievable.

Remember you only need to identify one pokémon.

Just ask every creature starting from the second from the left (from 2 to infinity) whether the one just left of it is a lion. In other words ask creature n whether creature n-1 is a lion.
The last creature to say 'yes' is a pokémon.
If nobody says yes, then all creatures are pokémons (pokémon-tachi?).

$\endgroup$
2
  • $\begingroup$ Sorry, it seems to be badly worded. Ask about the one on the left of the creature. So to creature n you ask "is creature n-1 a lion?". $\endgroup$
    – Florian F
    Commented Feb 21 at 21:32
  • $\begingroup$ Yes, this is a nice construction. $\endgroup$
    – hexomino
    Commented Feb 22 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.