Square with side 100 was cut by 99 horizontal and 99 vertical lines into 10000 rectangles (not necessarily with integer sides). How many rectangles in this square with area not exceeding 1 at least can be?
Problem
Source: Saints Petersburg Olympiad 2015
Tags: rectangle, combinatorics
09.07.2017 09:55
Do you mean the maximum or minimum number of such squares that we can obtain?
09.07.2017 10:50
I meant to find a square with min. number of rectangles with area <=1
10.07.2017 17:58
Lemma. If rectangle $S$ has side lengths $1-x,y$ so that $(1-x)y>1$ then $y>1+x$. Consider general case for $n \times n$ square. We prove that there are at least $n$ rectangles with area not exceeding $1$. Let $V,H$ be set of all vertical, horizontal side lengths of small rectangles respectively then $|V|=|H|=n$. In order not to have at least $n$ rectangles whose areas $ \le 1$, there exists at least one $1-a \in V, 0<a<1$ and one $1-b \in H, 0<b<1$. WLOG, $1>a>b$. Case 1. If there is only one $1-b \in H$ (i.e. only one horizontal side length $<1$). Consider row of $n$ rectangles whose vertical length is $1-a$. Let $y_1,y_2, \ldots, y_{n-1},y_n \; (y_n=1-b)$ be horizontal side length of such rectangles then $\sum_{i=1}^ny_i=n$ and $y_i \ge 1$ for all $i= 1, \ldots, n-1$ according to the assumption. If there exists $y_{n-1}$ so $y_{n-1}>1+a$. Hence, $$(n-2) \min_{1 \le i \le n-2} \{y_i \} +1+a+1-b<n \implies \min_{1 \le i \le n-2} \{ y_i \} < 1- \frac{a-b}{n-2}<1.$$This contradicts to assumption that $y_i \ge 1$ for all $i=1, \ldots, n-1$. This follows all $y_i \le 1+a$ for $i=1, \ldots, n-1$, which deduces all $n$ rectangles have areas $\le 1$ according to Lemma. Case 2. From case 1, we find that each $V,H$ has at least two side lengths that are less than $1$. From $V \cup H$, arrange all side lengths $<1$ in order $0<1-a \le 1-a_1 \le 1-a_2\le \ldots <1$. WLOG, $1-a \in V$. Let $n-m$ be number of horizontal side lengths $> 1+a$ then $m(1-a)+(n-m)(1+a) < \sum_{\ell \in H} \ell =n$ which follows $m>n/2$, i.e. there are at least $n/2$ horizontal side lengths $\le 1+a$. By considering row of rectangles whose vertical side length is $1-a$, then the row consists at least $n/2$ rectangles areas $\le (1-a)(1+a)<1$. If there is another vertical side length of $1-a$ then we are done. If not, all the rest $n-1$ vertical side lengths have length $\ge 1-a_1$. If there exists a horizontal side length $\le 1-a_1$ then with similar argument, we can find columns of rectangle whose horizontal side length is $1-a_1$ have at least $n/2$ rectangles whose areas $\le 1$ and can conclude. Next consider case for all $n-1$ horizontal side lengths (except for $1-a$) are $\ge 1-a_2$ and we keep going. Since we only have limited number of side lengths $<1$ so this process will end showing that there exists at least $n$ rectangles whose areas $\le 1$. Construction for $n$ rectangles can be followed from idea of case $1$: Pick one horizontal side length $\varepsilon$ very small, pick one vertical side length to be $0.99$. Others horizontal side lengths are the same and equal $\frac{n-\varepsilon}{n-1}$ which can give $\frac{n-\varepsilon}{n-1} \cdot 0.99>1$. Other vertical side lengths are the same and equal $\frac{n-0.99}{n-1}>1$. With this, only $n$ rectangles whose horizontal side length is $\varepsilon$ have area $\le 1$.
08.02.2021 04:17
Quote: Lemma. If rectangle $S$ has side lengths $1-x,y$ so that $(1-x)y>1$ then $y>1+x$. Consider general case for $n \times n$ square. We prove that there are at least $n$ rectangles with area not exceeding $1$. Let $V,H$ be set of all vertical, horizontal side lengths of small rectangles respectively then $|V|=|H|=n$. In order not to have at least $n$ rectangles whose areas $ \le 1$, there exists at least one $1-a \in V, 0<a<1$ and one $1-b \in H, 0<b<1$. WLOG, $1>a>b$. Case 1. If there is only one $1-b \in H$ (i.e. only one horizontal side length $<1$). Consider row of $n$ rectangles whose vertical length is $1-a$. Let $y_1,y_2, \ldots, y_{n-1},y_n \; (y_n=1-b)$ be horizontal side length of such rectangles then $\sum_{i=1}^ny_i=n$ and $y_i \ge 1$ for all $i= 1, \ldots, n-1$ according to the assumption. If there exists $y_{n-1}$ so $y_{n-1}>1+a$. Hence,$$(n-2) \min_{1 \le i \le n-2} \{y_i \} +1+a+1-b<n \implies \min_{1 \le i \le n-2} \{ y_i \} < 1- \frac{a-b}{n-2}<1.$$This contradicts to assumption that $y_i \ge 1$ for all $i=1, \ldots, n-1$. This follows all $y_i \le 1+a$ for $i=1, \ldots, n-1$, which deduces all $n$ rectangles have areas $\le 1$ according to Lemma. Case 2. From case 1, we find that each $V,H$ has at least two side lengths that are less than $1$. From $V \cup H$, arrange all side lengths $<1$ in order $0<1-a \le 1-a_1 \le 1-a_2\le \ldots <1$. WLOG, $1-a \in V$. Let $n-m$ be number of horizontal side lengths $> 1+a$ then $m(1-a)+(n-m)(1+a) < \sum_{\ell \in H} \ell =n$ which follows $m>n/2$, i.e. there are at least $n/2$ horizontal side lengths $\le 1+a$. By considering row of rectangles whose vertical side length is $1-a$, then the row consists at least $n/2$ rectangles areas $\le (1-a)(1+a)<1$. If there is another vertical side length of $1-a$ then we are done. If not, all the rest $n-1$ vertical side lengths have length $\ge 1-a_1$. If there exists a horizontal side length $\le 1-a_1$ then with similar argument, we can find columns of rectangle whose horizontal side length is $1-a_1$ have at least $n/2$ rectangles whose areas $\le 1$ and can conclude. Next consider case for all $n-1$ horizontal side lengths (except for $1-a$) are $\ge 1-a_2$ and we keep going. Since we only have limited number of side lengths $<1$ so this process will end showing that there exists at least $n$ rectangles whose areas $\le 1$. Construction for $n$ rectangles can be followed from idea of case $1$: Pick one horizontal side length $\varepsilon$ very small, pick one vertical side length to be $0.99$. Others horizontal side lengths are the same and equal $\frac{n-\varepsilon}{n-1}$ which can give $\frac{n-\varepsilon}{n-1} \cdot 0.99>1$. Other vertical side lengths are the same and equal $\frac{n-0.99}{n-1}>1$. With this, only $n$ rectangles whose horizontal side length is $\varepsilon$ have area $\le 1$. So what's the answer?