Selections and weighings

[Guest]

You have 81 black balls and 19 white balls, of identical shape, weight, and feel, in a barrel. You select balls blindfolded.

How many balls must you select to be assured of selecting a black ball?

20 balls. Your first 19 might all be white.

How many must you select to be assured of getting a white ball?

82 balls, in case the first 81 are all black.

How many must you select to be assured of getting all the black balls?

100. You can't know if the balls you haven't yet selected are black, so you have to take them all.

Now that you have all 81 black balls, you are told that they are not truly identical, but that one is slightly heavier than the others. You are given a set of balance scales and instructed to find the heavy ball. What is the minimum number of weighings in which you can guarantee to find the heavy ball?

Four. Divide into groups of 27 and weigh (1). Take the heavy group, or the unweighed group if the weighed groups are equal. Divide the heavy group into three groups of 9 and repeat the weighing (2). Again, divide the heavy group into three groups of 3 and repeat weighing (3). Take two balls from the heavy group of 3 and weigh against each other (4). The heavier ball is the heavy ball, or if they weigh the same, the unweighed ball is the heavy ball.

Using the above method, what is the *minimum* number of weighings in which you could actually find the heavy ball?

Four. The heavy ball is identified only in the fourth weighing.

Eighteen of the nineteen white balls are identical. The nineteenth is of a slightly different weight, but you don't know if it's heavier or lighter (and can't tell by feel). Using the balance scales, what is your weighing strategy for finding the odd ball and what is the minimum number of weighings to guarantee finding it? Assume that the eighteen balls are lettered from A to R so that you can tell them apart. (I don't have the optimal solution to this, since I just made it up and it's not obvious to me, but I'll think about it while reading other's responses.)

[Guest]

EDIT: I just saw that I violated my own conditions...oops. I solved the problem for eighteen balls instead of nineteen! Well, here is my "solution" anyway, for whatever it's worth. The real solution will be similar, I think.

******************

What a ripoff! I just wrote up a solution for the last problem that identified the odd ball in three or four weighings, but I wasn't allowed to post it, and now it's lost! Let me try to reproduce it.

Divide the 18 balls into three groups of six.

Weighing 1: Weigh one of these groups against another.

IF WEIGHING 1 BALANCES

Weighing 2a: The odd ball is in the unweighed group of six. Weigh three of these against three known good balls.

* IF WEIGHING 2a BALANCES

Weighing 3a-1: One of the remaining three unweighed balls is the odd ball. Weigh any two of them against two known good balls.

** IF WEIGHING 3a-1 BALANCES

Weighing 4a-1a: The remaining unweighed ball is the odd ball. Weigh it against another ball to determine if it's light or heavy.

SOLUTION: 4 WEIGHINGS

** IF WEIGHING 3a-1 DOES NOT BALANCE

Weighing 4a-1b: One of the two from the Weighing 3a-1 is the odd ball, and you know if it's light or heavy. Simply weigh one of them against the other or against a known good ball to determine which is the odd ball.

SOLUTION: 4 WEIGHINGS

* IF WEIGHING 2a DOES NOT BALANCE

Weighing 3a-2: One of the three from the Weighing 2a is the odd ball, and you know if it's light or heavy. Weigh one of them against another of them to determine which is light/heavy. If they balance, the remaining one is the odd ball.

SOLUTION: 3 WEIGHINGS

IF WEIGHING 1 DOES NOT BALANCE

Weighing 2b: Take 3 from the light group and 3 from the heavy group and weigh them against the unweighed 6 balls, which you know to be good.

+ IF WEIGHING 2b BALANCES

Weighing 3b-1: The odd ball is in the remaining 3 light or 3 heavy balls. Weigh 2 heavy balls and a light ball against 3 known good balls. If they weigh light, the light ball is the odd ball.

SOLUTION: 3 WEIGHINGS

++ IF WEIGHING 3b-1 BALANCES

Weighing 4b-1a: In this case, either the last remaining heavy ball is heavy or one of the two light balls is light. Weigh the heavy ball and a light ball against two known good. If they weigh heavy, the heavy ball is the odd ball. If they weigh light, the light ball is the odd ball. If they balance, the remaining light ball is the odd ball.

SOLUTION: 4 WEIGHINGS

++ IF WEIGHING 3b-1 DOES NOT BALANCE

Weighing 4b-1b: If 3b-1 weighed light, we already determined that the light ball was the odd ball. If it weighs heavy, then one of the two heavy balls is the odd ball. Weigh one of them against the other or against a known good ball to determine which is the odd ball.

SOLUTION: 4 WEIGHINGS

+ IF WEIGHING 2b DOES NOT BALANCE

Weighing 3b-2: If Weighing 2b weighs heavy, one of the three heavy balls is heavy; otherwise, one of the three light balls is light. From this group of three, weigh any two against each other. If they balance, the unweighed third ball is the odd ball. If they do not balance, the heavier (if Weighing 2b weighed heavy) or lighter (if Weighing 2b weighed light) ball is the odd ball.

SOLUTION: 3 WEIGHINGS

Can anyone do better than this?

*******************

EDIT: Maybe this will do it.

In Weighing 3a-1, consider the unweighed balls as a group of four, and weigh three of them against three good. If they balance, the remaining ball is the odd ball and can be identified as light or heavy in the fourth weighing. If the group of three weighs light or heavy, then you know the odd ball is either light or heavy, and by weighing one of the three against another in the fourth weighing, you can immediately identify the odd ball.

[bonanova]

20, 82, 100, 4.

There are exactly 81 possibilities.

Each weighing has 3 distinguishable outcomes.

Four weighings can distinguish among 3x3x3x3 = 81 possibilities.

Devise a 1st weighing that reduces the number of possibilities to 27 -> 27 against 27; with the 27 suspect balls,

Devise a 2nd weighing that reduces the number of possibilities to 9 -> 9 against 9; with the 9 suspect balls,

Devise a 3rd weighing that reduces the number of possibilities to 3 -> 3 against 3; with the 3 suspect balls

The 4th weighing is 1 against 1; it determines the heavy ball.

Four is the fewest weighings, using this method.

4.

Three weighings can distinguish among no more than 3x3x3=27 possbilities.

With 19 balls that could be heavy or light you have 19x2=38 possibilities.

Three weighings won't do it.

Use the above method.