[unreality]

In spirit of the sixth Harry Potter movie coming out (even though I don't even like Harry Potter ), I bring you the third installment of and

A distant realm has 100 people of wizarding blood, no more, no less. Recall from the previous riddles that no two wizards are of the same strength level. The Sultan of this realm (a nonwizard) wants to rank them from best to worst in exact order of strength, without error, using the ranking mind-duel process from the previous riddles.

You are his main logician, called in to figure out how to do it. Furthermore, when a wizard runs a test, he/she charges in gold, so the Sultan needs to know how much to pull out of the treasury... so what is the shortest number of duels it could take to determine? What is the maximum necessary? What is the expected?

What's your strategy?

I actually haven't figured it out myself yet. This popped into my mind when I was out running and I had to come back and post it... so we're all in uncharted water here ;D

[Guest]

basically you could simply execute a merge sort. this gives minimum, maximum, and average of aprox. 650 comparisons. (n*log[2] n).

in case you are unfamiliar with the algorithm, here's an example with 20 wizards.

let's say the wizard's strength is

14,62,23,7,19,88,51,30,10,2,43,76,9,24,15,6,32,20,45,81

then divide the wizards into two groups left and right.

A = 14,62,23,7,19,88,51,30,10,2 B =43,76,9,24,15,6,32,20,45,81

divide again.

A = 14,62,23,7,19 C =88,51,30,10,2 B =43,76,9,24,15 D =6,32,20,45,81

divide again.

A = 14,62 E =23,7,19 C =88,51 F = 30,10,2 B =43,76 G = 9,24,15 D =6,32 H =20,45,81

now that you have groups of aprox. 2 you can begin to compare.

for the groups of 2, simply compare, then swap their order if the larger is on the left.

for the groups of 3, you'll need 2-3 comparisons.

after that you can begin the merge part of the algorithm.

here's what the groups look like prior.

A = 14,62 E =7,19,23 C =51,88 F = 2,10,30 B =43,76 G = 9,15,24 D =6,32 H =20,45,81

total comparisons = 15.

so basically you take the first element in A, then compare it with the first element in E.

if the E element is smaller, then compare the first element in A with the second element in E.

if the element in E is larger, then you know the first element in A goes between those two.

then compare the second element in A with the second element in E.

if the second element in A is larger, then go to the third element in E.

if the second element in A is still larger, then you know it's the last element in that group.

so after these 4 comparisons we have

A = 7,14,19,23,62. you can do a similar sort of thing with the remaining groups.

result after 1 merge;

A = 7,14,19,23,62 C = 2,10,30,51,88 B = 9,15,24,43,76 D = 6,20,32,45,81

total comparisons = 28

use the same merge process, until you are back to 1 group,

result after second merge.

A = 2,7,10,14,19,23,30,51,62,88 B = 6,9,15,20,24,32,43,45,76,81

total comparisons = 46

result after final merge.

2,6,7,9,10,14,15,19,20,23,24,30,32,43,45,51,62,76,81,88

total comparisons = 64.

i would have guessed prior to the algorithm roughly 4.3*20 = 86 comparisons.

[unreality]

basically you could simply execute a merge sort. this gives minimum, maximum, and average of aprox. 650 comparisons. (n*log[2] n).

in case you are unfamiliar with the algorithm, here's an example with 20 wizards.

let's say the wizard's strength is

14,62,23,7,19,88,51,30,10,2,43,76,9,24,15,6,32,20,45,81

then divide the wizards into two groups left and right.

A = 14,62,23,7,19,88,51,30,10,2 B =43,76,9,24,15,6,32,20,45,81

divide again.

A = 14,62,23,7,19 C =88,51,30,10,2 B =43,76,9,24,15 D =6,32,20,45,81

divide again.

A = 14,62 E =23,7,19 C =88,51 F = 30,10,2 B =43,76 G = 9,24,15 D =6,32 H =20,45,81

now that you have groups of aprox. 2 you can begin to compare.

for the groups of 2, simply compare, then swap their order if the larger is on the left.

for the groups of 3, you'll need 2-3 comparisons.

after that you can begin the merge part of the algorithm.

here's what the groups look like prior.

A = 14,62 E =7,19,23 C =51,88 F = 2,10,30 B =43,76 G = 9,15,24 D =6,32 H =20,45,81

total comparisons = 15.

so basically you take the first element in A, then compare it with the first element in E.

if the E element is smaller, then compare the first element in A with the second element in E.

if the element in E is larger, then you know the first element in A goes between those two.

then compare the second element in A with the second element in E.

if the second element in A is larger, then go to the third element in E.

if the second element in A is still larger, then you know it's the last element in that group.

so after these 4 comparisons we have

A = 7,14,19,23,62. you can do a similar sort of thing with the remaining groups.

result after 1 merge;

A = 7,14,19,23,62 C = 2,10,30,51,88 B = 9,15,24,43,76 D = 6,20,32,45,81

total comparisons = 28

use the same merge process, until you are back to 1 group,

result after second merge.

A = 2,7,10,14,19,23,30,51,62,88 B = 6,9,15,20,24,32,43,45,76,81

total comparisons = 46

result after final merge.

2,6,7,9,10,14,15,19,20,23,24,30,32,43,45,51,62,76,81,88

total comparisons = 64.

i would have guessed prior to the algorithm roughly 4.3*20 = 86 comparisons.

I like the idea of the merge sort, the problem is, the comparing method isn't steadfast. If you have three wizards (A, B and C), the possibilities are:

ABC

ACB

BAC

BCA

CAB

CBA

say A compares B & C and gets B>C. That narrows it down to:

ABC

CAB

CBA

that is, it only cuts out half of the possibilities. Furthermore, when you separate the list into pairs of two, you can't just objectively compare two wizards. All comparisons require three total participants and the strength of the compar-er changes the results.

Maybe I should have reposted the comparison technique from the previous problems. Basically it is this: a compar-er wizard compares two dueling wizards. If the compar-er is stronger than both of them, the compar-er gives the correct result. If either wizard (or both) is stronger than the compar-er, the compar-er gives the opposite result because the compar-er isn't sufficiently powerful to correctly compare the two dueling wizards.

Unless I've misread, I don't think the merge sort works with this in mind

I've been working on some stuff, later today I'll think more on this problem too hehe

[edit - typo]

Edited July 18, 2009 by unreality

[Guest]

hmm that does add an interesting twist to the problem.

it seems to me tough the three possibilities would be...

if A measures B and C and finds B is greater,

ABC - A weaker than both, give incorrect result

BAC - A weaker than C, gives incorrect result

CBA - A stronger than both, gives correct result.

from here you'd want C to measure A and B.

so yeah you could still do a sort of merge sort, but you'd have to start with the large side and work your way to the small.

here's an example with 12 wizards doing a merge sort.

19,24,12,7,61,55,3,32,45,67,30,4

A = 19,24,12

B = 7,61,55

C = 3,32,45

D = 67,30,4

so, 19 measures 24 and 12 and gives wrong result (says 12 is greater).

so after that we would have three possible orders.

19,12,24

12,19,24

24,12,19

so we use the 24 to compare, and says 12 less than 19. from this we can conclude the middle is the correct order.

with B,

7 compares 61,55

7,55,61

55,7,61

61,55,7

61 compares 7 and 55 from this either the top or bottom is correct, so we'll need one more comparison to determine which.

with C

3 compares 32,45

3,32,45

32,3,45

45,32,3

45 compares 3 and 32 once again either top or bottom, and need 1 more comparison.

with D

67 compares 30 and 4

67,30,4

30,67,4

4,30,67

so 4 will compare 30 and 67, once again either top or bottom.

total comparisons, 11, current order,

A = 12,19,24

B = 7,55,61

C = 3,32,45

D = 4,30,67

from here, we take the two weakest ones in each group, and use the two strongest ones to compare them.

24 will compare 12 and 7. we know 24 is greater the 12 but not sure whether or not 24 is greater than 7.

so we have two possibilities,

12,24,7

7,12,24

from this we use the 61 to compare 7 and 12. we get 12 as greater and we know 61 is greater than 7, therefore the bottom one must be correct.

so then use 24 and compare 12 and 55. then use 61.

from these four comparisons we would get

7,12,19,24,55,61

for C and D, we need 10 comparisons.

3,4,30,32,45,67

total comparisons = 25

after the final merge,

45 comparisons.

12*3.5 = 42. so its still about n*log[2] n

[unreality]

hmm that does add an interesting twist to the problem.

it seems to me tough the three possibilities would be...

if A measures B and C and finds B is greater,

ABC - A weaker than both, give incorrect result

BAC - A weaker than C, gives incorrect result

CBA - A stronger than both, gives correct result.

I was doing strongest to weakest, so ABC would be A>B>C. Flipping yours or mine around, they're exactly the same

from here you'd want C to measure A and B.

so yeah you could still do a sort of merge sort, but you'd have to start with the large side and work your way to the small.

here's an example with 12 wizards doing a merge sort.

19,24,12,7,61,55,3,32,45,67,30,4

A = 19,24,12

B = 7,61,55

C = 3,32,45

D = 67,30,4

so, 19 measures 24 and 12 and gives wrong result (says 12 is greater).

so after that we would have three possible orders.

19,12,24

12,19,24

24,12,19

so we use the 24 to compare, and says 12 less than 19. from this we can conclude the middle is the correct order.

with B,

7 compares 61,55

7,55,61

55,7,61

61,55,7

61 compares 7 and 55 from this either the top or bottom is correct, so we'll need one more comparison to determine which.

with C

3 compares 32,45

3,32,45

32,3,45

45,32,3

45 compares 3 and 32 once again either top or bottom, and need 1 more comparison.

with D

67 compares 30 and 4

67,30,4

30,67,4

4,30,67

so 4 will compare 30 and 67, once again either top or bottom.

total comparisons, 11, current order,

A = 12,19,24

B = 7,55,61

C = 3,32,45

D = 4,30,67

from here, we take the two weakest ones in each group, and use the two strongest ones to compare them.

24 will compare 12 and 7. we know 24 is greater the 12 but not sure whether or not 24 is greater than 7.

so we have two possibilities,

12,24,7

7,12,24

from this we use the 61 to compare 7 and 12. we get 12 as greater and we know 61 is greater than 7, therefore the bottom one must be correct.

so then use 24 and compare 12 and 55. then use 61.

from these four comparisons we would get

7,12,19,24,55,61

for C and D, we need 10 comparisons.

3,4,30,32,45,67

total comparisons = 25

after the final merge,

45 comparisons.

12*3.5 = 42. so its still about n*log[2] n

that seems to work!

I have an idea... I don't know what the 'computational complexity' of it is, maybe you can help with that:

number the wizards 1-100

say we pick two wizards at random, X and Y. That leaves 98 more to split in 49 pairs. X does all 49 and Y does all 49, for a total of 98 duels.

Now, in the pairs where X and Y differ in their results (call these duelers A and B), the following are possible:

say that X got A>B and Y got B>A...

X>A>B

B>X>A

B>A>X

Y>B>A

A>Y>B

A>B>Y

merging them:

X>A>B>Y

X>A>Y>B

Y>B>X>A

Y>B>A>X

now take B and have him/her compare X and Y.

If B gets Y>X, then X>Y and A>B

If B gets X>Y, then Y>X and B>A.

~~

If X and Y coincide that A>B, they're either both stronger or both weaker...

X>Y>A>B

Y>X>A>B

B>A>X>Y

B>A>Y>X

B>X>A>Y

B>Y>A>X

B>X>Y>A

B>Y>X>A

in this scenario, A is never strongest, so have A compare B and X. In the two scenarios in which A says B>X, you know that A>B. If A says X>B, then B>A.

After you do that once, you know the relationship of X to Y, and thus don't ever need to do it again, and thus you'll also know the A>B or B>A for that pair. And if by luck you don't need to do it at all, you'll do it anyway just to get whether X or Y is larger. So 98+1=99 for the lowest end of the range so far (that's if X and Y disagree on every single one, the ideal case). But for all pairs where X and Y agree, you'll need an additional comparison as I've outlined.

But if all are "disagrees", after 99 trials, you have 50 pairs that are separated into stronger and weaker (since you'll know X and Y too).

If not, you could have a maximum of 49 disagreements, and need 98*2=196 trials. Plus one more to determine X or Y makes 197.

So it takes 99-197 trials to have 50 ordered pairs.

Now group the weaker half into one group of 50 and the stronger half into another group of 50. They become separate systems now, but with a similar tactic. Each will take 49-97 making a total so far of 197-391 trials to break it down into four groups of 25 each. 1-25, 26-50, 51-75 and 76-100.

I'm not sure where to proceed from there. Maybe have one compar-er and 12 pairs in each set? I don't think that will work... I'll have to think about it further. But right now it's a little less than 2-4 times n, which is pretty good so far. But it will take more trials for sure.

[Guest]

it sounds like your doing the quick sort method. your taking all wizards that are weaker than x and y into 1 group, and then all wizards that are stronger than x and y and making them into a group. if so then from here, you would take two wizards from the weak and use them to compare with all the other weak wizards, and two wizards from the strong and use them to compare with all the other strong wizards, etc.

this method has average and best roughly n*log[2] n, but can have worst case of n^2.

you may also want to look at the shell sort and the heap sort as well, which can give better averages, though have about the same worst case as the merge sort.

Edited July 21, 2009 by phillip1882