==> 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