Using a balance scale the minimum number of times, find the median weight person

Question

There are 15 person with different weights.

What is the least number of tries required to find the middle (median) weight person? How?

The only tools you have is your brain and a balance scale with no limitation on area or weight. (you can put as many people you like on each side of the balance scale).

Answer 1

Here's 31 weighings. I'll only use one-vs-one weighings.

One can sort 5 elements in 7 comparisons. Split the people into 3 groups of 5 and sort each one (21 weighings). Sort the three medians of the three groups by comparing each pair (3 weighings). Call these groups the light, medium, and heavy group by their sorting.

Now, note that the median of the light group has at least eight people heavier than them: the two heavier people in their group, and the three median-and-above people in each of the other two groups. That means they are below median, as are the two below-median people in the light group. Likewise, we know three above-median people.

We can therefore eliminate these six people from considering, and find the median of the nine remaining people, which are sorted into a group of five and two-groups of two.

Note that we can merge two sorted groups of size $a$ and $b$ using $a+b-1$ weighings by comparing the two heaviest people in each group, removing the heavier one as the maximum, and repeating. So, one can merge the two sorted lists of two into a sorted list of four in 3 weighings.

At this point, we've used 27 weighings, and could spend 8 weighing to merge the two groups of 4 and 5 and have the nine sorted, for a total of 35.

But, that's overkill because we just need the median of the nine. Compare the median of the group of 5 and the median of the group of 4, rounding down for the four (1 weighing). Whichever way the result is, the two heavier people of the median-heavier group are above median, and likewise for the lighter people. Eliminating these, we're left with two sorted people and three sorted people.

Again, we could merge-sort in 4 weighings, but we instead do it in 3. Compare the median of the three to each of the two (2 weighings). If the results are opposite, the median of the three is the median, and we're done. Otherwise, say WLOG both are lighter. Compare the heavier of the two to the lightest of the three (1weighing). If he's lighter, the lighter of three is the median. Otherwise, he's the median, as we know two people lighter than him and two people heavier.

That's a total of 31 = 21 + 3 + 3 + 4 weighings.

[A computer search by Kenneth Oksanen found that the optimal number of comparisons (one-vs-one weighings) is between 24 and 28 inclusive, though an exact answer is not known.]

Answer 2

Seeing as we have no information about the people's weights other than that they are all different, I don't think it will ever be useful to weigh more than two people at a time. Since we're only making one on one comparisons, I expect that standard sorting algorithms would be the way to do it the fastest.

Let's look at mergesort:

Group the people into groups of 4 and one group of 3. Then for each group of 4 do the following, calling the people A, B, C, and D:

• Weigh A against B and C against D (2 weighings)
  • WLOG let A and C be the lighter ones
• Weigh A against C
  • WLOG let A be lighter. We now know who the lightest of the four is (A)
• Weigh B against C
  • If B is lighter, we know A < B < C < D in 4 weighings
  • If C is lighter, we need to weigh B against D to know A < C < B < D or A < C < D < B

So in a max of 5 weighings, we can sort each of the groups of 4. For the group of three

• Weigh A against B, then B against C
  • If A < B < C or A > B > C, we're done.
• Weigh A against C

So in a max of 3 weighings we can sort the group of 3. Now we have 4 groups where we know the order of their weights. Weighings so far - up to 18. Now we need to merge pairs of groups:

• While either group still has at least one person, weigh the two lightest remaining people against each other
  • The lighter of the two is removed from their group

The order in which the people are removed from their groups is their order in the merged group. This can take up to 7 weighings for merging the groups of 4 and 6 for merging a group of 4 and the group of 3. Total weighings so far - up to 31.

Now we can merge the two remaining groups to find the median-weighted person. We do the same thing as we did before, but this time after we have removed 8 people from their groups, we know who the median-weighted person is.

Worst case scenario - we have to do 39 weighings.

Answer 3

I believe that a "single-elimination tournament" strategy gets us down to $35$ weighings.

(Step 1) Run a balanced four-round single-elimination tournament to find the lightest person. Eliminate them. We've used 14 weighings so far. We're going to repeat this 7 more times, each time using partial information from the previous rounds.

(Step 2) Due to the structure of the tournament, the lightest person "won" against (at most) 4 other people. One of these four other people is the lightest person among those remaining. Also, these four other people have won (at most) 0, 1, 2, and 3 matches respectively. Play 0 against 1, then play the winner against 2, then play the winner of that against 3. The final winner is the next lightest person; eliminate them.

(Step 3) The final winner in Step 2 has now won at most four matches. I believe that by enumerating cases, one can show that the losers of these matches have won at most 3, 2, 1, and 0 matches themselves. Assuming I enumerated the cases properly, one can then repeat Step 2 until eight people are eliminated. The eighth person to be eliminated is the one of median weight.

All in all, this procedure takes 14 weighings to initialize, and then 3 weighings for each of the next 7 steps. So 35 in all.

Answer 4

Pick a person. Weight that person against all other 14. This splits the world into 3 sections:

• The heavier (x)
• That person
• The lighter (y)

Take the group that must include the middle weight, repeat.

Best case scenario, 14 weighings, x == y at first attempt.

Worst case scenario, picking successively heaviest and lightest persons, 14+13+12+11...+1 = 105.

(This is a partial quicksort with the worst choice of pivot.)

Alternative solution (selection sort):

Eliminate the heaviest at each round, 8 rounds needed, 14+13+12+...7 = 84

Third solution:

Insertion sort with only 8 spots (last is the middle person) and binary search for inserting. 8 first insertions require at worst 17 weighings, 7 lasts at worst 28. Total is 45. (best case is 34).

Answer 5

This doesn't take advantage of the possibility of weighing multiple people against each other at the same time, but a variation of the Quicksort algorithm, but only sorting half of the partitions, could work. Purely using quicksort to completely sort the 15 people would take on average $15 log_2 15 = 58.6$ comparisons.

Eyeball the people and pick someone who looks like they might be the middle weight person to use as the first pivot. Compare the other 14 people against him and sort them into lighter and heavier groups. If the groups are the same size, you're done! Else, you'll need to repeat the process with the larger remaining group, since that group must contain the middle weight person. So the best case scenario is 14 comparisons. In the worst case you alternately pick the lightest and heaviest people and have to make 105 comparisons. For the average case, I'd surmise that since you are effectively sorting half of the people, it would take $8 log_2 8 = 24$ comparisons.

Answer 6

It's a pretty poor answer, but in the worst case scenario I have $63$ tries.

Pick a person. Weigh them against others until you get 8 greater or 8 lesser. Now, imagine that as you are comparing them against your picked person, you're filling a series of 15 slots, and each lighter person takes the left-most spot, and the heavier person takes the right-most spot.

As soon as someone sits in the middle spot, that person and their group (heavier or lighter) go back into the pool, the picked person takes the next spot for the other group, and every spot taken is locked. Repeat.

In the worst case scenario, the first 7 people you pick are all on the light side. That's 56 tries. Then it'll take you another 7 to find the lightest of the remainder.

Answer 7

You can weigh 2 and find the difference of the 1 vs 1 sides, and then use that towards the next one when you continue to weigh against him with more people, continue this process until you can compare them all to the 1 person, successfully determining their "weight".

You have now compared 14 people and determined their weight in comparison to the one's unknown weight.

Next, we can calculate this one whom we compared to by using the 2 people who weighed closest (the one closest yet greater, and the one closest yet lighter) to effectively rate their weight.

This gives us a mere

14 weighs