Vol. 13: Puzzle This

MAKE's favorite puzzles; including dates, palindromes, orbs, and poison pills!

By Michael H. Pryor

Illustrations by Roy Doty

Digital Edition

SUBSCRIBERS:

Read this article now in your digital edition!

Get Make:

Subscribe to MAKE and get the best rate!

+ Downloads & Extras:

Answers

� MAKE: NOISE — Discuss this article

You must be logged in to post a talkback.
[ Display main threads only] [ Newest First]

Showing messages 1 through 18 of 18.

14?!?
You must be logged in to reply.

My officemate and I spent about 20 or 30 minutes on this and confidently declared the answer to be 19. (We also noted that it could be 18 if it could be guaranteed that SOME floor would break the orb.)

Then I saw the 14, gasped and closed the window.

We reworked our solution and got the same thing you did. However our previous confidence made us question how it could be *proven* that this is a minimum. You've got a demonstration, but that's hardly a proof.

(We did at least establish, with a lot of handwaving, that 14 was the minimum for this scheme type.)
Posted by drysdam on February 25, 2008 at 09:58:38 Pacific Time

Radar Date - wrong wrong wrong
You must be logged in to reply.

9/09/1909 not a palindrome?
Posted by jaa_baba on February 25, 2008 at 20:05:49 Pacific Time

Radar Date - wrong wrong wrong
You must be logged in to reply.

Hmmm... Since you padded the day with a zero, why wouldn't you pad the month?

9/09/1909 would be 9/9/1909 or 09/09/1909 if you were consistent, so no, I don't consider that to be a valid palindrome.
Posted by MichaelPryor on February 25, 2008 at 20:58:15 Pacific Time

pills
You must be logged in to reply.

you can also split the pills into two piles of 6. Take the lighter pile after the first weighing, and split into two piles of 3. Weigh them, and keep the remaining pile of 3. Pick any two pills from the pile of 3. If they weigh the same, the remaining pill is the safe one. If they don't weigh the same, eat the lighter one. This is the same binary search that you're using, but is a little easier to follow than the initial split into three piles.
Posted by thowland on February 25, 2008 at 20:23:44 Pacific Time

pills
You must be logged in to reply.

It was stated in the puzzle that the assassin does NOT know the weight of the non-poisionous pill. It could be heavier [or] lighter. Since this fact was not known, a binary search does not work. In using that approach, the assassin would have 25% chance of surviving!
Posted by bwstellar on February 26, 2008 at 19:54:25 Pacific Time

pills
You must be logged in to reply.

In the given situation there is always a possibility that the assassin will have to choose between 2 pills and he will not know which one is the poisonous pill. However the solution I present minimizes the likelihood that the situation will come to that. So here goes...

Firstly the assassin should ask the queen for her mercy and request that he have a glass of water to take whichever pill he chooses. If the queen really does have the hots for the assassin this shouldn't be too hard to get.

The assassin now must narrow down the 12 pills. To do this initially he should divide the pills into two groups of 6. setting aside one group. He must then subdivided the second group into two groups of three and place each group of three on opposite sides of the scale. If the two groups of three are equivalent in weight then it can be determined that the non-poisonous pill is not among the weighed (6) pills and must be a member of the group of pills that were initially set aside. If the weight is not equal among the two groups of 3 then the non-poisonous pill must be among the group of 6 pills that were weighed.

Now that we have eliminated 6/12 pills as being poisonous and we know that all the poison pills are the same weight, we can now determine whether the non-poisonous pill is heavier or lighter than the poisonous pills while further reducing the number of unknowns. To do this we divide the unknown group of 6 pills into a group of 4 and 2. Weighing the unknown group of 4 pills against 4 poisonous pills that we eliminated earlier will clarify one of two possibilities:
1) If the scale is balanced then the non-poison pill is not among the 4 weighed unknown pills and must be among the final two pills (in which case the non-poisonous pill can be determined by weighing one of the 2 pills against a known poison pill).
or
2) If the scale is unbalanced, then the non-poison pill is among the group of 4 and not the group of 2. Also by the direction of the unbalanced scale it can be determined whether the non-poison pill is heavier or lighter than the poison pills (if unknowns are heavier than the non-poison pill is heavier and vice versa). In this case there is still work to do to further eliminate poisonous pills.

