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

%I

%S 0,3,9,19,33,51,74,102,135,173,216,264,318,378,444,516,594,678,768,

%T 864,966,1074,1188,1308,1435,1569,1710,1858,2013,2175,2344,2520,2703,

%U 2893,3090,3294,3505,3723,3948,4180,4419,4665,4918,5178,5445,5719,6000,6288,6584,6888,7200,7520,7848

%N Numerators for the "Minimum-Redundancy Code" card problem.

%C 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).

%C The problem can be solved using Huffman codes.

%C 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".

%D 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"

%H D. A. Huffman, <a href="https://www.ic.tu-berlin.de/fileadmin/fg121/Source-Coding_WS12/selected-readings/10_04051119.pdf">A Method for the Construction of Minimum-Redundancy Codes</a>, in Proceedings of the IRE, vol. 40, no. 9, pp. 1098-1101, Sept. 1952.

%e For n=2, there are 3 cards, so a(2)/3 = 3/3 = 1 question is needed on average.

%e For n=3, there are 6 cards, so a(3)/6 = 9/6 = 1.5 questions are needed on average.

%Y Cf. A286496.

%K nonn,frac

%O 1,2

%A _Danny Pflughoeft_, Nov 10 2019

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 March 28 15:12 EDT 2020. Contains 333089 sequences. (Running on oeis4.)