Question on a problem - Any solutions?

[Ben1587]

The problem:
Given N distinct points in the unit square [0,1]x[0,1], including the origin (0,0) as one of the N points. Can you construct N rectangles, contained in the unit square, with sides parallel to the coordinate axes, pairwise non-intersecting, such that each of our N given points is the lower-left-hand corner of one of the rectangles, and such that the total area of the rectangles is at least 1/2?

Question: either prove that such a construction is always possible, or give a set of N distinct points (including the origin) for which it is impossible.

Thanks

 

[AKG]

I don't know if this proof is rigourous enough, but you may want to consider this idea: assume that we can choose N points such that the area formed by those rectangles < 1/2. This means there's a remaining uncovered area > 1/2. All we would have to do is to change the direction of these triangles to take up that uncovered area instead, and I think it would have to take up over 1/2 then. For example, imagine the points are (0,0), (0.2,0.1), (0.3,0.2), (0.4,0.3), ..., (0.9,0.8). Each rectangle will go up 0.1, and across all the way, except for the last one, which will go up 0.2. The total area here will be:

0.1 + 0.1(0.8) + 0.1(0.7) + ... + 0.1(0.2) + 0.2(0.1) = 0.47 < 1/2

Now, instead, make the rectangles (except for the last one) go all the way to the top (instead of all the way to the right) and the area will be:

0.1 + 0.1(0.9) + 0.1(0.8) + ... + 0.1(0.3) + 0.1(0.2) = 0.54 > 1/2

Now it won't always be possible to always cover all the uncovered spots, but I think if you have less than half, you'll always be able to adjust some rectangles to have more than they used to. Of course, this isn't really all that convincing, but it might help?

 

[matt grime]

This seems very easy r so where am I going wrong:

let the n points be labelled them 1,2,3...n in increasing order of the x coorindates (assume these x coordinates are distinct*), any any points will do. for the point labelled r, construct the rectangle of base 2/3 the distance (or any proportion greater then 1/2) from point r to point r+1's x coordinate (where point n+1 we define to be 1) and of height 1. the rectangles then cover 2/3 of the area.

* If there are points with equal x cooridinates, there is an easy way to generalize this idea, but it's quite tedious, since one may cover arbitrarily large (well, still less than 1 unit area) parts of the square using the argument above.

 

[AKG]

This seems very easy r so where am I going wrong:

let the n points be labelled them 1,2,3...n in increasing order of the x coorindates (assume these x coordinates are distinct*), any any points will do. for the point labelled r, construct the rectangle of base 2/3 the distance (or any proportion greater then 1/2) from point r to point r+1's x coordinate (where point n+1 we define to be 1) and of height 1. the rectangles then cover 2/3 of the area.

You can't always choose a height of 1. If the point, for example, is (1/2, 3/4), it can have a maximum height of 1/4.

 

[matt grime]

Yes, thanks, this is because I misread the question and started out with a counter example realized that was wrong and tried to change it. Knew it was wrong somewhere.

 

[Gokul43201]

But a modification of matt's idea will work.

Choose the length of each base to be infinitesimally smaller than the difference in x-coordinates between the r'th and r+1'th points.
(just changing matt's 2/3 to $$1- \delta$$)

If y(r) > 0.5, make the rectangle go downwards with height just smaller than y. If not, draw the rectangle upwards with height just smaller than 1- y(r).

$$2N\delta$$ can always be chosen to be smaller than $$\sum |~y(r)- 0.5~|$$ unless y(r) = 0.5 for all r in [1,N]. And since we are told that one of the points is at (0,0), we are safe.

 

[AKG]

If y(r) > 0.5, make the rectangle go downwards with height just smaller than y. If not, draw the rectangle upwards with height just smaller than 1- y(r).

What does this mean? Keep in mind that the N points are each to be the bottom-left corner of the rectangles (so if "making the rectangle go downwards" means what I think it means, it's not an admissible approach).

 

[Gokul43201]

Oops, missed that detail.

 

[Gokul43201]

Okay, can you not construct the unit square itself from the point at (0,0), and the rest is immaterial (or let's say 'infinitesimal', to complete the construction) ? Surely, I'm making a mistake somewhere...again !

 

[Wong]

The question sounds easy. I don't get what the difficulty is.

Given N pts, you just try to draws a "system of grid lines". (i.e. for each pt, try to draw a vertical and horizontal line through the pt, making a "cross"). Then in this grid system, each pt (call it pt i)is the lower left corner of a rectangle (call it rectangle A_i). Choose a rectangle of whatever size contained in A_i, and containing the pt i, to satisfy the condition area<0.5.

 

[Wong]

Oops~~sorry. I misread the question. The area should be greater than 0.5...

But if the unit square is closed then for pts on {1}x[0,1] and [0,1]x{1} we should *not* be able to find such a rectangle satisfying the conditions, unless you count "degenerate" rectangles (i.e. {y}x{y}). In this case, if I choose the N pts to be all lying on the aforementions "boundaries", then the propostion is disproofed.

 

[Wong]

Oops sorry that is wrong too... because I have to include the origin...

 

[michka]

The problem:
Given N distinct points in the unit square [0,1]x[0,1], including the origin (0,0) as one of the N points. Can you construct N rectangles, contained in the unit square, with sides parallel to the coordinate axes, pairwise non-intersecting, such that each of our N given points is the lower-left-hand corner of one of the rectangles, and such that the total area of the rectangles is at least 1/2?

Question: either prove that such a construction is always possible, or give a set of N distinct points (including the origin) for which it is impossible.

Thanks

Counterexample: N=2, the points: (1/3, 1/3) and (2/3, 2/3). There total are of the two possible rectangles is 2/9.