[bonanova]

You have five objects, A, B, C, D and E, no two of which have the same weight.

You have a balance scale but no weights.

What is the maximum number of weighings [comparing two objects] needed to order the objects by weight?

How many weighings are necessary for six objects?

[Guest]

You have five objects, A, B, C, D and E, no two of which have the same weight.

You have a balance scale but no weights.

What is the maximum number of weighings [comparing two objects] needed to order the objects by weight?

How many weighings are necessary for six objects?

Do you mean minimum number of weighings?

[Guest]

You have five objects, A, B, C, D and E, no two of which have the same weight.

You have a balance scale but no weights.

What is the maximum number of weighings [comparing two objects] needed to order the objects by weight?

How many weighings are necessary for six objects?

Assuming you meant minimum number of weighings that guarantee correct ordering in all cases

Assume that at each phase, weighings provide minimal information.

Adding additional objects to ordering:

To order 1 obect, 0 weighings.

To order 2 objects, new object can fit in 2 regions (weight less than existing object or more). This requires one weighing. 1 weighing so far.

To order 3 objects, there are 3 potential regions for new object: (lower than all, higher than all, between the other 2). At most, this takes 2 weighings. 3 weighings so far

To order 4 objects, 4 potential regions. If start by comparing a side object (lowest or highest, can take 3 weighings). If start by comparing central object, takes 2 weighings at most. 5 so far

To order 5, 5 regions. Choose one of central 2 objects to start. 3 weighings at most. 8 so far.

I calculate that, in general, for n > 0, the number of weighings is -1 + ceil(n/2)*(floor(n/2)+1)

So, for n = 5

-1 + 3*(2+1) = 8

for n=6

-1 + 3*(3+1) = 11

For 1000 objects,

-1 + 500*(500+1) = 250499

Edited October 19, 2010 by mmiguel1

[Guest]

Assuming you meant minimum number of weighings that guarantee correct ordering in all cases

Assume that at each phase, weighings provide minimal information.

Adding additional objects to ordering:

To order 1 obect, 0 weighings.

To order 2 objects, new object can fit in 2 regions (weight less than existing object or more). This requires one weighing. 1 weighing so far.

To order 3 objects, there are 3 potential regions for new object: (lower than all, higher than all, between the other 2). At most, this takes 2 weighings. 3 weighings so far

To order 4 objects, 4 potential regions. If start by comparing a side object (lowest or highest, can take 3 weighings). If start by comparing central object, takes 2 weighings at most. 5 so far

To order 5, 5 regions. Choose one of central 2 objects to start. 3 weighings at most. 8 so far.

I calculate that, in general, for n > 0, the number of weighings is -1 + ceil(n/2)*(floor(n/2)+1)

So, for n = 5

-1 + 3*(2+1) = 8

for n=6

-1 + 3*(3+1) = 11

For 1000 objects,

-1 + 500*(500+1) = 250499

use a heap sort or merge sort. NlogN algorithms are much better than that N^2 business

Edited October 19, 2010 by mmiguel1

[bonanova]

For example you could get lucky and weigh A vs B, B vs C, C vs D, D vs E and find them in ascending order, and you'd do it in four weighings.

But it might take more than four. So yes, the minimum number to insure a correct ordering.

I guess when I said maximum I was thinking "the most it might take."

in fewer than 8 weightings?

And six in fewer than 11?

I gets nontrivial rather quickly, so let's stop there.

I understand there is a formula that gives the correct answer for up to eleven objects but fails at twelve.

But five or six you can do by hand.

[EventHorizon]

is binary search for the spot of the new item, and keep adding in new items.

The formula that gives (where a_n is the number of weighings needed for n items) is:

a_n+1 = a_n + ceiling( log₂n )

Here's the number of weighing needed for the first couple:

1 - 0

2 - 1

3 - 3

4 - 5

5 - 8

6 - 11

7 - 14

8 - 17

Of course, from the description of the problem (not to mention who posted it), I think I can do better.

[EventHorizon]

I got 5 in 7, but the method is not simple.

I thought about what checks would decrease the search space by half. I start off with pairing them off with one extra.

Compare the first pair, and name the smaller one a and the bigger one b. Compare the next two and name the smaller one c and the bigger one d. Compare a and c. Now compare the last one (named e) to the larger of a and c.

The first three compares halve the search space, and the last with leave you with 7 or 8 possible orderings.

In every case, there are three more comparisons that halve the search space each time.

For the case of 6 objects. The first four checks (and namings/renames) are a<b, c<d, e<f, and a<c (if c<a, swap names for a and c and for b and d). This leaves 45 orderings. Assuming you can always essentially halve the remaining ones, it will take 6 more comparisons (since 2^6 = 64 > 45). This would be 10 total for ordering all 6 objects.

Surely it isn't as simple as log₂N! as N keeps growing. Would there always be a way to halve the search space? Perhaps I'll write some code later to check larger numbers.