Problem of the Week 1078

My Name is Max. Where Am I?

Suppose f(x) is a real-valued function on [0, 1] that is strictly increasing between x = 0 and a certain value, x = MAX, and then is strictly decreasing from x = MAX to x = 1 (such functions are called unimodal). You may ask 5 questions of the form: "What is the value of f(x)?" where you get to specify x. The x-values you choose can depend on the answers to questions already answered.

Your mission is to determine an interval that is guaranteed to contain MAX, the idea being to make this interval as small as you can. How small can you guarantee?

Note: The 5 is arbitrary. There is an elegant solution as a function of n, where n is the number of questions, and if you solve 5 you will probably have solved the general question.

Of course, this formulation ignores issues related to the full specification of real numbers. Just assume that you can set x to be any real number with all its digits, and the answer, f(x), will consist of all the digits of that real number. This technicality is easily avoided by restricting the problem to terminating rationals, which would not change its essence.

Source: Larry Carter, though it turns out to have a long history. It appeared in the Spring 2007 puzzle column in EMISSARY, the newsletter of MSRI.

© Copyright 2007 Stan Wagon. Reproduced with permission.



24 August 2007