Sorry, an error occurred while loading the content.

## Re: Problem 312: Find median of 5 numbers

Expand Messages
• 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
Message 1 of 16 , Dec 1, 2004
• 0 Attachment
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:
>
> You are given 5 variables: A,B,C,D,E, but you don't know the
values
> of the variables. You are allowed to make up to six binary
> 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
variables,
> but I'm only asking for the median, so maybe six comparisons are
> enough.
• ... is ... variables ... no ... are ... this ... I saw this problem posed by somebody on another board, and he claimed it could be done in six steps, but I
Message 2 of 16 , Dec 1, 2004
• 0 Attachment
--- In mathforfun@yahoogroups.com, "plano9" <plano9@y...> wrote:
>
> --- In mathforfun@yahoogroups.com, "Peter Otzen" <pmaxotzen@h...>
> wrote:
> >
> > --- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>
> > wrote:
> > >
> > > You are given 5 variables: A,B,C,D,E, but you don't know the
> > values
> > > of the variables. You are allowed to make up to six binary
> > > 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
> > variables,
> > > but I'm only asking for the median, so maybe six comparisons
are
> > > enough.
> >
> > I can do it in 7, and with luck it could be 6 or even 5.
> > I will sleep on it and see if I can eliminate the 7th
> >
> > Peter
>
> Same, I have reduced it to 7 as well. Have you solved this slim?
> The method used to get 7 on any set may be basically be the proof
> that a surefire method for 6 moves doesn't exist. In addition
this
> problem could be answered with brute force, although I don't think
> its worth the time to program something and wait for it to finish.

I saw this problem posed by somebody on another board, and he
claimed it could be done in six steps, but I think I doubt his
word. I'm not convinced it can be done in six.
• ... I ve solved it! It can be done in six comparisons: First two comparisons: take any two pairs of points and compare them. Third comparison: Of the two
Message 3 of 16 , Dec 4, 2004
• 0 Attachment
--- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>
wrote:
>
> You are given 5 variables: A,B,C,D,E, but you don't know the
> values of the variables. You are allowed to make up to six binary
> 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
> variables, but I'm only asking for the median, so maybe six
> comparisons are enough.

I've solved it! It can be done in six comparisons:

First two comparisons: take any two pairs of points and compare
them.
Third comparison: Of the two pairs, compare the two high points.

At this point, you're going to have points with this pattern:

A<B<C and D<C

4th comparison: Compare E with D

Case 1: E<D

A<B<C and E<D<C
5th comparison should be B with D The two results are symmetrical,
so WLOG

A<B<D<C and E<D

The median is the greater of B and D, and the 6th comparison will
take care of that.

Case 2: D<E

A<B<C and D<C and D<E

5th comparion should be B with E. Two possibilities

Case 2a: E<B

D<E<B<C and A<B
The median is the greater of E and A and the sixth comparison will
take care of that

Case 2b: B<E

A<B<C and B<E and D<C and D<E

6th comparison should be B with D. Two possibilities
Case 2b1: B<D

A<B<D<C and D<E D is the median

Case 2b2: D<B

A and D are < B
E and C are > B

B is the median

We're done
• ... take ... Not sure what you mean by WLOG, but what if the values were, A=1, B=5, E=6, D=7, C=9 I am not sure that you have it??? Perhaps you meant to say
Message 4 of 16 , Dec 4, 2004
• 0 Attachment
--- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>
wrote:
>
> --- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>
> wrote:
> >
> > You are given 5 variables: A,B,C,D,E, but you don't know the
> > values of the variables. You are allowed to make up to six binary
> > 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
> > variables, but I'm only asking for the median, so maybe six
> > comparisons are enough.
>
> I've solved it! It can be done in six comparisons:
>
> First two comparisons: take any two pairs of points and compare
> them.
> Third comparison: Of the two pairs, compare the two high points.
>
> At this point, you're going to have points with this pattern:
>
> A<B<C and D<C
>
> 4th comparison: Compare E with D
>
> Case 1: E<D
>
> A<B<C and E<D<C
> 5th comparison should be B with D The two results are symmetrical,
> so WLOG
>
> A<B<D<C and E<D

Not sure what you mean by WLOG, but what if the values were,
A=1, B=5, E=6, D=7, C=9

I am not sure that you have it???

Perhaps you meant to say the greater of B and E in the next line?

