OFFSET
0,4
COMMENTS
Calculated from Andrzej Pelc's complete solution for 1-liar games which gives the minimum number of questions required for a given set {1,...,k}.
Andrzej Pelc's formula for the minimum number of questions required for a given set {1,...,k} is: the least value of q such that f(q)>=k, where f(q)=2^q/(q+1) for even k, and f(q)=(2^q-q+1)/(q+1) for odd k. We use this to generate the sequence of maximum set sizes for each value of q.
LINKS
D. Osthus and R. Watkinson, A simple solution to Ulam's liar game with one lie, Elemente der Mathematik 63 (2008), 97-101.
A. Pelc, Solution of Ulam’s Problem on searching with a lie, J. Combinatorial Theory, Series A, vol. 44 (1987), 129-140.
EXAMPLE
a(1) = 1 since 1 question is (vacuously) sufficient to determine x in {1}; a(2) = 1, since 2 questions (with one possible lie) is no better than 1; a(3) >= 2, since we can determine x in {1,2} by asking "Is x in {1}?" three times and majority voting. But a(3) is not >2 because we need 5 questions for {1,2,3}; which implies a(4) = 2 also.
MAPLE
LiarSequence:=proc(n)
local q, L, k;
q:=1: L:=NULL;
for k from 1 to n do
while 2^q/(q+1)-(k+1 mod 2)*(q-1)/(q+1)<k+1 do q:=q+1; L:=L, k end:
end: L end:
CROSSREFS
KEYWORD
nonn
AUTHOR
Robin W. Whitty, Jun 15 2017
EXTENSIONS
a(0) and a(29)-a(37) from Pontus von Brömssen, Jan 30 2024
STATUS
approved