We are left with 4 pills 3 of which are poisonous. We know whether or not the non-poison pill is heavier or lighter than the poisonous ones. For simplicity sake I'll assume the non-poisonous pill is heavier than the poisonous ones (since this will work either way). We are now left with one measurement and 4 unknowns. If we take 3 of the unknown pills and divide them into groups of 2 and 1. We then weigh the group of 2 unknowns against the one unknown plus one of the known poison pills. If the scales are weighing towards the side with the one unknown and the poison pill then the unknown pill must be the non-poisonous pill. If the scales are balanced then the unknown pill that we did not weigh in this measurement is safe one to ingest. However if the scales tip to the side of the 2 unknown pills then we can conclude two things.

1) We're the most unlucky assassin ever.
and
2) We have a 50% chance of living.

Here's where my solution gets a bit creative. Looking at the scale that's used in this conundrum, it appears that minuscule weight differences would not obviously register and thus the weight difference between the poison/non-poison pills will be relatively significant. The problem stated that you can only make three weighings. If we are faced with the situation where it is 50/50 between two pills and we cannot physically hold the two options and tell a difference then we drop them both in the glass water and see which ones falls fastest.

Failing that as an assassin I would hope to ingest the poison pill so I no longer have to play messenger boy between disgruntled lovers.

Cheers,
Posted by felgindy on March 09, 2008 at 12:59:35 Pacific Time

Radar Date - wrong revised
You must be logged in to reply.

OK, then::

12/9/1921

Not only does it treat zero's consistently, it's later than my last attempt.
Posted by jaa_baba on February 26, 2008 at 08:08:51 Pacific Time

Radar Date - wrong revised
You must be logged in to reply.

That's definitely a good answer!
Posted by MichaelPryor on February 26, 2008 at 08:10:03 Pacific Time

Radar Date - wrong revised
You must be logged in to reply.

Using the same format, 29/9/1992 is also possible.
Posted by JermsG on May 15, 2008 at 22:10:40 Pacific Time

Crystal Orbs
You must be logged in to reply.

To prove that 14 is the minimum, work by recursion. For o orbs, and d drops, let F(o,d) be the maximum number of floors that can be distinguished. If you drop an orb at a certain floor and it breaks, you know the correct floor (first one at which the orb breaks) is there or lower, and you have one fewer orb and one fewer drop to continue with. If it doesn't, you know the correct floor is higher and you have the original number of orbs but one fewer drop. If you plan correctly the two new searches (whose lengths we assume we already know - that's the recursion) do not overlap or have a gap between them. Thus:

F(o,d) = F(o-1,d-1) + F(o,d-1)

To start the recursion, note that with no drops we can distinguish between one state.

We can now work out the terms of this recursion in a table:

o d0 1 2 3 4 5 6 7<br/>

0 1 1 1 1 1 1 1 1

1 1 2 3 4 5 6 7 8

2 1 2 4 7 11 16 22 29

3 1 2 4 8 15 26 42 64

4 1 2 4 8 16 31 57 99

5 1 2 4 8 16 32 63 120

(etc). Note that with unlimited orbs you
can distinguish 2^d floors.

To get a formula for this you can use generating functions (or other combinatorial methods) and conclude that in the n^th row, the entry is the sum of the first n terms in row d of Pascal's triangle (with the left-hand "1" indexed by 0 in the traditional fashion.) Thus in particular the 2-orb row has entries

1 + n + n(n-1)/2 = (n^{2 + n +2)/2

and the three-orb row has entries

1 + n + n(n-1)/2 + n(n-1)(n-2)/6}
Posted by Robert Dawson on March 05, 2008 at 05:49:11 Pacific Time

Crystal Orbs -Correction
You must be logged in to reply.

Sorry, messy markup. Let me try again with the table and formula.
```
  o 0   1   2   3   4   5   6   7 

d_|______________________________

0 | 1   1   1   1   1   1   1   1

1 | 1   2   3   4   5   6   7   8 

2 | 1   2   4   7   11  16  22  29

3 | 1   2   4   8   15  26  42  64

4 | 1   2   4   8   16  31  57  99

5 | 1   2   4   8   16  32  63  120
```
(etc). Note that with unlimited orbs you
can distinguish 2^d floors.

To get a formula for this you can use generating functions (or other combinatorial methods) and conclude that in the n^th row, the entry is the sum of the first n terms in row d of Pascal's triangle (with the left-hand "1" indexed by 0 in the traditional fashion.) Thus in particular the 2-orb row has entries

1 + n + n(n-1)/2 = (n² + n +2)/2

and the three-orb row has entries

1 + n + n(n-1)/2 + n(n-1)(n-2)/6

