Danny Pflughoeft - cp's OEIS frontend

User: Danny Pflughoeft

Danny Pflughoeft has authored 1 sequences.

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

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

User: Danny Pflughoeft

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python