wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Unit Interval Bins
        
(Message started by: Barukh on Jan 30th, 2004, 4:13am)
Title: Unit Interval Bins
Post by Barukh on Jan 30th, 2004, 4:13am
Given a unit interval [0, 1].

1. Find 10 numbers a1, …, a10 satisfying the following conditions:
   a1 is in this interval;
   a1, a2 are in different halves of this interval;
   a1, a2, a3 are in different thirds of this interval;
   …
   a1, …, a10 are in different tenths of this interval.

2. For what N, N such numbers exist?
Title: Re: Unit Interval Bins
Post by John_Gaughan on Jan 30th, 2004, 5:56am
1. I believe this is possible.

::
[hide]0 < a1 < 1/2
1/2 < a2 < 2/3
2/3 < a3 < 3/4
3/4 < a4 < 4/5
4/5 < a5 < 5/6
5/6 < a6 < 6/7
6/7 < a7 < 7/8
7/8 < a8 < 8/9
9/10 < a9 < 10/11
10/11 < a10 < 1
[/hide] ::

2. I suspect that :: [hide]for all N [subset] [smiley=bbz.gif], N [smiley=ge.gif] 1[/hide] :: I think mathematical induction can prove this, I'll see if I can come up with a proof.
Title: Re: Unit Interval Bins
Post by John_Gaughan on Jan 30th, 2004, 6:05am
Ah crap, I just answered the wrong question. Back to the drawing board...
Title: Re: Unit Interval Bins
Post by Sameer on Jan 30th, 2004, 10:23am
I don't get it...

just a simple notion to my confusion

last statement says they are in different tenths of interval
Consider a2 .. so it should be in [1/10,2/10] interval

Second statement says a1,a2 are in different halves
so a2 lies in [1/2,1]

these two intervals are disjoint.. no numbers exist.. or am i missing something..

equal intervals? order of numbers? argh... i know its friday...
Title: Re: Unit Interval Bins
Post by John_Gaughan on Jan 30th, 2004, 10:56am

on 01/30/04 at 10:23:13, Sameer wrote:
last statement says they are in different tenths of interval
Consider a2 .. so it should be in [1/10,2/10] interval

Second statement says a1,a2 are in different halves
so a2 lies in [1/2,1]

these two intervals are disjoint.. no numbers exist.. or am i missing something..


I don't think the the numbers need to be consecutive, i.e. a2 does not have to be between a1 and a3. If the numbers have to be in order there is no solution.

I think I found the solution:
::[hide]
a1 = 0.01
a2 = 0.99
a3 = 0.51
a4 = 0.41
a5 = 0.31
a6 = 0.81
a7 = 0.21
a8 = 0.61
a9 = 0.71
a10 = 0.11
[/hide]::

edit: changed wording to be more clear
Title: Re: Unit Interval Bins
Post by Barukh on Jan 31st, 2004, 10:22am

on 01/30/04 at 10:56:12, John_Gaughan wrote:
I think I found the solution:

Nice try, John, but unfortunately it doesn't work. For instance, [hide]a3, a4 are both in [0.4, 0.6] which is a single bin when divinding the interval into 5 pieces.[/hide] :(
Title: Re: Unit Interval Bins
Post by towr on Feb 1st, 2004, 9:13am
I think I found a solution, or rather 3968 :P
once you know the order of the ai intervals you can easily determine how large their intervals would be.
and 10! isn't that much...

Here's one set of solutions:
a1 : [0, 252]        ( [0,    0.1] )
a6 : [420, 504]      ( [0.167, 0.2] )
a8 : [630, 756]      ( [0.25,  0.3] )
a3 : [945, 1008]     ( [0.375, 0.4] )
a9 : [1120, 1260]    ( [0.444, 0.5] )
a4 : [1400, 1440]    ( [0.556, 0.571429] )
a5 : [1680, 1764]    ( [0.667, 0.7] )
a7 : [1960, 2016]    ( [0.778, 0.8] )
a2 : [2240, 2268]    ( [0.889, 0.9] )
a10: [2268, 2520]    ( [0.9,   1] )
Title: Re: Unit Interval Bins
Post by Sameer on Feb 2nd, 2004, 8:38am
What method did you use? ???
Title: Re: Unit Interval Bins
Post by towr on Feb 2nd, 2004, 9:05am
Brute force
As I said, once you've determine the sequence the ai's appear in, you also know the interval they must lie in.

