Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site fisher.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!princeton!astrovax!fisher!larsen
From: larsen@fisher.UUCP (Michael Larsen)
Newsgroups: net.math
Subject: Re: value of an integral
Message-ID: <1400@fisher.UUCP>
Date: Tue, 11-Mar-86 12:01:26 EST
Article-I.D.: fisher.1400
Posted: Tue Mar 11 12:01:26 1986
Date-Received: Wed, 12-Mar-86 22:53:59 EST
References: <823@drux2.UUCP> <8700001@umn-cs.UUCP>
Organization: Princeton University.Mathematics
Lines: 56

> 
> 
> 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.)

	To determine the required number of guesses, define more generally
f(x, y) to be the number of questions required to determine the lesser of
two integers, one in the interval [1, x], one in the interval [1+x-y, x],
where x >= y.  It is easy to show that the optimal first question in this
situation relates to the larger of the two intervals, [1, x].  This reduces
the computation of f(1000, 1000) to a problem requiring ~10^6 memories and ~10^9
operations. The calculation is simplified by defining g(m, n), for m >= f(n, n),
to be the largest integer p such that f(p, n) = m.  Clearly,

(*)			f(m+1, n) = f(m, n) + 2^m.

Now define h(n) = g(f(n, n), n).  If you know h(n), equation (*) gives all
other values of g(m, n).  Having computed h(n) and f(n, n) for all n such that
f(n, n) < M, you compute h(n) for all n with f(n, n) = M as follows:

Take the largest k with f(k, k) = M - 1 such that f(M - 1, k) <= n.  If no
such k exists, then f(n, n) > M.  If such a k does exist, then consider

			p = k + g(M - 1, n - k).

If p >= n, then f(n, n) = M, and h(n) = p.  Otherwise f(n, n) > M.
This gives a linear time, linear memory algorithm for computing f(x, x) for
all x < N.  Having implemented it, I report the following results:

			Range of n	Value of f(n, n)
			1		0
			2		2
			3		3
			4 - 6		4
			7 - 10		5
			11 - 19		6
			20 - 34		7
			35 - 62		8
			63 - 113	9
			114 - 209	10	
			210 - 387	11
			388 - 720	12
			721 - 1350	13

In particular, f(1000, 1000) = 13.