Ponder This — November’s Challenge!

SP-ponderthisSeems some of us can’t see a problem without wanting to take a crack at solving it. Does that sound like you? Good. Forge ahead and ponder this month’s problem

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
=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.


Ponder This is IBM Research’s monthly brain-twister where you can match wits with some of the best minds at IBM. IBM Research will post the names of those who submit a correct, original solution to their website! Send your submission to the webmaster.

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

Comments

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s