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

        riddles >> hard >> Digging wells Read the full problem to understand
        
(Message started by: hoogle on Oct 10th, 2008, 11:23am)
Title: Digging wells Read the full problem to understand
Post by hoogle on Oct 10th, 2008, 11:23am
Consider the following process, which goes on in stages:
A community is building a series of wells, trying to space them to meet the growing demand. Whenever a new family joins the community, the other families move a bit to make room for the new one, and everyone ends up with the same amount of room. Fortunately, they all live on the open interval (0,1). Unfortunately, the wells can't move.
Initially there is no well. At each stage i, i=1,2, . . .   the ith family arrives and a new well is drilled at a point from the open unit interval   (0, 1),  so that there will be i wells. The goal is to insure that after the new well is drilled, each of the i open subintervals   (0, 1/i),   (1/i, 2/i),   . . .,   ((i-1)/i, 1)   contains exactly one well.

For example, suppose the following choices were made.

Stage 1: first well is drilled at 0.7. Then certainly the interval   (0, 1)  , corresponding to a single family being in the community, has a well.
Stage 2: a second family arrives, and a second well is drilled at 0.3. Now each of   (0, 1/2)   and   (1/2, 1)   has a well.
Stage 3: third well is drilled at 0.4. Now each of the three families, residing in   (0, 1/3),   (1/3, 2/3), and   (2/3, 1)  , has a well.
Stage 4: Oops, there is no place to correctly drill the fourth well, because   (1/4, 2/4)   already has two wells and hence no matter where the fourth well is placed, one family will be without a well.
However, if the second well had been put at 0.2, then it would have been possible to complete the fourth stage.
Can this process go on forever?

If it can go on forever, then how should the locations be chosen? (There may not be a unique answer.)

If it cannot go on forever, what is the longest it can go?
Title: Re: Digging wells Read the full problem to underst
Post by SMQ on Oct 10th, 2008, 11:54am
I'm not sure whether this is hard or medium, but it certainly fits better here than CS (as there's nothing inherently computer related about it).  In the future, please don't post the same problem to multiple forums.  Thanks.

--SMQ
Title: Re: Digging wells Read the full problem to underst
Post by towr on Oct 10th, 2008, 2:09pm

on 10/10/08 at 11:23:35, hoogle wrote:
Can this process go on forever?
[..]
If it cannot go on forever, what is the longest it can go?
I suspect it can't go on forever, but can go on arbitrarily long.

Of course at this point it's little more than intuition; and that can go horribly awry in maths. But I think there's a problem getting wells in the far ends, i.e. (0..1/n) and (1-1/n..1)
Title: Re: Digging wells Read the full problem to underst
Post by hoogle on Oct 10th, 2008, 9:22pm
@towr: can you explain how it can go on arbitrarily long..How do you select the well positions
Title: Re: Digging wells Read the full problem to underst
Post by towr on Oct 11th, 2008, 4:58am

on 10/10/08 at 21:22:07, hoogle wrote:
@towr: can you explain how it can go on arbitrarily long..How do you select the well positions
It's just a suspicion at this point. But I think you can work backwards. I'd have to try it for a few cases to see if I can find a (usable) pattern first.
Title: Re: Digging wells Read the full problem to underst
Post by tohuvabohu on Oct 11th, 2008, 9:51am
I think the solution is to think in ranges rather than specific locations for the wells.
Start with a well at .01 and then one at .99.
Then each time you add a well you add it to whichever new region has no well, and further restrict the previous ranges to prevent any from incroaching on multiple subdivisions. Like this:

Well 3
.333-.666

Well 3 and 4
.333-.5
.5-.75

Wells 3, 4 and 5
.4-.5
.6-.75
.2-.333

Wells 3,4,5 and 6
.4-.5
.6-.666
.2-.333
.666-.833

Wells 3-7
.428-.5
.6-.666
.2-.2857
.71-.833
.285-.428

Wells 3-8
.428-.5
.625-.666
.2-.25
.75-.833
.285-.375
.5-.625

So you need to know the maximum number of citizens before you dig the first well.
I haven't attempted to see how far this method will go, or tried to check whether the choices I made were the only possibility, but it wouldn't be too hard to write a computer program that extends the method and tries all possible range restrictions.
Title: Re: Digging wells Read the full problem to underst
Post by rmsgrey on Oct 12th, 2008, 6:44am

on 10/11/08 at 09:51:33, tohuvabohu wrote:
I think the solution is to think in ranges rather than specific locations for the wells.
Start with a well at .01 and then one at .99.
Then each time you add a well you add it to whichever new region has no well, and further restrict the previous ranges to prevent any from incroaching on multiple subdivisions. Like this:

Well 3
.333-.666

Well 3 and 4
.333-.5
.5-.75

Wells 3, 4 and 5
.333-.5
.5-.75
.2-.333


You need to further restrict the first two ranges for the fifth well, giving:

.4-.5
.6-.75
.2-.333
Title: Re: Digging wells Read the full problem to underst
Post by tohuvabohu on Oct 12th, 2008, 1:29pm
You're right. I actually had it right on paper, but my scribblings were getting illegible so I refigured the numbers on the fly, and I was in a hurry. Everything is wrong after that mistake. I've edited it to maybe correct everything, maybe.
Title: Re: Digging wells Read the full problem to underst
Post by towr on Oct 13th, 2008, 4:14am
Unless I botched up my program (which is entirely possible, since it a major hack job); there's no solution for 18.
17 is the last one I get solutions for.

