- I reckon compare A and B, and then A and C. If both B and C are

greater than A, compare them. Then compare D to the median of A, B

and C ("mABC") and then compare E to mABC also. If one is greater and

one is less, then mABC is the median of all five. If not, then

compare, ooh, I dunno, cos then you'll have 3 variables less than

mABC but you won't know how they compare to each other. I have 45

minutes left in my lunch break to buy and eat a big feed though, so

I'm not going to dwell over this. But there my two cents.

--- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>

wrote:>

values

> You are given 5 variables: A,B,C,D,E, but you don't know the

> of the variables. You are allowed to make up to six binary

variables,

> comparisons. That is, in each of your 6 comparisons, you can take

> any two variables, and compare them to each other to see which is

> greater. (But you still won't know the values of the variables.)

> Can you find an algorithm for choosing the pairs to compare so that

> in the end, you will know the median? (Assume no two variables are

> equal.)

>

> Or if no such algorithm will always succeed can you prove that no

> surefire algorithm exists?

>

> Note that it takes 10 comparisons to uniquely order all 5

> but I'm only asking for the median, so maybe six comparisons are

> enough. - --- In mathforfun@yahoogroups.com, video_ranger <no_reply@y...> wrote:
>

<no_reply@y...>

> --- In mathforfun@yahoogroups.com, adh_math <no_reply@y...> wrote:

> >

> > --- In mathforfun@yahoogroups.com, "Peter Otzen" <pmaxotzen@h...>

> > wrote:

> > >

> > > --- In mathforfun@yahoogroups.com, slim_the_dude

> > > wrote:

After slim's most recent post, I'm surprised. :)

> > > >

> > > > I've [found the median]! It can be done in six

> > > > comparisons:

> > > >

> > >

> > > This raises the intersting point that we mighn't need 10

> > > comparisons to completely order the 5.

> > >

> > Here's a recursive strategy that I suspect is optimal:

> >

> > [non-optimal strategy]

> >

> > The general strategy for ordering n numbers is to order (n-1) of

> > the numbers, then to compare the n-th with a number as close as

> > possible to the median of the first (n-1) numbers. I haven't

> > proven optimality of this strategy, but would be surprised if

> > there were a faster way.

> >

> But maybe one improvement, at least for large n, is to pursue the

Nice idea...can't believe I missed this! Combining with the approach

> same method (of comparing with the median) within each half set -

> that is do a binary type search for the insertion point of the last

> element. So that instead of n+1 comparisons needed to insert the

> 2n+1 element it would require roughly log_2(n) (exactly log_2(n+1)

> comparisons if n=1,3,7,15 etc..). ==> [f(2n+1)-f(2n)] ~ log_2(n)

>

of splitting the set of 2n or 2n+1 numbers into sets of n or n+1 and

starting by ordering those sets separately (essentially slim's

method, which I also missed), it looks like there are asymptotically

faster algorithms than the one I outlined.

adh