lotus

previous page: 357 logic/weighing/box.p
  
page up: Puzzles FAQ
  
next page: 359 logic/weighing/gummy.bears.p

358 logic/weighing/find.median.p




Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

358 logic/weighing/find.median.p


What is the least number of pairwise comparisons needed to find the median of
2n+1 distinct real numbers?

logic/weighing/find.median.s

Consider median of three numbers {a,b,c}.
Let G[a,b]=max(a,b) and L[a,b]=min(a,b)
If we assume that median of {a,b,c} can be computed by two
comparisons, then the solution must be one of the following:
G[c,G[a,b]], G[c,L[a,b]], L[c,G[a,b]], L[c,L[a,b]].
However, it is easily seen that none of these provides
a solution. Therefore, we need more than two comparisons to
get median of three numbers.

Now, consider median of 5 numbers {a,b,c,d,e}.
There are two possible ways to start the computation.
Let Ci[a,b] denote the ith comparison between {a} and {b}.
First, we could start with C1[a,b] and C2[c,d].
Second, we could start with C2[a,C1[b,c]].
We ignore other trivialities such as C1[a,a] or C2[a,C1[a,b]].

In the first case, the next operation is to find
median of S={e,C1[a,b],C2[c,d]} which requires at least three
comparisons in addition to the two comparisons already performed.
So the total cost of the first approach is at least 5 comparisons.
However, if the median is not equal to {e} then we can always
choose C1 and C2 such that the median is not in S.

In the second case, the next step is to find median of S={C2[a,C1[b,c]],d,e}.
Again, the total cost of this approach is at least five comparisons.
If median is not equal to {d} or {e}, we can again always
choose C1 and C2 such that the median is not in S.

Other starting sets, such as {e,d,c,b,a}, can always be ordered
as {a,b,c,d,e}. This shows that the argument covers all possible cases.

Navid,
haddadi@sipi.usc.edu

 

Continue to:













TOP
previous page: 357 logic/weighing/box.p
  
page up: Puzzles FAQ
  
next page: 359 logic/weighing/gummy.bears.p