Posers and Puzzles

Posers and Puzzles

  1. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    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. Donationrichjohnson
    TANSTAAFL
    Walking on sunshine
    Joined
    28 Jun '01
    Moves
    63101
    01 May '03 21:35
    (n-1) + (n-2) + ... + 2 + 1
  3. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    01 May '03 21:58
    There is a method of choosing pairs such that the total is smaller.
  4. Donationrichjohnson
    TANSTAAFL
    Walking on sunshine
    Joined
    28 Jun '01
    Moves
    63101
    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 memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    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 memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    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. Donationrichjohnson
    TANSTAAFL
    Walking on sunshine
    Joined
    28 Jun '01
    Moves
    63101
    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 memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    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.
Back to Top