wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> Line Segments in a Square
(Message started by: cool_joh on Jul 5th, 2008, 7:41pm)

Title: Line Segments in a Square
Post by cool_joh on Jul 5th, 2008, 7:41pm
A finite set of line segments (each including its endpoints) of total length 18 is placed on a square of side 1 (the square includes the boundary and the interior). Each segment is parallel to one of the sides and does not extend beyond the boundary of the square. Show that the lines divide the square into regions one of which has area at least 1/100.

Title: Re: Line Segments in a Square
Post by towr on Jul 6th, 2008, 7:11am
I don't see any reason why the line-segments would have to divide the square at all.
For example, you can have 36 parallel pieces 0.5 units long spaced 0.02 units apart, somewhere in the middle of the square.

Title: Re: Line Segments in a Square
Post by cool_joh on Jul 6th, 2008, 7:14am
In that case, I think the region is the whole square, whose area is 1 > 1/100.  ;D

Title: Re: Line Segments in a Square
Post by NightBreeze on Jul 6th, 2008, 8:59am
Indeed. The problem is to proof that for every possible division, there is a part of the square whose area is > 1/100

Edit: the inequality can't be strict. Since 9 horizontal and 9 vertical lines, equally spaced apart will divide the square into 100 parts of equal surface.

Title: Re: Line Segments in a Square
Post by Grimbal on Jul 6th, 2008, 12:20pm
[hide]Suppose we manage to create a division where all areas are <1/100 unit.

The total perimeter of the regions equals the perimeter of the square plus twice the lines dividing the square (twice because they contribute on both sides).  So the total perimeter is
   P = 4 + 2·18 = 40

Since all lines are horizontal and vertical, the minimum perimeter for one region of area ai is achieved with a square, where the perimeter is 4·sqrt(ai).  So
   pi >= 4·sqrt(ai)

Since ai<1/100 for all regions, we have
   pi >= 4·sqrt(ai) = 4·ai/sqrt(ai) > 4·ai/sqrt(1/100) = 40·ai.
   pi > 40·ai.

Since the total perimeter P=sum(pi) and the total area A = sum(ai), we have
   P > 40·A
But A = 1 and P = 40, so we have a contradiction.[/hide]



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