11
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ By "least number of tries", are you looking for the best worst-case scenario? $\endgroup$ – Rob Watts Jan 15 '15 at 20:41
  • $\begingroup$ Fact: with $n$ people, you can find the median in $O(n)$ comparisons. This is a puzzle in itself. (IMO a more interesting one for abstract technical people like me; though not one I would post to this site.) $\endgroup$ – Lopsy Jan 15 '15 at 21:06
  • 2
    $\begingroup$ funny thing: no one seems to be willing to weight more than 2 persons at once. I don't have a solution that would put several persons on each side of the scale. I wonder if there is a proof that it would be useless. $\endgroup$ – njzk2 Jan 15 '15 at 21:21
  • 1
    $\begingroup$ Intuitively, since median is an order-ranking thing, it doesn't seem sensible that comparing multiple people's weights added together would be any use. $\endgroup$ – smci Jan 15 '15 at 22:48
  • $\begingroup$ @njzk2 it might be worth asking that as a separate question $\endgroup$ – Rob Watts Jan 16 '15 at 1:53
8
$\begingroup$

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 bottom group has eight people has eight people heavier them them: the two heavier people in their group, and the three median-and-above people in each pf the other two groups. The 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 three (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.]

$\endgroup$
  • $\begingroup$ The best solution so far $\endgroup$ – Rafe Jan 16 '15 at 6:09
  • $\begingroup$ ISTR you can find the median of 5 in 6 comparisons. I'm not sure whether or not that partitions the other elements around the median, but if it does then I think it'll work instead of sorting, won't it? $\endgroup$ – Steve Jessop Jan 16 '15 at 11:40
  • $\begingroup$ @SteveJessop It might be doable, but I'm not sure it saves weighings. As I'm doing it, the middle list of five needs to be sorted, and merging the two lists of twos uses the fact that the groups of five they were in were sorted. $\endgroup$ – xnor Jan 19 '15 at 10:00
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Selection sort may be improved considerably if one sets up rounds as tournament brackets, and only invites into each round those people who might be the heaviest (or lightest). The first round requires 14 comparisons, but the second would only require three (to find the heaviest among the four people who had been compared their weight to the heaviest). Subsequent rounds would require various numbers of weighings, depending upon who was heaviest in the second round. $\endgroup$ – supercat Jan 15 '15 at 22:38
  • $\begingroup$ @supercat: such as what Lopsy answered? Yes, it is a pretty good improvement. $\endgroup$ – njzk2 Jan 16 '15 at 14:02
  • 1
    $\begingroup$ Yeah, I noticed his answer after I wrote my comment; some time ago (I don't remember exactly how far back, but when my PC had 64Megs of RAM) I wrote a program to implement what I called "tournament sort". The number of comparisons ended up being less than quicksort, but the bookkeeping overhead was much higher. Like other forms of selection sort, it had the advantage of making early items available first. $\endgroup$ – supercat Jan 16 '15 at 16:32
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I made 14... ${}$ $\endgroup$ – warspyking Jan 15 '15 at 20:30
  • $\begingroup$ I like the Quicksort idea. But in this case, we're finding a pivot, rather than sorting. $\endgroup$ – Chris Cudmore Jan 16 '15 at 18:45
0
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Fixed huge mess up in first paragraph. $\endgroup$ – warspyking Jan 15 '15 at 20:29
  • $\begingroup$ What does find the difference of the 1 vs 1 sides mean? $\endgroup$ – Golden Dragon Jan 15 '15 at 20:32
  • 2
    $\begingroup$ We only have a balance scale - this doesn't give you any indication as to how much heavier or lighter people are compared to each other. $\endgroup$ – Rob Watts Jan 15 '15 at 20:32
  • 1
    $\begingroup$ Next, we can calculate this one whom we compared to by using the 2 people who weighed closest how do you propose to do that? $\endgroup$ – njzk2 Jan 15 '15 at 20:38
  • $\begingroup$ Like everyone is pointing out, you don't know who weighed closer - balance scale only gives a "lighter/heavier" indication. $\endgroup$ – smci Jan 15 '15 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.