Intereting Posts

Solving a polynomial in an easier manner
Nash Equilibria for zero-sum games (Rock Paper Scissors)
The big O notation
Isomorphism between complex numbers minus zero and unit circle
Suppose that $f$ is analytic on a close curve γ. Prove or disprove $\int_\gamma \overline{f(z)}f'(z)dz$ is purely imagine.
Choosing an advanced group theory text: concerns
How to prove that $\lim_{n \to \infty} n x^{n} = 0 $ when $0<x<1$?
What is the space curve with curvature and torsion obeying
Prove if $n^2$ is even, then $n$ is even.
Is this vector-valued map Hölder-continuous?
Let $f (z) $ be an entire function such that $|f (z)|≤K|z|$, $∀z∈\mathbb{C}$, for some $K>0$. If $f (1) =i$, then$f (i) $ is
Is $\mathbb{Z}_p\otimes_{\mathbb{Z}} \mathbb{Z}_q$ noetherian?
Are there any positive integers $a, b, c, d$ such that both $(a, b, c)$ and $(b, c, d)$ are Pythagorean triples?
Holomorphic Function in Disk and its Maximal
Sum of $\lfloor k^{1/3} \rfloor$

A person is thinking of a number between 1 and 1000. What is the least number of yes/no questions that we can ask and know what that person’s number is given that the person is allowed to lie on at most one of her answers.

- 9 pirates have to divide 1000 coins…
- Is this urn puzzle solvable?
- 100 prisoners and a lightbulb
- Which simple puzzles have fooled professional mathematicians?
- Game: two pots with coins
- Tall fraction puzzle
- Rainbow Hats Puzzle
- Can the product $AB$ be computed using only $+, -,$ and reciprocal operators?
- Maximize :: $A = B \times C$
- Puzzle on the triangle.

This is known as Ulam’s problem of searching with lies. For one lie it was first solved by Andrzej Pelc. The minimum number of questions is not hard to calculate but the strategy attaining this number in the worst case takes several pages to describe. Later the solution was simplified.

For $n$ objects with $1$ lie, $n$ even, the number $q$ of questions needed is the smallest solution to $\frac{2^q}{q+1} \geq n$ which is $14$ when $n=1000$. There is a non-adaptive solution using Hamming codes that uses at most one more question than Pelc’s method, but can specify all the questions before gameplay begins.

For distinguishing from $n$ options we need $\lceil \log_2 n \rceil$ bits of information. However, when we allow some bit to be faulty, we get $nk$ possibilities where $k$ is the number of asked questions. Optimally we would have to use at least logarithm of it, so

$$k = \log_2 (n k)$$

which with $n = 1000$ could be solved numerically, with appropriate ceils we get $k = 14$. This is the lower bound, that is, in the worst case we can’t get the answer with smaller number of questions (there might be, of course, better lower bounds). To get the upper bound you can apply the coding theory, some sample approaches include “repeat every question 2 times”, which will get you something like $2\lceil\log_2 n\rceil+1$ questions ($21$ for $n = 1000$), or search for the faulty place with binary search, arriving at about $\lceil\log_2 n\rceil +\big\lceil\log_2\lceil\log_2 n\rceil\big\rceil+1$ questions ($15$ for $n = 1000$).

I hope this helps 😉

**Edit:** Hamming(15,11) code corrects 1 error and achieves even better bound: you would be able to distinguish $2^{11} = 2048$ possibilities. Of course, it also applies in your case.

Here is a quick proof that it cannot be done in $13$ questions. Suppose there was a strategy that could do this; we may safely assume that $13$ questions are asked in all cases (just fill up with dummy questions if you happen to know the answer earlier). Then after $13$ questions, one will have found out both the number the person was thinking of, *and* the number of the answer that was a lie (taking $0$ if there was no lie). But the person may start with deciding both on the number and the number of the question that she will lie to. That gives $1000\times14>2^{13}=8192$ possibilities, too much to sort out using $13$ yes/no answers.

By this argument it still remains possible that $14$ questions will do, as $15000<2^{14}=16384$.

- Building a hidden markov model with an absorbing state.
- Subgroups of finite nonabelian simple groups
- Understanding the Definition of a Differential Form of Degree $k$
- Reference request: Nonlinear dynamics graduate reference
- What does it mean for a matrix to be orthogonally diagonalizable?
- Zero-dimensional ideals in polynomial rings
- Conditions under which the Limit for “Measure $\to 0$” is $0$
- If $X$ is a connected subset of a connected space $M$ then the complement of a component of $M \setminus X$ is connected
- How can I visualize division of negative numbers
- Can every element in the stalk be represented by a section in the top space?
- Proving a reduction formula for the antiderivative of $\cos^n(x)$
- Find the limit without use of L'Hôpital or Taylor series: $\lim \limits_{x\rightarrow 0} \left(\frac{1}{x^2}-\frac{1}{\sin^2 x}\right)$
- Can you recommend some books on elliptic function?
- How to prove that if each element of group is inverse to itself then group commutative?
- Limit of ${x^{x^x}}$ as $x\to 0^+$