>
> The median is the greater of B and D, and the 6th comparison will
> take care of that.
>
> Case 2: D<E
>
> A<B<C and D<C and D<E
>
> 5th comparion should be B with E. Two possibilities
>
> Case 2a: E<B
>
> D<E<B<C and A<B
> The median is the greater of E and A and the sixth comparison will
> take care of that
>
> Case 2b: B<E
>
> A<B<C and B<E and D<C and D<E
>
> 6th comparison should be B with D. Two possibilities
> Case 2b1: B<D
>
> A<B<D<C and D<E D is the median
>
> Case 2b2: D<B
>
> A and D are < B
> E and C are > B
>
> B is the median
>
>
> We're done
• ... symmetrical, ... WLOG is the standard internet abbreviation for without loss of generality . I say this because of the symmetry. Whichever is greater
Message 5 of 16 , Dec 4, 2004
• 0 Attachment
--- In mathforfun@yahoogroups.com, "Peter Otzen" <pmaxotzen@h...>
wrote:
> > Case 1: E<D
> >
> > A<B<C and E<D<C
> > 5th comparison should be B with D The two results are
symmetrical,
> > so WLOG
> >
> > A<B<D<C and E<D
>
> Not sure what you mean by WLOG, but what if the values were,
> A=1, B=5, E=6, D=7, C=9
>
> I am not sure that you have it???
>
> Perhaps you meant to say the greater of B and E in the next line?
>

WLOG is the standard internet abbreviation for "without loss of
generality". I say this because of the symmetry. Whichever is
greater between B and D, you're going to be able know the precise
order of 4 of the numbers, and the fifth is going to be less than the
the 2nd highest of the four. The rest of my proof follows from that.
• ... the ... that. Understood, and well done. I realise now that you must have meant to go on to say the greater of B and E is the median, and the 6th test
Message 6 of 16 , Dec 4, 2004
• 0 Attachment
--- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>
wrote:
>
> --- In mathforfun@yahoogroups.com, "Peter Otzen" <pmaxotzen@h...>
> wrote:
> > > Case 1: E<D
> > >
> > > A<B<C and E<D<C
> > > 5th comparison should be B with D The two results are
> symmetrical,
> > > so WLOG
> > >
> > > A<B<D<C and E<D
> >
> > Not sure what you mean by WLOG, but what if the values were,
> > A=1, B=5, E=6, D=7, C=9
> >
> > I am not sure that you have it???
> >
> > Perhaps you meant to say the greater of B and E in the next line?
> >
>
> WLOG is the standard internet abbreviation for "without loss of
> generality". I say this because of the symmetry. Whichever is
> greater between B and D, you're going to be able know the precise
> order of 4 of the numbers, and the fifth is going to be less than
the
> the 2nd highest of the four. The rest of my proof follows from
that.

Understood, and well done.

I realise now that you must have meant to go on to say the greater of
B and E is the median, and the 6th test would sort that out, since
the 5th test was already comparing B with D.

Peter
• ... This raises the intersting point that we mighn t need 10 comparisons to completely order the 5. Perhaps don t even need 8. Peter
Message 7 of 16 , Dec 4, 2004
• 0 Attachment
--- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>
wrote:
>
> I've solved it! It can be done in six comparisons:
>

This raises the intersting point that we mighn't need 10 comparisons
to completely order the 5. Perhaps don't even need 8.

Peter
• ... Here s a recursive strategy that I suspect is optimal: Pick any three numbers and compare them pairwise, obtaining (possibly after renaming) C
Message 8 of 16 , Dec 5, 2004
• 0 Attachment
--- In mathforfun@yahoogroups.com, "Peter Otzen" <pmaxotzen@h...>
wrote:
>
> --- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>
> wrote:
> >
> > 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. Perhaps don't even need 8.
>
Here's a recursive strategy that I suspect is optimal: Pick any three
numbers and compare them pairwise, obtaining (possibly after renaming)

C < B < A.

Next compare D with B; no matter what the outcome, transitivity gives
an extra piece of information, and (at worst) a fifth comparison
orders the four elements. After renaming,

D < C < B < A.

Now compare E with C (at most sixth comparison):
If E < C, the elements are ordered after seven comparisons.
If E > C, they're ordered after at most eight.

---

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.

To calculate the number of comparisons required by this method, let
f(n) be the maximum number of comparisons (i.e. "the worst case"), and
observe that

f(2n+1) = f(2n) + n + 1,
f(2n+2) = f(2n+1) + n + 1 = f(2n) + 2(n+1).

Since f(1) = 0 and f(2) = 1, a bit of algebra shows that

f(2n) = n^2 + n - 1,
f(2n+1) = n^2 + 2n.

In particular, f(n) ~ n^2/4 for large n. The first few values are:

n | f(n)
========
1 | 0
2 | 1
3 | 3
4 | 5
5 | 8
6 | 11
7 | 15
8 | 19, etc.

There are (n choose 2) = n(n+1)/2 binary comparisons of n numbers, so
the above strategy is asymptotically better than brute force by a
factor of 2.

