login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A328950 Numerators for the "Minimum-Redundancy 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 21 23:00 EST 2020. Contains 332113 sequences. (Running on oeis4.)