Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member 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. Donation richjohnson
    TANSTAAFL
    01 May '03 21:35
    (n-1) + (n-2) + ... + 2 + 1
  3. Standard member royalchicken
    CHAOS GHOST!!!
    01 May '03 21:58
    There is a method of choosing pairs such that the total is smaller.
  4. Donation 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...

    have you already solved this?

  5. Standard member 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. Standard member 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. Donation 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. Standard member 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.