Posted by Robert Dawson on March 05, 2008 at 05:56:24 Pacific Time

Poison Pills
You must be logged in to reply.

Number the pills 1 through 12.

First, weigh 5,6,7 and 8 on the left against 9,10,11 and 12 on the right.

If the left side is heavier, record the number "+9"; if the right side is heavier record the number "-9". If they balance, record "0"

Second, weigh 2,3,4 and 11 on the left against 5,6,7 and 12 on the right.

If the left side is heavier, record the number "+3"; if the right side is heavier, record the number "-3". If they balance, record "0".

Third, weigh 1,4,7 and 11 on the left side against 2,5,8 and 10 on the right side.

If the left side is heavier, record the number ""+1"; if the right side is heavier, record the number "-1". If they balance, record "0".

That completes the three allowed weighings.

Now, add the three numbers you have recorded. The sum will represent the number of the odd pill, with the sign indicating whether it is heavy ("+") or light ("-"). However, if the final sum is 9, 10, 11 or 12, reverse the sign for the final result.

Posted by davidhy on March 15, 2008 at 17:08:27 Pacific Time

Poison Pills
You must be logged in to reply.

Very elegant.

My solution was similar, but lacked the mathematical derivation of the answer. Instead, I constructed a table.

Create three sets of piles for each weighing.

The left-most piles are placed on the balance. The rightmost is left on the table.

Keep track of the position of the LEFT tray.

1,6,3,4 -- 5,11,7,8 -- 9,10,2,12
1,12,11,10 -- 2,3,4,5 -- 6,7,8,9
11,9,8,3 -- 7,1,10,2 -- 12,4,5,6

Now, here is the table for the solution. Keep in mind, the 'u'p and 'd'own reference the left tray. '-' means balanced.

ddu or uud = 1
-uu or -dd = 2
dud or udu = 3
du- or ud- = 4
uu- or dd- = 5
d-- or u-- = 6
u-u or d-d = 7
u-d or d-u = 8
--d or --u = 9
-du or -ud = 10
udd or duu = 11
-d- or -u- = 12

Posted by Lurquer on March 26, 2008 at 16:51:36 Pacific Time

Poison Pills
You must be logged in to reply.

All the solutions look so complicated too me, but not necessary. You don't need to indentify the poison pill, just isolate it into a pile. (and eat from another )

Divide the 12 into 3 groups of 4. Put 2 groups on the scale.

If they balance, the poison pill is in the unused pile, eat any on the scale.

If they don't, remove the heavier pile, place the new one on the scale. If the new pile is also the heaviest, the lighter pile contains a lighter poison pill.

If they balance, the heavier poison pill is in the first pile removed.

If the new pile weighed is lighter then someone lied to you and more than one pill different.
Posted by idearat on May 19, 2008 at 17:19:55 Pacific Time

crystal orbs
You must be logged in to reply.

Dont get it -what if the first floor it breaks on is the 3rd. How would you determine that starting on 14?
Posted by ubay on April 09, 2008 at 15:06:38 Pacific Time

crystal orbs
You must be logged in to reply.

First you would drop one on 14 and it would break. The previous floor you tested was floor 0 (since you hadn't tested any). So next you would start dropping the other unbroken one on 1, it wouldn't break, move up to 2, it wouldn't break, move up to 3 and it breaks. You now now the first floor it breaks on.
Posted by MichaelPryor on April 10, 2008 at 09:32:35 Pacific Time

Poison Pills
You must be logged in to reply.

All the solutions look so complicated too me, but not necessary. You don't need to indentify the poison pill, just isolate it into a pile. (and eat from another )

Divide the 12 into 3 groups of 4. Put 2 groups on the scale.

If they balance, the poison pill is in the unused pile, eat any on the scale.

If they don't, remove the heavier pile, place the new one on the scale. If the new pile is also the heaviest, the lighter pile contains a lighter poison pill.

If they balance, the heavier poison pill is in the first pile removed.

If the new pile weighed is lighter then someone lied to you and more than one pill different.
Posted by idearat on May 19, 2008 at 17:21:25 Pacific Time

Poison Pills
You must be logged in to reply.

This doesn't work because ALL of the pills are poisonous EXCEPT for one.
Posted by zigness on November 17, 2008 at 09:23:44 Pacific Time

Showing messages 1 through 18 of 18.

Join the conversation -- every MAKE article has an online page that includes a place for discussion. We've made these RSS and Atom feeds to help you watch the discussions: subscribe.