Election

Following on some talk about the electoral college:

Say you have a set S of n elements, s(1)...s(n). There is some total ordering relation ~ defined on S, such that for any i,j between 1 and n you can always determine whether s(i)~s(j). By comparing elements of S two at a time, what is the minimum number of comparisons needed to arrange S in order according to ~?

In other words, say you're voting for candidates for a political office, chosen from n candidates. For any two candidates, you can definitely say I prefer A to B, but you can only look at candidates two at a time, and your preferences must be consistent (as per the total ordering), i.e. you can't say I prefer Alfred to Beatrice and I prefer Beatrice to Clarence and I prefer Clarence to Alfred. How many comparisons are necessary to put the n candidates in order of preference?

(n-1) + (n-2) + ... + 2 + 1

There is a method of choosing pairs such that the total is smaller.

hmm, yes - I can see now that it is possible to order 4 elements with only 5 pairings...

have you already solved this?

Kind of. I think. I think I might have an approximate estimate fro how many are needed (i.e. I know the rate of growth, I think).

All right, I have a fast method, and I know about how many comparisons it takes given some n. I have a hunch that on average it is optimal. Can you tell me what it is?

Originally posted by royalchicken
All right, I have a fast method, and I know about how many comparisons it takes given some n. I have a hunch that on average it is optimal. Can you tell me what it is?

does it involve grouping the elements into 3's?

In some cases some groups will have three elements, but grouping them in threes is not an essential feature of this. Grouping them is, though.