Ponder This Challenge - November 2014 - Distribution using two coins

Ponder This Challenge:

There are 24 letters in the Greek alphabet, from alpha, beta, and gamma, through chi, psi, and omega. The names of the letters are of different lengths, from short two-letter names like mu or pi through the seven letters in omicron.

We want to generate a random Greek letter, where the probability of a letter is determined by the length of its name, and the following:

Psi is a special case with a probability of zero (we are actually generating one of 23 letters)

Letters whose names are composed of an even number of letters have a probability of 2^length times the probability of the letter Tau

All the other letters (except Psi and Tau) have a probability of 2^(length-2) times the probability of Tau

So, for example, the letter mu (with a length of two letters) should appear 2^2 = 4 times more than tau. Omicron (with a length of seven letters) should appear 2^(7-2), or 32 times more often than tau.

The task is to generate the random Greek letter using six coin tosses, in which the coins are chosen from two types: one with a probability of p_1 of getting a tails and 1-p_1 of getting heads; and the other with a probability of p_2 for tails and 1-p_2 for heads.

You should give p_1, p_2, and the tosses in the following format:

For example, the following solution (the parenthesis were added just for clarity):

p_1 = 1/2

p_2 = 1/4

1 (2 alpha (1 beta gamma)) beta

We toss the first coin p_1

     If it's tails, we toss the second coin

         If it's tails

             We generate alpha

         Otherwise

             We toss p_1 and

                 If it's tails

                     We chose beta

                 Otherwise

                     We chose gamma

     Otherwise

         We chose beta

Using the schema above yields:

Alpha: 1/8

Beta: 11/16 (= 3/16 + 1/2)

Gamma: 3/16

Credit for the source of this problem will be provided in the solution.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  A simple way to solve this month's challenge is by p1=1/17 and p2=1/2. However, this solution requires seven coin tosses, and we asked for six.

  The solution we meant, and which many of you found, is p1=8/17 and p2=1/3.

  Tossing p1 twice, we split the probability to 64/289, 72/289, 72/289, 81/289 and using up to four more coin tosses we get the desired distribution.

  See Oleg Vlasii's picture (PNG, 11KB) of the binary tree to solve it.

  1

       (1 lambda

           (2  (2 alpha beta)   (2 zeta epsilon)))

       (1  (2  (2 gamma omicron)   (2 omicron upsilon))

           (2  (2  (2  (2 tau eta)   (2 rho mu))

                     (2  (2 phi nu)   (2 xi delta)))

               (2  (2  (2 chi theta)   (2 theta kappa))

                    (2  (2 pi sigma)   (2 omega iota)))))

           1 (1 lambda

               (2  (2 alpha beta)   (2 zeta epsilon)))

               (1  (2  (2 gamma omicron)   (2 omicron upsilon))

                    (2  (2  (2  (2 tau eta)   (2 rho mu))

                               (2  (2 phi nu)   (2 xi delta)))

                         (2  (2  (chi theta)   (theta kappa))

                               (2  (2 pi sigma)   (2 omega iota)))))

  Another solution uses p1=46/289 p2=1/3.

  Philip Kinlen sent us another visualization http://abitofmaths.blogspot.hk/2014_12_01_archive.html

  This month's problem was inspired by UYHIP's October's challenge: http://www.brand.site.co.il/riddles/201410q.html

Solvers

