4
$\begingroup$

This question already has an answer here:

On some island, the population is split into native people and into outlanders. There are more natives than outlanders.

Someone with extreme logical and mathematical thinking wants to know who are the strangers and who are the autochthons of this place, while asking as few questions as possible.

Feasible questions are:

  • Are you a foreigner on this island?
  • Is that dude a foreigner on this island?

Now .... we know that natives always tell the truth, whereas foreigners may lie whenever they want.

What is the minimum number of questions needed to find out who are the strangers and who are the autochthons on the island?

Hint:

the number works especially with big populations

$\endgroup$

marked as duplicate by Lopsy, Gamow, Haobin, Len, Tryth Feb 15 '15 at 2:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ No other questions allowed? $\endgroup$ – Ross Presser Feb 14 '15 at 2:07
  • 1
    $\begingroup$ You say "foreigners lie whenever they want". Does that mean they always lie or just that they can lie but don't always lie? $\endgroup$ – Duncan Feb 14 '15 at 2:19
  • $\begingroup$ @Abidare001, what's your native language? Can you write the puzzle down in your native language and post it in a pastebin. I don't want to be a pain, but there are some things we're not quite understanding like: I honestly didn't believe "autochthon" was a word :). Does outlander = stranger? Do foreigners sometimes tell the truth? Does "ask anyone" mean they can ask multiple people, or they can ask anyone they want (but just one person)? Is the minimum always the same (if foreigner says yes i'm foreigner, you know he's a foreigner)? $\endgroup$ – Millie Smith Feb 14 '15 at 3:04
  • $\begingroup$ Lastly (ran out of space): Are we just trying to figure out if one person is a foreigner, or are we trying to figure out the whole population. Anyway, I'm probably overthinking this. $\endgroup$ – Millie Smith Feb 14 '15 at 3:06
  • $\begingroup$ @Duncan i v already told that foreigners lie or tell the truth randomly or accoding to their mood ... doesnt matter. $\endgroup$ – Abr001am Feb 14 '15 at 9:00
3
$\begingroup$

Let $n$ and $s$ be the numbers of natives and strangers, respectively. We are told that $n > s$ and that natives always tell the truth but strangers lie when they wish.

As stated, the puzzle requires an inquirer to ask just one individual ("ask anyone") a series of questions to separate the set of all natives from the set of all strangers.

Now, had the strangers been incapable of telling the truth, you would be able to craft questions that produce consistent answers (e.g. "How many natives would a liar never say there are?"). But since the strangers can tell the truth but also can lie, their answers are unreliable. So if the inquirer picked a stranger, the answers need not take any element of the inquiry into account. In that case, no set of questions would give you certainty and the puzzle has no answer. At best, the inquirer can tell they are talking to a stranger, but cannot compel the stranger to produce the correct answer.

However, consider a variant where the inquirer can ask multiple people multiple questions. Then one strategy is to ask each person, "Who are the natives?" and go with the majority. Here, it doesn't matter what the strangers say - if they tell the truth, they contribute to the majority, and if they lie, they are in the minority anyway. For this strategy to work, the number of natives questioned must be greater than the number of strangers questioned, so in the worst case, $2s + 1$. Since $n>s$, we also have $n+s > s+s \geq 2s+1$, so there are enough people to ask. However, this assumes knowledge of $s$, which may not be the case.

If $n+s$ is odd, then from $n>s$, we have $n+s \geq (s+1) + s$, i.e. $n+s \geq 2s+1$.

If $n+s$ is even, then from $n>s$, we have $n+s \geq (s+2) + s$, i.e. $n+s \geq 2s+2$, or $n+s-1 \geq 2s+1$.

So according to this strategy, the answer is $2s+1$ questions if you know $s$, otherwise it is $n+s$ for an odd population and $n+s-1$ for an even population.

Is there a better strategy?

Since strangers provide no information, any optimal strategy will need to include asking at least one native and be able to tell when at least one native has answered. In the worst case, an optimal strategy will require $s+1$ questions, but since the inquirer doesn't know $s$, we're back to a total of $n+s$ questions for odd populations and $n+s-1$ for even populations.

$\endgroup$
  • $\begingroup$ have i mentionned the part of "permitted questions" in proper english ???? $\endgroup$ – Abr001am Feb 14 '15 at 9:20
  • $\begingroup$ @Abidare001 Sorry for missing your intent. You are correct, of course, though the phrasing in your question could be construed as an inclusive list rather than an exclusive list. To restrict questions to those two, each 'question' in my answer is really ($n+s$) of the permitted questions. A naive correction would be to multiply the tallies by ($n+s$). Nevertheless, those answers discuss a variant to your question. The direct answer to your puzzle in my paragraph 3 does not rely on what question is asked, whether one of your two or something else. $\endgroup$ – Lawrence Feb 14 '15 at 12:51
  • $\begingroup$ its ok but somone above accused me of misexplaining my problem ... i thought it is exclusive option when i said "permitted" $\endgroup$ – Abr001am Feb 14 '15 at 13:18
0
$\begingroup$

Seems that some people here dont get me properly !

here is an erronous approach proposed as a bad solution-exemple since there is a solution with less questions.

Lets make $n$ the number of inhabitants .

Lets say the inquisitor will ask the first $n-1$ population about some dude.

There should be a majority of these $n-1$ telling the truth .... So we exclude the minority who says opposed thing as the majority and We mind results.

Afterwards , We ask the elite about other different dude and etc until we ask about $n/2$ persons.

Now .... .

The wost case .... is when the first half-1 asked about folks are all foeigners ... and all the questionned guys said about em they r foreigners .... so the remaining $n/2$ member should be native and without any supplementary pain we know that him including the last asked $n/2$ guys are all natives

the number must be in this case = $n-1 + n-2 + ..... + (n/2+1)$ it is an arithmetic sum and it is false !

$\endgroup$

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