It is known that in a certain city there are a significant number of witches, even though this practice is forbidden. The problem is that nobody knows who these witches are, since a witch is very careful to appear to others as a perfectly normal person.

You are appointed by the Mayor to establish (as accurately as possible) how many witches are in the city. You are allowed to do a single phone call to every family in the town. In general, you can expect a sincere response to your questions, excepting of course the case when a truthful answer would cause a witch to disclose herself.

How would you carry on your job?

[updated – more specifics]

Let’s assume that you must determine the number only through phone calls. The only thing you have is the list of phone numbers to every family in the town (no credit card information, you cannot hire private investigators, etc).

Also, let’s assume that witches are pretty good to appear as “innocent” people. Psychological tricks won’t work, or even if they do, you cannot use them as a reliable source of information.

Finally, let’s assume that witches don’t really know each other, although assuming the contrary would be an interesting variation of the original problem.

Research the materials used by the witches in their practice, and buy the purchasing information from credit card companies for my geographical area regarding those purchases.

The witches won’t reveal themselves, but it says nothing about them revealing other witches.

Assuming that witches would know other witches, I’d call and ask them if the neighbor to their left is a witch, and then if the neighbor to their right is a witch.

If witches are unable to discern if other people are witches, I’d call each house and say, "I’ve been told that you’re a witch." If the people on the other end attacked the results, i.e. "No I’m not," I put them in the "not-a-witch" category. If they attack the evidence, i.e. "Who told you that?" I’d put them in the "witch" category.

(It’s a nice rule of thumb when investigating people. The innoncent question the results, the guilty attack the evidence.)

Call the local Republican Party who will no doubt carry out a full investigation.

More specifics:

Let’s assume that you must determine the number only through phone calls. The only tyhing you have is the list of phone numbers to every family in the town (no credit card information, you cannot hire private investigators, etc).

Also, let’s assume that witches are pretty good to appear as "innocent" people. Psychological tricks won’t work, or even if they do, you cannot use them as a reliable source of information.

Finally, let’s assume that witches don’t really know each other, although assuming the contrary would be an interesting variation of the original problem.

I know.

1) Call each family and offer them the NEW AND IMPROVED SuperDuper TurboDicer for only $99.99 (as seen on TV!) in the most obnoxious way possible. Mention you’ll throw in a set of Ginsu knives if they BUY RIGHT NOW!!

2) Arrest anyone who threates to turn me into a frog.

3) Profit!

Well if psychological indica won’t work,and witches would not recognize other witches, then you’re pretty much screwed.

Your only probe is your questions. A query as to whether or not the person in question is a witch will always return false. A query as to whether or not the person in question knows of other witches is an invalid query.

The only likely scenario I can think of is to call at midnight on a full moon and mark those who do not answer as witches, although that implies that witches will never miss work and that regular people would answer the phone in order to tell whoever is calling not to call at midnight.

BTW – this puzzle has a solution ðŸ™‚

The trick is to give everyone plausible deniability.

Tell each person to grab a six-sided die and roll it. If the answer is 1, 2, 3 or 4, then tell the truth about whether you are witch or not. If the answer is 5 or 6, then lie (i.e., if you’re a witch say "no" and if you’re not a witch say "yes").

Let W be the number of people who say they’re a witch and N the number of people who say they’re normal.

Then the number of witches in town is approximately 2W-N.

For higher accuracy (but higher degree of citizens who refuse to participate in your survey), have them lie only if they roll a 6 (in which case the number of witches is approximately (5W-N)/4).

For more detail about methods to try for testing when asking ’embarassing questions’, including methods to minimize variance, read the first few pages of:

http://www.statslab.cam.ac.uk/~rrw1/stats/digress.pdf

Actually, read the whole thing, full of interesting examples.

Excellent solutions!

Adi

Clearly, you can’t ask a callee if they are a witch, true witches are going to lie to you.

The key is to craft a question that gives you the information you want regardless of whether the callee tells the truth or lies. The way to do this is through the use of conditional statements creating double negatives.

1) Call from an unlisted phone that can receive phone calls.

2) Call first house.

3) When person answers the phone, tell them

"Congratulations, you just won…" <click> hang up the phone!

4) Repeat for every house.

5) Every person that calls back to see what they won means that there’s a witch there.

Because the number was unlisted, they had to use their witch powers to figure out what number to call.

Of course witches can’t read minds, so they wouldn’t know they didn’t really win anything.

Building on Raymond’s post, I would posit that not only do you need to offer plausible deniability, but you also need to make it extremely easy for witches to remove themselves from the equation by having them all pick the same result.

It’s safe to assume that witches will always give the answer most likely to protect themselves, whereas non-witches will give you an "honest" answer. If you ask the callee to lie on a 6 out of 6, then you’ll end up getting 5 out of 6 non-witches to say "no", whereas 1 out of 6 will say "yes". All witches, however, will say "no" since saying "yes" means that there is a 5 of 6 chance that they’re a witch, which is a risk they have no reason to take–especially given that none of them are expected to be aware of what the others respond.