• Oleg Vlasii (10/31/2014 10:53 PM EDT)
• Yanwu He (11/01/2014 07:55 AM EDT)
• Martin Thiim (11/01/2014 01:40 PM EDT)
• Sergey Grishaev (11/01/2014 08:09 PM EDT)
• Gregory Giecold (11/02/2014 02:13 AM EDT)
• Motty Porat (11/02/2014 10:57 AM EDT)
• Jochen Voß (11/02/2014 06:51 PM EDT)
• Adam Daire (11/02/2014 09:04 PM EDT)
• Ehud Schreiber (11/02/2014 10:00 PM EDT)
• William Heller (11/03/2014 01:01 AM EDT)
• Atul Kumar (11/03/2014 10:29 PM EDT)
• Deron Stewart (11/04/2014 06:58 AM EDT)
• David Brink (11/04/2014 03:55 PM EDT)
• Erik Hostens (11/04/2014 05:31 PM EDT)
• Zhuo Wang (11/04/2014 07:20 PM EDT)
• Joseph DeVincentis (11/04/2014 07:27 PM EDT)
• Dieter Beckerle (11/04/2014 09:00 PM EDT)
• Ziqi Zhu (11/05/2014 02:57 AM EDT)
• Harald Bögeholz (11/05/2014 01:08 PM EDT)
• Liubing Yu (11/05/2014 05:31 PM EDT)
• Bryce Herdt (11/05/2014 10:13 PM EDT)
• Aviv Nisgav (11/06/2014 08:33 AM EDT)
• Thomas Slothouber (11/07/2014 12:55 AM EDT)
• Don Dodson & David Dodson (11/07/2014 01:07 AM EDT)
• Yasodhar Patnaik (11/08/2014 05:23 PM EDT)
• Chris Shannon (11/09/2014 02:31 AM EDT)
• Govind A. N. (11/09/2014 03:11 AM EDT)
• Antoine Comeau (11/09/2014 04:59 AM EDT)
• Dan Dima (11/09/2014 04:45 PM EDT)
• Andreas Stiller (11/09/2014 08:46 PM EDT)
• Peter Gerritson (11/10/2014 01:46 PM EDT)
• Tatiana Stepanova & Svyatoslav Savenko (11/10/2014 07:04 PM EDT)
• David Friedman (11/10/2014 09:15 PM EDT)
• Chuck Carroll (11/11/2014 08:24 AM EDT)
• Adrian Orzepowski (11/11/2014 09:34 AM EDT)
• Cynthia Beauchemin (11/12/2014 06:08 AM EDT)
• Graham Hemsley (11/12/2014 08:22 AM EDT)
• Piotr Nadczuk (11/12/2014 11:33 AM EDT)
• Arthur Breitman (11/12/2014 02:22 PM EDT)
• Hendrik Nigul (11/12/2014 05:12 PM EDT)
• John Tromp (11/12/2014 11:33 PM EDT)
• Pen-Li (Ben) Yu (11/13/2014 03:07 AM EDT)
• Gilles-Philippe Paillé (11/14/2014 02:07 PM EDT)
• Addison Fischer (11/14/2014 04:14 PM EDT)
• Jan Fricke (11/15/2014 11:45 AM EDT)
• William F. Darnieder (11/15/2014 12:25 PM EDT)
• Daniel Bitin (11/17/2014 02:22 PM EDT)
• Bart De Vylder (11/17/2014 07:15 PM EDT)
• Jan Rubak (11/17/2014 08:18 PM EDT)
• Stéphane Higueret (11/18/2014 11:25 AM EDT)
• David Greer (11/18/2014 04:05 PM EDT)
• Tobias Zurell (11/20/2014 06:42 AM EDT)
• Shirish Chinchalkar (11/22/2014 08:26 AM EDT)
• Uoti Urpala (11/22/2014 11:15 PM EDT)
• Hyun Jae Moon (11/23/2014 03:36 AM EDT)
• Kyoung A. Lee (11/23/2014 06:10 PM EDT)
• James Ha (11/23/2014 07:53 PM EDT)
• Daniel Hahn (11/23/2014 09:15 PM EDT)
• Rachit Srivastava (11/24/2014 05:25 PM EDT)
• Michael Rosola (11/26/2014 01:56 PM EDT)
• Rogerio Ponce da Silva (11/26/2014 05:30 PM EDT)
• Jeffrey Boyle (11/28/2014 03:42 PM EDT)
• Siyeon Kim (11/28/2014 06:13 PM EDT)
• Joël Bleuse (11/28/2014 07:56 PM EDT)
• Yujin Kim (11/29/2014 12:24 AM EDT)
• June Kang (11/29/2014 01:09 AM EDT)
• Huikang Yi (11/29/2014 02:40 AM EDT)
• David Yang (11/29/2014 02:14 PM EDT)
• Peter Shim (11/29/2014 05:59 PM EDT)
• Igor Karp (11/30/2014 12:00 AM EDT)
• Radu-Alexandru Todor (11/30/2014 05:30 PM EDT)
• Heidi Kim (11/30/2014 07:28 PM EDT)
• Robin Park (11/30/2014 05:00 PM EDT)
• Kwonil Kobe Ko (11/30/2014 07:00 AM EDT)