IBM Research | Ponder This | November 2014 challenges

# Ponder This

## November 2014

<<October November December>>

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:
<Coin>=1 or 2
<Greek letter>=alpha or beta or gamma or delta or epsilon or zeta or eta or theta or iota or kappa or lambda or mu or nu or xi or omicron or pi or rho or sigma or tau or upsilon or phi or chi or omega
<solution>= <Greek letter> or <coin> <solution> <solution>

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

Challenge: 10/31/2014 @ 12:00 PM EST
Solution: 12/01/2014 @ 12:00 PM EST
List Updated: 10/31/2014 @ 12:00 PM EST

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)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.