Number of solutions:
1: 1  
2: 2  
3: 6  
4: 16  
5: 64  
6: 128  
7: 512  
8: 1024  
9: 2624  		10: 3968  
11: 11392  
12: 7168  
13: 17920  
14: 11776  
15: 8064  
16: 4608  
17: 1536
18: 0

[edit]
One of the solutions  for 17 (and therefore anything before)

position of new well:
1,  1,  1,  3,  2,  4,  1,  7,  4,  7,  3,  10, 7,  1,  14,  6,  11

well-number, and interval where it should be struck.
#14  (0 .. 1/17)
#7   (1/14 .. 1/13)
#3   (1/7 .. 2/13)
#11  (3/14 .. 3/13)
#5   (2/7 .. 5/17)
#16  (5/16 .. 6/17)
#9   (3/8 .. 5/13)
#2   (5/11 .. 6/13)
#13  (1/2 .. 9/17)
#6   (4/7 .. 7/12)
#17  (10/17 .. 11/17)
#10  (11/17 .. 2/3)
#4   (8/11  .. 11/15)
#12  (11/14  .. 4/5)
#8   (6/7 .. 13/15)
#15  (15/17 .. 14/15)
#1   (16/17 .. 1)
[/edit]

[edit2]added pdf-graphic of solution[/edit2]
Title: Re: Digging wells Read the full problem to underst
Post by hoogle on Oct 13th, 2008, 8:59am
@towr

can you explain how your program works......how were you able to conclude that there will be no  more than 17 wells.............
Title: Re: Digging wells Read the full problem to underst
Post by towr on Oct 13th, 2008, 9:47am

on 10/13/08 at 08:59:07, hoogle wrote:
can you explain how your program works......how were you able to conclude that there will be no  more than 17 wells.............
I start with an interval (0..1),
And then at each step n decide in which interval (i/n..(i+1)/n) the next well will come, and how that affects the intervals in the previous step.

For example in step two, I can pick interval (0..1/2) or (1/2..1); and every interval I have so far will have to be clipped at the edges of the 1/n-length pieces. If an interval becomes empty the candidate solution is invalid (because there would be no place to put the well any longer).

So really, it is just a matter of finding the insertion order of wells. An O(n!) problem, save for the fact you quickly eliminate many paths.
So given that this should find a solution if there were one for 18 wells; and given that I didn't find one; I can conclude there isn't one. (But it might be prudent if someone independently checks this; because, as I said, the program is a bit of mess.)
Title: Re: Digging wells Read the full problem to underst
Post by SMQ on Oct 13th, 2008, 10:56am

on 10/13/08 at 09:47:30, towr wrote:
(But it might be prudent if someone independently checks this; because, as I said, the program is a bit of mess.)

I started working on essentially the same program Friday evening, but got distracted by real life...  I should be able to verify/refute your results in a little while here.

Edit: I get the same results as towr.

#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long uint32;
typedef unsigned long long uint64;
typedef pair<uint32, uint32> rational;
typedef pair<rational, rational> interval;
typedef vector<interval> intvec;
typedef vector<intvec> vecvec;

bool operator < (const rational & x, const rational & y) {
 return (uint64)(x.first)*y.second < (uint64)(x.second) * y.first;
}

int main(void) {
 intvec s;
s.push_back(interval(rational(0, 1), rational(1,1)));
 vecvec v; v.push_back(s);
 uint32 n = 1;

 while (!v.empty()) {
   cout << n << ": " << v.size() << endl;
   ++n;
   vecvec u;
   // for each solution to n-1 wells
   for(vecvec::const_iterator it = v.begin(); it != v.end(); ++it) {
      // for 0 <= i < n, place new well in interval (i/n, i+1/n)
      for(uint32 i = 0; i < n; ++i) {
        intvec s; bool ok = true;
        // find intersections of pervious placements with intervals < i
        for(uint32 j = 0; j < i; ++j) {
          rational a0(j, n), a1(j+1, n);
          rational start = a0 < (*it)[j].first ? (*it)[j].first : a0;
          rational end = (*it)[j].second < a1 ? (*it)[j].second : a1;
          if (start < end) s.push_back(interval(start, end)); else ok = false;
        }
        // place interval i
        s.push_back(interval(rational(i, n), rational(i+1, n)));
        // find intersections of pervious placements with intervals > i
        for(uint32 k = i; k+1 < n; ++k) {
          rational a0(k+1, n), a1(k+2, n);
          rational start = a0 < (*it)[k].first ? (*it)[k].first : a0;
          rational end = (*it)[k].second < a1 ? (*it)[k].second : a1;
          if (start < end) s.push_back(interval(start, end)); else ok = false;
        }
        // if all intersections ok, store new solution for n wells
        if (ok) u.push_back(s);
      }
   }
   v = u;
 }

 cout << n << ": 0" << endl;
 return 0;
}

--SMQ
Title: Re: Digging wells Read the full problem to underst
Post by Barukh on Oct 15th, 2008, 2:28am

on 10/13/08 at 04:14:39, towr wrote:
Unless I botched up my program (which is entirely possible, since it a major hack job); there's no solution for 18.
17 is the last one I get solutions for.

You are right (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1075464786).


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