• ... three ... renaming) ... gives ... optimality ... and ... so ... But maybe one improvement, at least for large n, is to pursue the same method (of comparing
Message 9 of 16 , Dec 6, 2004
• 0 Attachment
>
> --- In mathforfun@yahoogroups.com, "Peter Otzen" <pmaxotzen@h...>
> wrote:
> >
> > --- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>
> > wrote:
> > >
> > > 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. Perhaps don't even need 8.
> >
> Here's a recursive strategy that I suspect is optimal: Pick any
three
> numbers and compare them pairwise, obtaining (possibly after
renaming)
>
> C < B < A.
>
> Next compare D with B; no matter what the outcome, transitivity
gives
> an extra piece of information, and (at worst) a fifth comparison
> orders the four elements. After renaming,
>
> D < C < B < A.
>
> Now compare E with C (at most sixth comparison):
> If E < C, the elements are ordered after seven comparisons.
> If E > C, they're ordered after at most eight.
>
> ---
>
> 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.
>
> To calculate the number of comparisons required by this method, let
> f(n) be the maximum number of comparisons (i.e. "the worst case"),
and
> observe that
>
> f(2n+1) = f(2n) + n + 1,
> f(2n+2) = f(2n+1) + n + 1 = f(2n) + 2(n+1).
>
> Since f(1) = 0 and f(2) = 1, a bit of algebra shows that
>
> f(2n) = n^2 + n - 1,
> f(2n+1) = n^2 + 2n.
>
> In particular, f(n) ~ n^2/4 for large n. The first few values are:
>
> n | f(n)
> ========
> 1 | 0
> 2 | 1
> 3 | 3
> 4 | 5
> 5 | 8
> 6 | 11
> 7 | 15
> 8 | 19, etc.
>
> There are (n choose 2) = n(n+1)/2 binary comparisons of n numbers,
so
> the above strategy is asymptotically better than brute force by a
> factor of 2.
>

But maybe one improvement, at least for large n, is to pursue the
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)
• ... We definitely know that 7 is a lower bound, because of the following argument: There are 5! = 120 possible orderings. Each comparison at most eliminates
Message 10 of 16 , Dec 6, 2004
• 0 Attachment
>
> --- In mathforfun@yahoogroups.com, "Peter Otzen" <pmaxotzen@h...>
> wrote:
> >
> > --- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>
> > wrote:
> > >
> > > 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. Perhaps don't even need 8.
> >

We definitely know that 7 is a lower bound, because of the following
argument:

There are 5! = 120 possible orderings. Each comparison at most
eliminates half of those orderings, so it will take at least log
(base 2) of 120 = 6.9 comparisons.
• ... Okay folks... 7 is indeed the lowest possible number of of comparisons to completely order the 5 elements, because I ve just found a way of doing it in 7.
Message 11 of 16 , Dec 6, 2004
• 0 Attachment
--- In mathforfun@yahoogroups.com, slim_the_dude <no_reply@y...>
wrote:
>
> We definitely know that 7 is a lower bound, because of the
> following argument:
>
> There are 5! = 120 possible orderings. Each comparison at most
> eliminates half of those orderings, so it will take at least log
> (base 2) of 120 = 6.9 comparisons.

Okay folks... 7 is indeed the lowest possible number of of
comparisons to completely order the 5 elements, because I've just
found
a way of doing it in 7.

Comparison 1: compare any two.
A<B

Comparison 2: compare any other two:
A<B and C<D

Comparison 3: Compare B with D
WLOG (because of symmetry):
A<B<D and C<D

Comparison 4: Compare E with B

Case 1. E<B

A<B<D and E<B and C<D
Comparison 5: Compare A with E
WLOG (because of symmetry of the relationships between A,B and E),
we get: A<E<B<D and C<D

There are four cases for C: C<A, A<C<E, E<C<B, or B<C<D

Comparison 6: compare C with E
This reduces the possibilities of C to two cases (the 1st two or
latter two above), and the 7th comparison will finish us off.

Case 2: B<E

A<B<D and C<D and B<E

Comparison 5: compare E with D
Case 2a: E<D
A<B<E<D and C<D

This is just like the pattern we just solved above in two
comparisons, so again, we're done in 7.

Case 2b: D<E
A<B<D<E and C<D

Compare C with A.
Case 2b1: C<A

Then C<A<B<D<E and we're done.

Case 2b2: A<C

Then A<B<D<E and A<C<D
C is wither between A and B or betwen B and D. The 7th comparison
will take care of that.

QED. It can be done in 7 comparisons.
• ... ... After slim s most recent post, I m surprised. :) ... Nice idea...can t believe I missed this! Combining with the approach of splitting
Message 12 of 16 , Dec 7, 2004
• 0 Attachment
--- In mathforfun@yahoogroups.com, video_ranger <no_reply@y...> wrote:
>
> --- 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:
> > > >
> > > > 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.
> >
After slim's most recent post, I'm surprised. :)

> But maybe one improvement, at least for large n, is to pursue the
> 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)
>
Nice idea...can't believe I missed this! Combining with the approach
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.