Fun Math Problem - Page 2

On August 27 2009 11:46 EtherealDeath wrote:
Within this bounded interval are some set number of other bounded intervals, which may or may not intersect with other bounded intervals. For example, one possible set of intervals is {[1,100],[2,36],[45,798]}.

On August 27 2009 21:52 ninjafetus wrote:
Restating the problem more clearly for anyone still confused.

You are given an closed interval [a,b], and some number of closed subintervals S_i = [a_i, b_i].
For each S_i, choose a c_i contained in [a_i, b_i] such that min_{i,j} (c_i, c_j) is maximized.

Wait, that might not be any more clear at all, save for math people who already get it...

In other words, each subinterval gets a point. Choose the points so that the distance between the two closest points is maximized over all possible choices of points.

On August 27 2009 18:56 Muirhead wrote:
My argument definitely works. I know a lot of people on this site spurt nonsense solutions to these kinds of questions, but I do actually have a math/IMO background . It's a little complicated, but if you think about it you'll understand it. I am well aware that changing a_1 can change every other a_i.

Alternatively, note that my argument proves that the coordinates of the solution points are rational linear combinations of the coordinates of the endpoints. Furthermore, the argument provides natural bounds on the denominators of the coefficients. Thus, we only need to check a finite number of d as in severedevil's argument.

On August 27 2009 13:49 Muirhead wrote:
I do not know (or believe) that there is a terribly simple formula for the answer.

If I just had to write a computer program to find an exact answer, I would proceed inductively. Suppose that there are n intervals, and that I have a computer program that can find the answer given n-1 intervals.

The computer program (call it P) that solves for n-1 intervals would receive input of the form [a_1,b_1],[a_2,b_2],...,[a_{n-1},b_{n-1}] where the a_i are inputted in nondecreasing order.

Furthermore, suppose the computer program P would give me my answer as a function of a_1, assuming a_1 <= a_2 and that the other a_i and b_i are fixed. The function would be piecewise linear and therefore easy to express.

I claim that, given P, it is easy to construct a similar program which works with an input of n intervals. The new program Q would insert a test value of a_1. Then it would run P on [a_2,b_2],...,[a_n,b_n], spitting out a function of a_2. It would compute the value of a_2 such that the maximum minimum distance spit out by that function is as close to |a_1-a_2| as possible, thus solving the problem for the test value of a_1. Through judicious choices of test values of a_1, the full function of a_1 could be discovered. This is because Q knows the answer it should spit out is a piecewise linear function of a_1 with the number of distinct linear components a bounded function of n.