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,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".

References

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

Links

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

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.

Crossrefs

Cf. A286496.

Sequence in context: A226184 A066506 A058331 * A049749 A147055 A146638

Adjacent sequences: A328947 A328948 A328949 * A328951 A328952 A328953

Keyword

nonn,frac

Author

Danny Pflughoeft, Nov 10 2019

Status

approved