Author |
Topic: Digging wells Read the full problem to understand (Read 2807 times) |
|
howard roark
Full Member
Posts: 241
|
 |
Digging wells Read the full problem to understand
« on: Oct 10th, 2008, 11:23am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: Digging wells Read the full problem to underst
« Reply #1 on: Oct 10th, 2008, 11:54am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Digging wells Read the full problem to underst
« Reply #2 on: Oct 10th, 2008, 2:09pm » |
Quote Modify
|
on Oct 10th, 2008, 11:23am, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Digging wells Read the full problem to underst
« Reply #3 on: Oct 10th, 2008, 9:22pm » |
Quote Modify
|
@towr: can you explain how it can go on arbitrarily long..How do you select the well positions
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Digging wells Read the full problem to underst
« Reply #4 on: Oct 11th, 2008, 4:58am » |
Quote Modify
|
on Oct 10th, 2008, 9:22pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Digging wells Read the full problem to underst
« Reply #5 on: Oct 11th, 2008, 9:51am » |
Quote Modify
|
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.
|
| « Last Edit: Oct 12th, 2008, 1:35pm by tohuvabohu » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Digging wells Read the full problem to underst
« Reply #6 on: Oct 12th, 2008, 6:44am » |
Quote Modify
|
on Oct 11th, 2008, 9:51am, 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
|
|
IP Logged |
|
|
|
tohuvabohu
Junior Member
Gender:
Posts: 102
|
|
Re: Digging wells Read the full problem to underst
« Reply #7 on: Oct 12th, 2008, 1:29pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Digging wells Read the full problem to underst  wells17.pdf
« Reply #8 on: Oct 13th, 2008, 4:14am » |
Quote Modify
|
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]
|
| « Last Edit: Oct 13th, 2008, 12:17pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
howard roark
Full Member
Posts: 241
|
|
Re: Digging wells Read the full problem to underst
« Reply #9 on: Oct 13th, 2008, 8:59am » |
Quote Modify
|
@towr
can you explain how your program works......how were you able to conclude that there will be no more than 17 wells.............
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Digging wells Read the full problem to underst
« Reply #10 on: Oct 13th, 2008, 9:47am » |
Quote Modify
|
on Oct 13th, 2008, 8:59am, 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.)
|
| « Last Edit: Oct 13th, 2008, 9:57am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Digging wells Read the full problem to underst
« Reply #11 on: Oct 13th, 2008, 10:56am » |
Quote Modify
|
on Oct 13th, 2008, 9:47am, 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
|
| « Last Edit: Oct 13th, 2008, 11:55am by SMQ » |
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Digging wells Read the full problem to underst
« Reply #12 on: Oct 15th, 2008, 2:28am » |
Quote Modify
|
on Oct 13th, 2008, 4:14am, 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print