OFFSET
1,2
COMMENTS
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
REFERENCES
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".
LINKS
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.
EXAMPLE
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.
PROG
(Python)
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
CROSSREFS
KEYWORD
nonn,frac
AUTHOR
Danny Pflughoeft, Nov 10 2019
STATUS
approved