CareerCup

Are we looking for a heavy weight or light weight ball? I am assuming light weight here.

Minimum number of times to find the ball that is not equal weight is 2

Make two groups of 3 balls and one group of 2 balls

For e.g.
Group 1 and Group 2 has 3 balls
Group 3 has 2 balls

a) Weigh Group 1 and Group 2
b) If Weight (Group1) == Weight(Group2) then Group3 has the light weight ball
b1) Weight balls in Group3 to find the light weight ball
c) Else either Group1 or Group2 has the light weight ball
c1) Choose two balls from light weight group and weigh again
c11) If Weight(ball1) == Weight(ball2) then left out ball (Ball3) is the light weight ball
c12) Else either ball1 or ball2 is the light weight ball

So, the minimum number of times to use a scale is 2 times - using three-group technique.

So I though about this for a while, and here's what I ended up with.

First, observe that since we have a balance that allows us to compare two sets of balls then there are 3 possible outcomes:
1. The left side of the balance is heavier
2. The right side of the balance is heavier
3. The two sides are equal in weight

Now, we can think about the implications of each of the 3 outcomes.
1. The heavier ball is on the left side.
2. The heavier ball is on the right side.
3. The heavier ball is not on either side i.e. is in the set of balls not involved in the measurement

One of these 3 must occur and in all 3 cases we can eliminate the possibility that the ball is in the other 2 groups. So every time we take a measurement, we can remove 2 of the 3 groups that we separated the balls into. Now, if we assume that we divide the balls into equal groups each time, then we see that since we are left with 1/3 of the balls after each measurement, then the number of measurements necessary to reduce it to 1 ball would be ceiling(log_3(n)) where n is the original number of balls.

Now, we can consider the case where we can have groupings of different sizes, as we must if the number of balls isn't divisible by 3. In order for the conditions above to hold, the two groups on the scale must have the same number of balls; otherwise the conclusions are invalid. So, we have the condition that at least 2 of the 3 groups must have an equal number of balls. Since at each measurement its possible that we end up with the largest group, then the necessary number of further measurements at each step is log_3(max(n_i)) where n_i is the list of the number of balls in each group at step i. Thus, we see that its in our best interest to keep max(n_i) low at each point which means picking numbers as close to equal as possible. Obviously the closest we can come to equal is split exactly in thirds, so we see that if we follow the optimal strategy for each value of n we have the following relation:

num_measurements = ceiling(log_3(n))

0-3 => 1 measurements
4-9 => 2 measurements
10-27 => 3 measurements
....

This is our answer for the worst case number of measurements for each given number of balls.

I believe the problem is missing one important factor. The order in which the "odd" ball is picked...

If first or second, weight two balls. If 3rd-8th, weight 6 balls initially. Hence, it depends on chance of having odd ball in hand

Also, if the odd ball is one of the first four balls, two attempts is very likely

The two problems with knowledge of whether the different ball is heavier or lighter and without aforementioned knowledge are completely different. If it is known that the different ball is lighter (or heavier), the answer is obviously 2 turns of weighing.

Assuming that the different ball is lighter:

1) Start by picking 6 balls at random and place 3 on either side of a scale
2) If the the first weighing is equal, it will take only 1 weighing to determine which of the remaining 2 balls is different (k
3) If the first weighing is unequal, and we know that the ball is lighter, so we pick 2 balls at random from the lighter side.
4) If the second weighing from the pile of 3 balls is equal, then the left out ball is lighter.
Or else, the lighter ball is found from the weighing.

If, on the other hand, it is unknown that the different ball is heavier or lighter, it will take 3 tries to figure out the different ball.