A286496 -id:A286496 - cp's OEIS frontend

A325908 The largest k such that an integer x between 1 and k (inclusive) can be guessed in at most n queries "is x < y?" with one lie.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 7, 12, 22, 40, 76, 142, 268, 500, 944, 1788, 3389, 6444, 12286, 23464

Offset: 0

Mikhail Tikhomirov, Sep 08 2019

S. M. Ulam, "Adventures of a Mathematician", Scribner’s, 1976.

A. Pelc, Solution of Ulam’s Problem on searching with a lie, J. Combinatorial Theory, Series A, vol. 44 (1987), 129-140.

Cf. A286496 (with queries about membership of an arbitrary set instead of a set {x < y}).

A328950 Numerators for the "Minimum-Redundancy Code" card problem.

Original entry on oeis.org

0, 3, 9, 19, 33, 51, 74, 102, 135, 173, 216, 264, 318, 378, 444, 516, 594, 678, 768, 864, 966, 1074, 1188, 1308, 1435, 1569, 1710, 1858, 2013, 2175, 2344, 2520, 2703, 2893, 3090, 3294, 3505, 3723, 3948, 4180, 4419, 4665, 4918, 5178, 5445, 5719, 6000, 6288, 6584, 6888, 7200, 7520, 7848

Offset: 1

Danny Pflughoeft, Nov 10 2019

Given a deck of cards consisting of one 1, two 2's, three 3's, ..., n n's, what's the best average number of yes-or-no questions needed to ask to determine a randomly drawn card?  The answer is the above sequence divided by the number of cards (A000217).
The problem can be solved using Huffman codes.
This problem was popularized in Martin Gardner's Scientific American "Mathematical Games" column, and was included in his book "My Best Mathematical and Logic Puzzles".
Also a(n) is the merge cost in the optimal file merge pattern algorithm applied to the list comprising 1 to n. - Darío Clavijo, Aug 21 2024

			For n=2, there are 3 cards, so a(2)/3 = 3/3 = 1 question is needed on average.
For n=3, there are 6 cards, so a(3)/6 = 9/6 = 1.5 questions are needed on average.

Martin Gardner, My best mathematical and logic puzzles. New York: Dover Publications Inc., 1995, p. 29, puzzle #52 "Playing Twenty Questions when Probability Values Are Known".

geeksforgeeks.org, Optimal merge patterns.
D. A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, in Proceedings of the IRE, vol. 40, no. 9, pp. 1098-1101, Sept. 1952.

Cf. A286496.

def Ofmp(f):
    c = 0
    while len(f) > 1:
        f.sort()
        m = f[0] + f[1]
        c += m
        f[0] = m
        f.pop(1)
    return c
a = lambda n: Ofmp(list(range(1, n+1)))
print([a(n) for n in range(1, 49)]) # Darío Clavijo, Aug 21 2024

cp's OEIS Frontend

A325908 The largest k such that an integer x between 1 and k (inclusive) can be guessed in at most n queries "is x < y?" with one lie.

Views

Author

Keywords

References

Links

Crossrefs

A328950 Numerators for the "Minimum-Redundancy Code" card problem.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python