if a1 > a2 then
   S(a2) [subset] [0,0.5] and S(a1) [subset] [0.5,1]
   if a3 > a1 then
       S(a2) [subset] [0,0.33...] and
       S(a1) [subset] [0.33...,0.66...] and
       S(a3) [subset] [0.66...,1]
       <...>
   else if a3 < a2 then
       S(a3) [subset] [0,0.33...] and
       S(a2) [subset] [0.33...,0.66...] and
       S(a1) [subset] [0.66...,1]
       <...>
   else
       S(a2) [subset] [0,0.33...] and
       S(a3) [subset] [0.33...,0.66...] and
       S(a1) [subset] [0.66...,1]
       <...>
   endif
else
   S(a1) [subset] [0,0.5] and S(a2) [subset] [0.5,1]
   <...>
endif

(I'm not going to work out the whole tree, since that'll have level 10 depth, and 10! leaves..)

The easy way to get a final answer is to take the conjunction of all intervals ai must lie in. a simple double loop can do this.
So basicly I just tried all 10! permutations of the ai's and at the same time checked that none of the intervals was empty (or singular)

Really, it's not brilliant or anything, just an easy way to solve problems if it's tracktable..
Title: Re: Unit Interval Bins
Post by John_Gaughan on Feb 2nd, 2004, 11:13am
towr, I understand how you solved it but I am bit by another problem -- how to generate those permutations without using up over 128 MB of my computer's memory and to do it in less than O(n!). Even after googling I can't find any algorithm to brute force permutations, any suggestions?
Title: Re: Unit Interval Bins
Post by towr on Feb 2nd, 2004, 11:47am
You don't have to first generate each permutation, and then check them all. You can do it while you're generating them, and forget about all those that don't work, and drop those that do work to the output. This way it only costs O(1) memory.
And as I said, 10! isn't that much, so you can just do them serially (or stop at the first solution). I wouldn't suggest this method for N > 14 though (which is the practical limit of my computer, at least in similar problems).
Title: Re: Unit Interval Bins
Post by Sameer on Feb 2nd, 2004, 12:09pm
All this time I have been trying non-brute force. Will keep on trying!!  :P
Title: Re: Unit Interval Bins
Post by towr on Feb 2nd, 2004, 3:49pm
Well, non-brute force.. heuristicly it might be an idea to keep each interval, or the conjunction of all intervals, as large as posisble
starting with [1,2] the 3 should go in the middle as each then has 1/3rd, then thr 4th would go between 3&2 (or 1&3), so 1&2 still have a whole quarter, and 3 has 1/6th and 4 1/4th
If we then put 5 between 1&3 just 1/10th of the total is lost (between 3 and 4), so we can put the 6 there. etc

