Author |
Topic: Unit Interval Bins (Read 2246 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Unit Interval Bins
« on: Jan 30th, 2004, 4:13am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: Unit Interval Bins
« Reply #1 on: Jan 30th, 2004, 5:56am » |
Quote Modify
|
1. I believe this is possible.
::
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
::
2. I suspect that :: for all N [subset] [smiley=bbz.gif], N [smiley=ge.gif] 1 :: I think mathematical induction can prove this, I'll see if I can come up with a proof.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Unit Interval Bins
« Reply #2 on: Jan 30th, 2004, 6:05am » |
Quote Modify
|
Ah crap, I just answered the wrong question. Back to the drawing board...
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Unit Interval Bins
« Reply #3 on: Jan 30th, 2004, 10:23am » |
Quote Modify
|
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...
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Unit Interval Bins
« Reply #4 on: Jan 30th, 2004, 10:56am » |
Quote Modify
|
on Jan 30th, 2004, 10:23am, 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:
::
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
::
edit: changed wording to be more clear
|
| « Last Edit: Jan 30th, 2004, 10:58am by John_Gaughan » |
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Unit Interval Bins
« Reply #5 on: Jan 31st, 2004, 10:22am » |
Quote Modify
|
on Jan 30th, 2004, 10:56am, John_Gaughan wrote:| I think I found the solution: |
|
Nice try, John, but unfortunately it doesn't work. For instance, a3, a4 are both in [0.4, 0.6] which is a single bin when divinding the interval into 5 pieces. 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Unit Interval Bins
« Reply #6 on: Feb 1st, 2004, 9:13am » |
Quote Modify
|
I think I found a solution, or rather 3968 
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] )
|
| « Last Edit: Feb 1st, 2004, 9:54am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Unit Interval Bins
« Reply #7 on: Feb 2nd, 2004, 8:38am » |
Quote Modify
|
What method did you use? 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Unit Interval Bins
« Reply #8 on: Feb 2nd, 2004, 9:05am » |
Quote Modify
|
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..
|
| « Last Edit: Feb 2nd, 2004, 9:13am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Unit Interval Bins
« Reply #9 on: Feb 2nd, 2004, 11:13am » |
Quote Modify
|
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?
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Unit Interval Bins
« Reply #10 on: Feb 2nd, 2004, 11:47am » |
Quote Modify
|
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).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Unit Interval Bins
« Reply #11 on: Feb 2nd, 2004, 12:09pm » |
Quote Modify
|
All this time I have been trying non-brute force. Will keep on trying!!
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Unit Interval Bins
« Reply #12 on: Feb 2nd, 2004, 3:49pm » |
Quote Modify
|
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.
|
| « Last Edit: Feb 2nd, 2004, 3:50pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
eliza
Guest
|
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.
|
|
IP Logged |
|
|
|
eliza
Guest
|
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.
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Unit Interval Bins
« Reply #15 on: Feb 2nd, 2004, 10:00pm » |
Quote Modify
|
on Feb 2nd, 2004, 11:47am, 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.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Unit Interval Bins
« Reply #16 on: Feb 3rd, 2004, 12:44am » |
Quote Modify
|
on Feb 2nd, 2004, 10:00pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Unit Interval Bins
« Reply #17 on: Feb 3rd, 2004, 10:56am » |
Quote Modify
|
Sorry, I wasn't clear about the fact you were talking about memory and not time. It makes sense now.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Unit Interval Bins
« Reply #18 on: Mar 13th, 2004, 7:17am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Unit Interval Bins
« Reply #19 on: Mar 13th, 2004, 12:44pm » |
Quote Modify
|
on Mar 13th, 2004, 7:17am, Barukh wrote:
If somebody is interested, I can try to reproduce this proof. |
|
Do you really need to ask this question?? 
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Unit Interval Bins
« Reply #20 on: Mar 16th, 2004, 4:13am » |
Quote Modify
|
on Mar 13th, 2004, 12:44pm, 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 
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 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove