IBM Ponder This #199 · November 2014

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.

Solution

Best opened after a real attempt

To be added.