eventually we might get to [1,9,5,7,3,6,10,4,8,2] (which is a permutation that gives a solution)..
might just be coincidence though.
An algorithm based on this, if it works, would be O(n2), I think.. As you have to find the best place to put the next ai interval, and if you've placed k in the previous steps there are k+1 places to put the next one.
Title: Re: Unit Interval Bins
Post by eliza on Feb 2nd, 2004, 3:59pm
Interesting problme. You don't actually have to check 10! possible arrangements. Consider the points chosen in pairs that must stay balanced. Whenever there's an even number of points, half must fall below .5 and half above.Also, although other solutions are possible, if you only want to find a solution, any solution, you don't need to consider any scenario except where a1 is in the first tenth and a10 is in the last tenth. And because all solutions will have symmetric alternates, you don't need to consider any except where .333<a3<.5, and .5<a4<.75.
Working by hand, I found a5 could be placed in the 2nd, 3rd, or 4th fifth, but the middle insertion becomes pointless after adding a6 (it's possible, but it just unnecessarily restricts your options for further growth).
So a6 only has 2 scenarios you need to consider: 153462 and 163452. Adding a7 has only 10 scenarios you need to consider. The 8th point gives you 36 scenarios, ignoring the unbalanced ones. The numbers skyrocket after that. Although I don't have time right now, the way I'd solve it by hand from this point is to write in a column all the dividing points (.1, .111, .125, .143...) and choose one of the a6 options to write next to it. It shouldn't be too hard to figure out how to squeeze in just 2 more numbers in the top half and 2 in the bottom.
Title: Re: Unit Interval Bins
Post by eliza on Feb 2nd, 2004, 4:06pm
I could also add that every 3 elements you add, one must go in each third. Every 4 elements, one must go in each quarter, so this pattern will greatly restrict the possible permutations.
Title: Re: Unit Interval Bins
Post by John_Gaughan on Feb 2nd, 2004, 10:00pm

on 02/02/04 at 11:47:26, towr wrote:
You don't have to first generate each permutation, and then check them all. You can do it while you're generating them, and forget about all those that don't work, and drop those that do work to the output. This way it only costs O(1) memory.

But the time depends on the input, so it cannot be O(1). For large N you have more permutations, even if you do not have to check them all.
Title: Re: Unit Interval Bins
Post by towr on Feb 3rd, 2004, 12:44am

on 02/02/04 at 22:00:30, John_Gaughan wrote:
But the time depends on the input, so it cannot be O(1). For large N you have more permutations, even if you do not have to check them all.
memory isn't time, and I said memory was O(1), but ok, it is actually O(N), it's just in comparison to N! that hardly makes a difference..

But you could also do it a little less brutely. Iteratively add 1 more interval in each cycle, and throw out any permutation that no longer fits. Queuing every possibility you get 3968 permutations at iteration 10, which isn't bad memory-wise. And computation should be much faster.
Title: Re: Unit Interval Bins
Post by John_Gaughan on Feb 3rd, 2004, 10:56am
Sorry, I wasn't clear about the fact you were talking about memory and not time. It makes sense now.
Title: Re: Unit Interval Bins
Post by Barukh on Mar 13th, 2004, 7:17am
An answer to 2: N=17 is maximum.

This problem was proposed by a Polish mathematician Hugo Steinhaus some 40 years ago. His compatriot M. Warmus gave an elementary proof that 18 numbers don't exist several years later.

If somebody is interested, I can try to reproduce this proof.
Title: Re: Unit Interval Bins
Post by Sameer on Mar 13th, 2004, 12:44pm

on 03/13/04 at 07:17:31, Barukh wrote:
If somebody is interested, I can try to reproduce this proof.


Do you really need to ask this question??  ::)
Title: Re: Unit Interval Bins
Post by Barukh on Mar 16th, 2004, 4:13am

on 03/13/04 at 12:44:19, Sameer wrote:
Do you really need to ask this question??  ::)

Yes, I think I do. But it seems you expressed the interest in a nice way :D

Here’s how Warmus proved that there do not exist 18 numbers a1, …, a18 that satisfy the conditions of the problem.

Let ank be the number that lies in the interval [ (k-1)/n, k/n ), n = 1, …,  18; k = 1, …, n. The idea of the proof is to show that there always exist n, k such that ank = ank+1, a contradiction.

Consider all possible cases for a95. By definition, it lies in the range [4/9, 5/9), and by symmetry it’s sufficient to examine just the half of it. Warmus examines separately the following ranges of a95: (A) [4/9, 5/11);  (B) [5/11, 6/13);  (C) [6/13, 7/15); (D) [7/15, 8/17);  (E) [8/17, 1/2);  (F)  1/2.

Take, for instance, case (A). We have a95 = a115 = a147 = a157 = a168 = a178, because all these intervals cover [4/9, 5/11). It is also not difficult to get convinced that then  a94 = a146 = a156 = a167 = a177. The intersection of all these intervals is [3/8, 2/5), which completely covers the interval for a115. Therefore, a94 = a115 = a95, which is impossible.

It is interesting that the above reasoning does not use the 18-th element at all. The only case where this information is used is (B).

For the interested: reconstruct the proof for other cases  ;)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board