XRDS

Crossroads The ACM Magazine for Students

Sign In

Association for Computing Machinery

XRDS: Bemusement Solutions

WINTER/DECEMBER 2011

Daughters, Ages

Two MIT math grads bump into each other at Fairway on the Upper West Side in New York City. They haven't seen each other in more than 20 years.
THE FIRST GRAD SAYS TO THE SECOND:
"How have you been?"
SECOND: "Great! I got married and I have three daughters now"
FIRST: "Really? How old are they?"
SECOND: "Well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there."
FIRST: "Right, OK...oh wait...hmm, I still don't know."
SECOND: "Oh sorry, the oldest one just started to play the piano."
FIRST: "Wonderful! My oldest is the same age!"


Solution:

There are 3 daughters whose ages multiply to 72. Let’s look at the possibilities…

 AGES:  SUM OF AGES: 
 1 1 72  74
 1 2 36  39
 1 3 24  28
 1 4 18  23
 1 6 12  19
 1 8 9  18
 2 2 18  22
 2 3 12  17
 2 4 9  15
 2 6 6  14
 3 3 8  14
 3 4 6  13

After looking at the building number the man still can’t figure out what their ages are (we’re assuming since he’s an MIT math grad, he can factor 72 and add up the sums), so the building number must be 14, since that is the only sum that has more than one possibility. 

Finally the man discovers that there is an oldest daughter. That rules out the “2 6 6” possibility since the two oldest would be twins. Therefore, the daughters ages must be “3 3 8”. 

(Caveat: An astute reader pointed out that it IS possible for two siblings to have the same age but not be twins, for instance one is born in January, and the next is conceived right away and delivered in October. Next October both siblings will be one year old.)

(Source: techInterview)


FALL/SEPTEMBER 2011

The Composite Game

You're playing a game with a friend. She names any positive integer she likes, and you win if you can find that many consecutive composite (i.e., non-prime) numbers. If she says "three," you can win by saying "8, 9, and 10," for example. Can you find a strategy to win this game 100% of the time?


Solution:

We can reformulate the problem like this: prove constructively that for all integers n >= 1, there exists an integer q such that all integers in the interval [q, q+n-1] are composite. Given an arbitrary n >= 1, we'd like to construct a satisfactory q. The key to the problem is to use the factorial operation, since it results in numbers that have lots of consecutive factors — but the devil is in the details. q = n! does not work, for example, because it's not clear that n!+1 (the second value in the interval [q, q+n-1]) is composite. q = n!+2 seems promising, because now q is divisible by 2, q+1 = n! + 3 is divisible by 3, and so on. However, the end of the interval doesn't work out so nicely: q+n-1 = n!+n+1 is not necessarily composite. However, q = (n+1)!+2 does the trick. Observe that when q = (n+1)!+2, the interval [q,q+n-1] = (n+1)!+2, (n+1)!+3, … , (n+1)!+n+1. The first value is divisible by 2, the second by 3, and so on, all the way up until the last value, which is divisible by n+1. You win!

This problem establishes an interesting property about the primes: there are arbitrarily large gaps between consecutive prime numbers. In other words, there is no guaranteed way to find a new prime by starting at a known one and then searching within some bounded range.

SUMMER/JUNE 2011

The Poisoned Wine 

You have 240 barrels of wine, one of which has been poisoned. After drinking any small amount of the poisoned wine, one dies within 24 hours. You have five slaves whom you are willing to sacrifice in order to determine which barrel contains the poisoned wine. How do you achieve this in 48 hours?

Solution:

First consider doing two "rounds" of drinking, since it will take up to 24 hours for the poison to take effect, and we have 48 hours to solve the problem.

Now, it's best to consider the problem from the perspective of information theory. Each slave can exhibit one of three outcomes: they can survive, they can die after the first round, or they can die after the second round. Let's call these outcomes "0", "1", and "2", respectively. How many different outcomes can be realized across all five slaves? 3^5 = 243. In other words, there are 243 different 5-digit base-3 numbers. Five slaves and 48 hours allow us to encode 240 distinguishable scenarios (with a few to spare), so the problem is definitely solvable.

Number the barrels using 5-digit base-3 numbers, and let each slave correspond to one of the digit positions. Now we have encoded how that barrel should be drunk. For example, a barrel numbered "00212" should be drunk in round two by slaves 3 and 5 (if they're alive of course), and in round one by slave 4. Slaves 1 and 2 should not drink it at all.

Now let the slaves do their drinking and construct the number corresponding to the outcome observed. For example if slaves 1 and 3 die in round one and nobody dies in round two, then barrel 10100 is the poisoned one.

Find the solution at http://geeksforgeeks.org/forum/topic/finding-the-poisoned-wine/

SPRING/FEBRUARY 2011

The Magic Money Machine

The wizards at Wall Street are up to it again. The Silverbags investment bank has invented the following machine. The machine consists of 6 boxes numbered 1 to 6. When you first get the machine, it contains 6 tokens, one in each box. You have two buttons A, B on the machine and you can press them as many times as you like and in any order.
Button A Choose a number i from 1 to 5 and then take one token from box i and magically two tokens will be added to box i + 1.
Button B Choose a number i from 1 to 4 and then take one token from box i and then the contents of boxes i + 1 and i + 2 will be interchanged.
The machine sells for one trillion dollars. The contract says that you can take the machine back to the bank at any time and then the bank will give you one dollar for each token in the machine. Is the machine worth buying?

Solution:

Let’s denote the state of the machine with a string of six non-negative numbers, denoting the token count of the respective boxes. The initial state is <1, 1, 1, 1, 1, 1>.
First, note that in a state with <n, 0, 1> as a substring, we can reach a state where that same substring becomes <0, 5*2n-2, 0>. To see this, observe the following series of moves:
<n, 0, 1> press button A to obtain:
<n-1, 2, 1> press A twice to obtain:
<n-1, 0, 5> press B to obtain:
<n-1, 5, 0> press A five times to obtain:
<n-1, 0, 10> press B to obtain:
<n-2, 10, 0> press A ten times to obtain:
<n-2, 0, 20> press B:
<n-3, 20, 0> press A twenty times:
<n-3, 0, 40> press B:
<n-4, 40, 0> etc.
Call this sequence of moves Foo. Now consider the following operation of the machine:
<1, 1, 1, 1, 1, 1>! ! press A:
<0, 3, 1, 1, 1, 1>! ! press A:
<0, 2, 3, 1, 1, 1>! ! press A three times:
<0, 2, 0, 7, 1, 1>! ! press B:
<0, 1, 7, 0, 1, 1>! ! press A seven times:
<0, 1, 0, 14, 1, 1>! ! press B:
<0, 0, 14, 0, 1, 1>! ! do Foo:
<0, 0, 0, 20480, 0, 1>! do Foo:
<0, 0, 0, 0, 5*220478, 0>
5*220478 is greater than a trillion. Congratulations, Mr. or Ms. Moneybags!
Original problem statement and solution available at http://www.cs.cmu.edu/puzzle/puzzle32.html