Proofs of Lemmas.

Proofs of Lemmas

by 'Literka'.

This page uses definitions of a page of 'Literka' monotonic subsequences. As we defined there P is a square [0,1] x [0,1]. Roughly speaking rectangle partition is a partition of unions of rectangles, but exact definition gives mentioned page of 'Literka'.

Lemma 1. Let f:[0,1] -> R be a step function with p values and

be intervals where f is constant. Assume that f(x) =

for

. Then there exist:

a rectangle partition U of P
partition of P into subsets
each is a union of sets of a rectangle partition U
area of (which is a sum of areas of rectangles) is equal to the length of
define a function h: P -> I = [0,1] by h(x,y)= for . Then
1. h(x1,y)>=h(x2,y) if x1>x2
2. h(x,y1)>=h(x,y2) if y2>y1

Proof. We'll demonstrate an example of construction of sets

for a specific step function. It will be easy generalize it. Probably much better explanation provides an applet of 'Literka' demonstration of a proof of Lemma 1. The example of a step function f: [0,1] -> R is given by

f(x)=7 for 0.15>x>=0
f(x)=8 for 0.6>x>=0.15
f(x)=5 for 0.8>x>=0.60
f(x)=9 for 0.87>x>=0.8
f(x)=6 for 1>x>=0.87

First step is to construct p sets so that only the last condition of Lemma 1 is not satisfied. It is easy - just take rectangles of one side equal 1 and another - length of interval

. Place them in the same order as in the function f. Following picture explains it better. To draw a picture of this partition assume that

color blue corresponds to the value 7
color violet corresponds to the value 8
color yellow corresponds to the value 5
color red corresponds to the value 9
color green corresponds to the value 6

Picture of our partition looks like this:
Rozmiar: 7697 bajtów

Choose the largest value from all values of the function f and the corresponding rectangle for this value. Place it on the top of all rectangles (changing size but keeping the same area), which are to the right. Place these rectangles (which are to the right) below, squeezing heights and expanding widths to maintain the same area as it is shown on the picture. Rectangle on the top will be later untouchable.
Rozmiar: 6152 bajtów

Forget about value we chose before and choose the largest value from values of function f, which are left. Take the rectangle corresponding to this value and as before, place it above all rectangles, which are to the right neglecting all rectangles chosen in previous steps. Later this rectangle will be untouchable.
Rozmiar: 5425 bajtów

Proceed with a construction obtaining the following partition:
Rozmiar: 5748 bajtów

This is a final partition for our example. Of course, Lemma 1 is satisfied for this partition.
It may not be so easy with other examples, but it is easy to fill the gaps. If you are not convinced that a similar process can be used for any case, visit an applet of 'Literka' demonstration of a proof of Lemma 1

Lemma 2. Let

be a partition of P and k=

. Assume that all elements

have equal areas (hence area must be 1/k for each

). Assume that every vertical or horizontal straight line crosses at most n sets from this partition. Then partition is a rectangle partition and all

are squares.

Proof. Let

be a projection of

on X- axis and

be a projection of

on Y-axis. Let

be a measure of

and

be a measure of

. Since

and area of

is 1/k, we have
Rozmiar: 2632 bajtów

which means that
Rozmiar: 2234 bajtów

.
Notice that these inequalities are sharp, if

is not a square.
Let us define functions r:[0,1] -> R and s:[0,1] ->R. Define r(t) to be the number of sets

such that

(t belongs to X-projection of

) , define a function s(t) to be the number of sets

such that

. We have

If not all

are squares than a sharp inequality holds, which means that r(t) or s(t) is bigger than n for some t from [0,1]. Since r(t) and s(t) are integers, this value must be at least n+1. This is what we wanted to prove.

Return to the list of pages of 'Literka' about polytopes.
Return to the main geometrical page of 'Literka'.
Return to the main page of 'Literka'.