

A328950


Numerators for the "MinimumRedundancy Code" card problem.


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 yesorno 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 MinimumRedundancy Codes, in Proceedings of the IRE, vol. 40, no. 9, pp. 10981101, 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



