PS - There's a completely different method to solve this problem that isn't anything like the solution that you two are moving towards.  It's less elegant, but is sometimes easier for certain types of people to imagine.

12-Ball Solution

1^st Weighting:  5 6 7 8  v  9 10 11 12

If Equal – you have two more weightings to solve for 1 2 3 4 (I.e – the 4 ball problem I described earlier).

Let’s assume they are unequal and we find that 5 6 7 8 is light OR 9 10 11 12 is heavy..

2^nd Weighting:  5 6 9 v 10 7 4

If Equal, then you know it’s either 8-light, 11-heavy, or 12-heavy. Weigh 11 v 12 to solve.

If 5 6 9 is heavy, then it’s either 9-heavy or 7-light.  Weigh one of them against 2 to solve.

If 5 6 9 is light, then it’s either 5-light, 6-light, or 10-heavy. Weigh 5 v 6 to solve.

 

M: OK, so "by reducing it to 4 balls with 2 weightings" actually meant "by assuming the first weighting has identified a set of 4 balls containing the outlier".  Got it.  That's the path my solution takes 1/3 of the time.

So are you actually claiming to be able to do that for all cases?    I don't see how it's possible.  Are you only talking about one of the two possible outcomes of your first weighting?

Edit: I see you were.  "Never mind".  Interesting solution - my second weighing when the first was unequal was quite different, but they both work.

k, think i'm on to something here. Breaking them into groups of three, I can with 2 weighings narrow it down to 3 unknowns (in the worst case - other cases leave it with 1 of 3 of a known oddity, which can be easily solved with one weighing). Unfortunately, in that worst case i need 2 weighings to determine which of the oddities it is, correct? damn, i don't know if that will work.

 

M: I see where you're coming from with the "4ball problem" - sorry it took me a bit to understand.
i also see how your unequal 1st weighing breaks down to a solution - tho there's got to be a less convoluted way.

BorisTheFrugal wrote: ...I HATED this problem when I was first presented with it....

Me too! I just couldn't let it go. Soo many scribbles on so many pieces of paper... pool balls, like M57 said, finally, quecards (which I could move around and write notes on)... that did the trick.

"I am tall when i'm young;

I am short when i'm old.

The zephyr is my greatest foe."

Hmmm...   Zephyr = West wind?  Or Blimp?

A candle?

SquintGnome wrote:

A candle?

Correct :)

"light as a feather,

yet no man can hold it for long"

BorisTheFrugal wrote:

PS - There's a completely different method to solve this problem that isn't anything like the solution that you two are moving towards.  It's less elegant, but is sometimes easier for certain types of people to imagine.

B, what is the other way?

Jigler wrote:

"light as a feather,

yet no man can hold it for long"

A breath.

ratsy wrote:

Jigler wrote:

"light as a feather,

yet no man can hold it for long"

A breath.

yup :)

M57 wrote:

B, what is the other way?

Warning: Spoiler alert

I like to think of this in terms of 3-digit numbers in base 2.
There are 27 combinations of 0's, 1's and 2's:
000, 001, 002, 010, 011, 012, 020, 021, 022,
100, 101, 102, 110, 111, 112, 120, 121, 122,
200, 201, 202, 210, 211, 212, 220, 221, 222

Choose 12 particular options of the above list.
(I'll explain how to choose the particular 12 later)
And then assign those particular 12 3-digit sets to the 12 balls.
Use the three digits in the combination to place the ball for each of the 3 weighings.
The 1st digit is the 1st weighing, the 2nd is the 2nd, and 3rd is the 3rd.
And the digit itself determines the location of the ball:
    A 0 in the digit = that ball is not on the scale
    A 1 in the digit = that ball is on the left
    A 2 in the digit = that ball is on the right

So now if we write down the results of the 3 weighings as to which one side of the scale is heavier, and we assume that the different ball is a heavier, then the results would match the 3-digit number chosen above.
If we write down the results the same way, but the different ball is lighter, then the results would be somewhat different:
The 0's wouldn't change (because the different ball isn't on the scale)
The 1's would become 2's, because the light ball on the left would make the right side higher.
The 2's would become 1's, because the opposite reason of the above
So the combination 112 would become 221, and the combination 201 would become 102.

So the rules we'd need to abide by when choosing the 12 combinations are:
1) We must have x4 0's, x4 1's, and x4 2's in each weighing, because we need to put the 4 balls in each of the 3 locations
2) We must remove the inverses (using the inversion rules for light vs heavy listed above).  If we don't then we can't tell whether (by example) the 112 is the heavy or the 221 is light.

An example list would be assigning balls 1-12 with the following combinations:
      Ball is Heavy    Ball is light
1    112                221
2    110                220
3    121                212
4    122                211
5    210                120
6    202                101
7    201                102
8    200                100
9    011                022
10  021                012
11  020                010
12  002                001

