Mon, 26 Jul 2004 12:30:33 -0700 (MST) Richard Schroeppel <rcs@CS.Arizona.EDU> Another puzzle: It turns out that median-of-5 (Med5) can be constructed from the median-of-3 (Med3) function. One way is Med5(A,B,C,D,E) = Med3( A, Med3(B,C,D), Med3(B,E,Med3(A,C,D)) ). [All median-of-odd functions can be built out of any single one. In fact, any non-trival, 0-1 symmetric, monotone-nondecreasing, boolean function can be built from Med3, and vice versa. This includes weighted medians, and many others.] The expression above for Med5 in terms of Med3 is minimal. But it's far from obvious that the expression is right, and it sure doesn't look symmetrical. Even though Med5 is symmetrical in all permutations of the arguments, the expression has only the C:D swap symmetry. The puzzle is to come up with a better expression. Ideally it would exhibit full symmetry and be obviously correct. But even just having some additional symmetry would be an improvement. [On the run, so this may be cryptic:] Well, for any set S of size N, where N is odd, the median of any subset of size N-2 can only return one of 3 values (the median of S, or the values ranked 1 below and 1 above the median). So it is easy to construct something "obviously" right and completely symmetric, but it will be far from minimal. For example, if you take the median of every N-2 subset of S, and add those together, you'll get the sum of (N+1)/2 choose 2 copies of the value ranked 1 below the median, the same number of copies of the value ranked 1 above the median, and ((N-1)/2)^2 copies of the median (these sum to (N-2) choose 2). Let S' = set of medians of every N-2 subset of S. Then, median-N = sum(S') - binomial((N+1),2)*min(S') - binomial((N+1),2)*max(S') --------------------------------------------------------------- ((N-1)/2)^2 This is constructed out of median<N-2>, min, and max. We have median-1 and median-3, so the recursion terminates. This implementation of median-N is symmetric, and "obviously" right. But it is *far* from efficient. A more efficient implementation of median-N just needs to find 3 subsets of size N-2 of the set of N such that you can guarantee that the median of the 3 subsets will be different --- there is no way that will be symmetric for N>3, though (and a non-recursive implementation will be more efficient yet).