Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: $Revision: 1.6.2.14 $; site umn-cs.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!ihnp4!stolaf!mmm!umn-cs!ravikuma
From: ravikuma@umn-cs.UUCP
Newsgroups: net.math
Subject: Re: value of an integral
Message-ID: <8700001@umn-cs.UUCP>
Date: Sun, 2-Mar-86 13:44:00 EST
Article-I.D.: umn-cs.8700001
Posted: Sun Mar  2 13:44:00 1986
Date-Received: Fri, 7-Mar-86 04:20:06 EST
References: <823@drux2.UUCP>
Lines: 15
Nf-ID: #R:drux2:-82300:umn-cs:8700001:000:670
Nf-From: umn-cs!ravikuma    Mar  2 12:44:00 1986



For those interested in combinatorial algorithm design,  
here is a deceptively simple  problem:
  "A and B, two players each independently think of a
positive integer between 1 and 1000. You are allowed
to ask either of them (in any order) questions of the
form " Is your number less or equal to K?" for any K of
your choice, and find out the smaller of the guessed
                              -------
numbers. Trivially, you can do this using 20 questions,
since 10 questions suffice to find a guess. How much
better can you do? (14 questions suffice, though it is
not easy to prove that it is the lowerbound.)
Note: We are interested,  in the worst-case bound.)