Using this theory, suppose you call 300 people and get 290 "no" and 10 "yes" answers. This means that 10 people who rolled 6 of 6 gave an honest answer, resulting in an estimated 60 non-witches. If you get 30 people saying "yes" (indicating 180 non-witches), then you’ll end up with 120 witches.

Ask each family how many people in the family are witches.

Raymond’s answer is along the right lines but it is still wrong.

It fails to take into account the fact that you only have the phone number of a FAMILY, not individuals.

You therefore need some way of working out HOW MANY witches are in a given household, which is a very hard problem. For a start, it’s pretty clear that making assumptions about independence would be bad, which then means that ‘multiplication’ of probability distributions is hugely nonintuitive…

1) How many people are in your household?

2) How many are witches?

This would not reveal themselves as witches unless all were witches. Discounting any households where the number is either 1 less than the number of residents or 0 you could determine the average number of witches per capita and then apply that to the total count of people.

The other option is to take a poll of how many people would be against the town purchasing a witch detector with fines for witchery being used to pay for the equipment. Only witches would be against such a program being implemented.

Neither of these are probably the correct answer, but they would come up with an answer that I am sure the mayor would be willing to consider reasonable enough to pay me for the work.

Ok, I think the more important question is how does a person know how accurate their answer is?

Since you referred specifically to witches being female in the question, that narrows it down to approximately half the population. So if one said 25% (half of that again) would be within 25% of the total population for accuracy. Since you said that there was a significant number, you would likely be even more accurate.

You could increase that accuracy by asking every household what they estimate the witch population was. Further assumption would be that the witch population would likely rate the estimate higher than the non-witches would. Plot out the curve of responses and there would likely form a nice little bell curve. Take the peak (I’m not a stats guy, but I think that is called the mode or something like that) and give that as your estimate.

Even if it is completely inaccurate, but giving the mayor the best guess from the survey would likely appease him. Customers don’t want the right answer, they want what they already think the right answer is.

You said this was solvable, when are you going to post the solution?

One solution was already posted by Raymond Chen above.

My solution was different, but based on the same idea: you ask each person on the phone to throw a coin.

1) If the answer is Heads then you ask her to thrown the coin again, and say "yes" on heads or "no" otherwise.

2) If the answer is Tails on the first coin, then ask her to say "yes" if she is a witch, and "no" otherwise. She can be sincere here since under the assumption of the problem, her answer would not disclose her.

So, let’s assume that you get Y number of "yes" answers, and N number of "No" answers. From the total number T of people T=Y+N you had two categories: witches (W) and non-witches (Q). Obviously T=Y+N=W+Q.

Now, assuming an equal probability heads/tails distribution on the first coin, only half of N got in case (2). So, for the first case, half witches responded equally with "yes" and "no", and the other half say only "yes". Similarly, for the first case, half of the non-witches responded equally with "yes" and "no", and the other half with "no".

Therefore:

Y = W/4 + Q/4 + W/2

N = W/4 + Q/4 + Q/2

So, Y-N = (W-Q)/2. But we also know that W+Q=Y+N, so 2

W=2(Y-N)+(Y+N). In conclusion,W=(3*Y-N)/2

(or at least approximatively)

Adi, your answer is wrong for the reason given above too.

You want to estimate the total number of witches. What you propose will estimate the total number of witches among the subset of people who pick up the phone.

However, I am now wavering on whether you can assume distribution of witches to be independent of the family in which they live. After all, you have said that witches don’t know who other witches are.

So, if witchiness is randomly distributed throughout the town, you can simply ask an extra question "how many people are in your family". Then take your estimate, divide by the number of phone numbers and multiply by the total population to get an estimate of the total number of witches.

Well, I guess you alreayd know how many persons are living in that family. You could ask each one to come for the quick questionnaire to the phone…

Adi, I don’t fully agree with your answer. With your solution, saying "yes" to the "are you a witch" question means that there is a 75% likelihood that really you are a witch. If witches are not expected to give answers that incriminate themselves, then they will all answer "no". Your methodology should assume that all witches will answer "no" because it’s the answer most likely not to protect them.

Well, yes, there might be a 75% likelihood, but nobody will know for sure.

If there aredoubts, the experiment can be tweaked to decrease this probability to be close to 50%, and this might increase the "sincerity" level, even though it decreases your actual sample rate.

For example, you ask the witches to throw the coin two times in the first phase. If she gets heads on both throws, it will say the truth. If she gets tails on one of the throws, then it says "yes"/"no" depending on a third throw.

In that case, we have:

Y = 0.75

(W/2 + Q/2) + 0.25WN = 0.75

(W/2 + Q/2) + 0.25QAnd, therefore, if you say "yes", there is a 5/8*100 = 62.5 probability that you are a witch. But the real sample would be N * 0.25, so you have a higher margin of error.

Generally, if we go to N tests in the first phase, you will get a 100 * ((1 + 0.5^)(n+1)) likelihood to be a withc when you say "yes". This expression converges to 50% when N goes to infinity.

Sorry, the expression is 0.5 + (0.5)^(n+1). For one throw in the first phase: 75%, for two throws 62.5%, for three 56.25%, etc.

Even if every resident underwent your test and answered honestly according to the test, it is only theoreticaly accurate. You would have to modify the test slightly and re-run it a few different times to help verify any results you had.