login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A286496 Renyi-Ulam liar numbers: for k=1,2,3,... this is the maximum n such that k questions "Is x in subset S of {1,...,n}?" are guaranteed to determine x when at most one answer can be a lie. 2
1, 1, 2, 2, 4, 8, 16, 28, 50, 92, 170, 314, 584, 1092, 2048, 3854, 7280, 13796, 26214, 49932, 95324, 182360, 349524, 671088, 1290554, 2485512, 4793490, 9256394 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

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,...,n}.

Andrzej Pelc's formula for the minimum number of questions required for a given set {1,...,n} is: the least value of q such that f(q)>=n, where f(q)=2^q/(q+1) for even n, and f(q)=(2^q-q+1)/(q+1) for odd n. We use this to generate the sequence of maximum set sizes for each value of q.

LINKS

Table of n, a(n) for n=1..28.

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

Sequence in context: A112433 A171648 A189914 * A318187 A217931 A090129

Adjacent sequences:  A286493 A286494 A286495 * A286497 A286498 A286499

KEYWORD

nonn

AUTHOR

Robin W. Whitty, Jun 15 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 9 04:05 EDT 2020. Contains 333343 sequences. (Running on oeis4.)