OFFSET
0,3
COMMENTS
Original name: "A thinks of x in set M; B asks questions: is x in T?; A may lie once but only when true answer is Yes; a(n) is maximal size of M such that B can determine x with <= n questions."
It is sufficient to consider only subsets T of M; any elements of T that are not in M (which is known to both players) are irrelevant. The nature of the elements of M does not matter, for simplicity one can assume that M = {1, ..., m}, given that the set M must be finite in any case.
LINKS
Erdal Arikan and Serdar Boztaş, Guessing with lies, Proc. IEEE Int'l Symposium on Information Theory, Lausanne, Switzerland, 2002, pp. 208
Andrzej Pelc, Solution of Ulam's problem on searching with a lie, J. Combin. Theory Ser. A, 44 (1987), pp. 129-140.
Andrzej Pelc, Searching games with errors—fifty years of coping with liars, Theoretical Computer Science 270 (1-2), 2002, pp. 71-109.
Wikipedia, Ulam's game.
FORMULA
a(n+1) = 2*a(n) - b(n) with b = o(a), b(n) > 0 for all n >= 0 except for b(1) = b(3) = 0; b(n+1) = 2*b(n) - c(n) with c = o(b) (conjectured). - M. F. Hasler, Jun 26 2026
EXAMPLE
No question is needed to know the chosen element x of a singleton set {x}, but if there are more elements, one cannot know, so a(0) = 1 is the maximum size of a set where the answer can be known with 0 questions.
With one single question, the maximum size is the same, a(1) = 1: if there are more elements, one cannot know x from one single answer which may be a lie.
With two questions one can determine the chosen x in a two-element set M = {a, b}: Pick a singleton T = {a}; if the answer is yes you know x = a, if the answer is no, ask again and you can know whether x = a or x = b. It is easily seen that one cannot determine the chosen x of a 3-element set M = {a, b, c}, in general. (The first answer may be "No" in which case it is useless because it can be a lie.)
To illustrate a(3) = 3, consider M = {a, b, c} and the following table of optimal questions and possible outcomes:
Q1: A1, Q2 : A2, Q3: A3 -> Final Deduction:
-----------------------------------------------------
{a}: Y - - - - - - - - - -> x = a, no lies used
" : N, {a,b}: Y, {a}: Y -> x = a, 1 lie used on Q1
" : N -> x = b, no lies used
" : N, {b}, Y -> x = b, 1 lie used on Q2
" , N -> x = c, no lies used.
Here, a double quote " means "the same as above up to here".
An illustration for a(n = 4) = 6 is as follows:
Q1 : A1, Q2 : A2, Q3 : A3, Q4: A4 -> Final Deduction
-------------------------------------------------------------------
{a,b,c}: Y, {a} : Y - - - - - - - -> x=a, no lies used
" : N, {a,b}: Y, {a}: Y -> x=a, 1 lie used on Q2
" : N -> x=b, no lies used
" : N, {b}: Y -> x=b, 1 lie used on Q3
" : N -> x=c, no lies used
" : N, {a,b,c,d}: Y, {a,b}: Y, {a}: Y -> x=a, 1 lie used on Q1
" : N -> x=b, 1 lie used on Q1
" : N, {c}: Y -> x=c, 1 lie used on Q1
" : N -> x=d, no lies used
" : N, {d,e}: Y, {d}: Y -> x=d, 1 lie used on Q2
" : N -> x=e, no lies used
" : N, {e}: Y -> x=e, 1 lie used on Q3
" : N -> x=f, no lies used.
Here we have 2^4 - 3 = 13 lines corresponding to a final "leaf" in the tree, which isn't a complete binary tree, because receiving "Y-Y" on Q1 & Q2 ends the game with only 1 conclusion instead of 4 leaves that would have the complete binary tree with 2 more questions after A1 = A2 = Y. This is similar to the n = 3 question tree having only 2^8 - 3 = 5 final nodes. A rigorous proof that these sets of questions are optimal and the sizes are maximal would be significantly longer.
PROG
(Python)
def A010033(n): # takes ~ 2^k min for a(29+k)
if not hasattr(A:=A010033, 'W'): A.W=[1, 0]; A.seq=[1]
while len(A.seq) <= n: # extend the sequence
W = A.W; new_W = []; x = 0; start_k = 0 # Monotonicity tracking
while True:
max_y = -1; best_k = start_k
for k in range(max(x-len(W)+1, start_k), min(x+1, len(W))):
if k <= W[x-k]:
val = W[k] + W[x - k] - k
if val < max_y: break # Dropped below peak: stop searching
max_y = val; best_k = k
if max_y == -1: break # No valid state found: done for this n
new_W.append(max_y); start_k = best_k; x += 1
A.seq.append(x - 1) ; A.W = new_W
return A.seq[n] # M. F. Hasler, Jun 25 2026
CROSSREFS
KEYWORD
nonn,more,changed
AUTHOR
Thorsten Prenzel (prenzel(AT)unitas.or.uni-bonn.de)
EXTENSIONS
Edited and a(0) = 1 prefixed by M. F. Hasler, Jun 24 2026
a(28)-a(31) from M. F. Hasler, Jun 25 2026
a(24) corrected and a(32)-a(34) from Sean A. Irvine, Jul 07 2026
STATUS
approved