In this example, the weighings would be:
Weighing    Left            Right             Off
W1            1,2,3,4       5,6,7,8          9,10,11,12
W2            1,2,5,9       3,4,10,11      6,7,8,12
W3            3,7,9,10     1,4,6,12        2,5,8,11

Brilliant.

Break Billiard Balls Riddle:

You have 2 billiard balls, and a 100 story building.
You need to determine the highest floor floor of the building that you can drop one of the balls and it will survive.
If you drop a ball and it breaks, it cannot be used again.
If you drop a ball and it does not break, it can be used again with no loss of strength.
If you break both balls without determining the answer, you have not successfully completed your task.
What is the order of floors that you do test drops from to determine the answer in the LEAST number of test cases (and what is that number of tests)?

6oz of Water:

You have 2 glasses
Glass A is 9oz
Glass B is 4oz
You have an unlimited amount of water
You can fill or dump either glass
Each fill / dump / transfer of water counts as one step.

What is the fewest number of steps to measure out exactly 6oz of water, and how do you do it?

(one of my favorites from Car Talk, for any fans of the show)

BorisTheFrugal wrote:

Break Billiard Balls Riddle:

You have 2 billiard balls, and a 100 story building.
You need to determine the highest floor floor of the building that you can drop one of the balls and it will survive.
If you drop a ball and it breaks, it cannot be used again.
If you drop a ball and it does not break, it can be used again with no loss of strength.
If you break both balls without determining the answer, you have not successfully completed your task.
What is the order of floors that you do test drops from to determine the answer in the LEAST number of test cases (and what is that number of tests)?

Ok, here's my stab at this.

Initial (naive) thought:

Think like a HashMap (programer here ) and use the first ball to locate a set of ten floors, then use the other to locate the actual floor.  So:

1st ball - try floor 10, 20, 30, 40, 50, 60, 70, 80, 90, 100.

If it breaks on one of those, then use the 2nd ball to find the proper floor.  So just to illustrate, let's say it breaks on floor 40.  Then you take the 2nd ball and try 31, 32, 33, ..., 39 until it breaks - and you found it.  So worst case, the 1st ball breaks on floor 100, and the 2nd ball breaks on 99.  So that's 19 drops.

Better:

Ok, that was too simple - I bet we can do better. Thinking about it while typing the above, there's no reason to choose constant size 10 floor "buckets" for the 2nd ball to explore.  Let's say instead, each "bucket" of floors get's smaller to balance the drops of the two balls.  I tried a couple times, and came up with the following:

1st ball floors to try: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

Thus once the 1st ball breaks (assuming it does - worst case), then the bucket for the 2nd ball gets smaller relative to how many drops you made for the 1st ball.

So if the 1st ball breaks on floor 14, the 2nd ball tests 1-13 = 14 total drops  (1+13)

if it breaks on floor 27, the 2nd ball tests 15-26 = 14 drops (2+12)

... breaks on 39, 2nd ball tests 28-38 = 14 drops (3+11)

...

... breaks on 95, 2nd ball tests 91-94 = 14 drops (10+4)

... breaks on 99, 2nd ball tests 96-98 = 14 drops (11+3)

If the 1st balls survives to floor 100, then that's 12 drops.

 

So the best I can do is 14 drops using the above methodology.

BorisTheFrugal wrote:

6oz of Water:

You have 2 glasses
Glass A is 9oz
Glass B is 4oz
You have an unlimited amount of water
You can fill or dump either glass
Each fill / dump / transfer of water counts as one step.

What is the fewest number of steps to measure out exactly 6oz of water, and how do you do it?

(one of my favorites from Car Talk, for any fans of the show)

1) Fill Glass A

2) Pour Glass A to Glass B till Glass B full, leaving 5oz in A.

3) Dump Glass B

4) Pour Glass A to Glass B till Glass B full, leaving 1oz in A.

5) Dump Glass B

6) Pour the 1oz from Glass A to Glass B

7) Fill Glass A

8) Pour Glass A to Glass B till Glass B full, meaning we poured out 3oz - leaving 6oz in Glass A

 

So, 8 steps??  It seems I should be able to do better, but it's late and my head hurts after doing the ball drop one

Find the defective bottle riddle:

You have 5 bottles, each filled with pills.  4 of the bottles contain all normal pills, where each pill weighs 10 grams each.  The other bottle contains all defective pills, which weigh only 9 grams each (yes - these are monster pills!).  You have no idea which bottle contains the defective pills, you can't tell by looking at them, and you have a normal digital scale to tell you the weight, in grams, of the pills you place on it.  You can place as many pills on the scale, from any of the bottles, but you can make only a SINGLE weighing.

Locate the defective bottle of pills.  And do it by weighing the fewest number of pills possible (and how many is that?)