# Election

royalchicken
Posers and Puzzles 01 May '03 21:17
1. royalchicken
CHAOS GHOST!!!
01 May '03 21:17
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?
2. richjohnson
TANSTAAFL
01 May '03 21:35
(n-1) + (n-2) + ... + 2 + 1
3. royalchicken
CHAOS GHOST!!!
01 May '03 21:58
There is a method of choosing pairs such that the total is smaller.
4. richjohnson
TANSTAAFL
01 May '03 23:45
hmm, yes - I can see now that it is possible to order 4 elements with only 5 pairings...

5. royalchicken
CHAOS GHOST!!!
02 May '03 00:05
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).
6. royalchicken
CHAOS GHOST!!!
02 May '03 19:14
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?
7. richjohnson
TANSTAAFL
02 May '03 19:57
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?
8. royalchicken
CHAOS GHOST!!!
02 May '03 20:07
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.