We have a $10 \times 10$ table. $T$ is a set of rectangles with vertices from the table and sides parallel to the sides of the table such that no rectangle from the set is a subrectangle of another rectangle from the set. $t$ is the maximum number of elements of $T$. (a) Prove that $t>300$. (b) Prove that $t<600$. Proposed by Mir Omid Haji Mirsadeghi and Kasra Alishahi
Problem
Source: Iran 3rd round 2014 - Combinatorics exam problem 3
Tags: geometry, rectangle, combinatorics unsolved, combinatorics
28.09.2014 16:42
this problem proposed by Mir Omid Haji Mirsadeghi and Kasra Alishahi .
02.10.2014 09:37
If $T$ is the set of all rectangles with dimensions $1\times 6, 2\times 5, 3\times 4, 4\times 3, 5\times 2, 6\times 1$ then no rectangle is a subrectangle of another rectangle from the set. $T$ consists of $2(10\times 5 + 9\times 6 + 8\times 7)=320$ rectangles, so $t\geq 320>300$, proving the lower bound. Now consider an edge $E$ of the board. For each rectangle in $T$, let it's "base" be the side parallel to $E$ that is closest to $E$. We note that it is impossible for two rectangles to share the same base, otherwise one will be contained in the other. There are $(10+9+\cdots +1)\times 10=550$ possible bases, so $t\leq 550<600$, proving the upper bound. The upper bound is actually very weak and I have managed to prove that $t\leq 425$. It would be interesting to see if anyone can improve this bound (or the lower one), or even find the exact value of $t$.
03.06.2019 21:52
leminscate wrote: If $T$ is the set of all rectangles with dimensions $1\times 6, 2\times 5, 3\times 4, 4\times 3, 5\times 2, 6\times 1$ then no rectangle is a subrectangle of another rectangle from the set. $T$ consists of $2(10\times 5 + 9\times 6 + 8\times 7)=320$ rectangles, so $t\geq 320>300$, proving the lower bound. Now consider an edge $E$ of the board. For each rectangle in $T$, let it's "base" be the side parallel to $E$ that is closest to $E$. We note that it is impossible for two rectangles to share the same base, otherwise one will be contained in the other. There are $(10+9+\cdots +1)\times 10=550$ possible bases, so $t\leq 550<600$, proving the upper bound. The upper bound is actually very weak and I have managed to prove that $t\leq 425$. It would be interesting to see if anyone can improve this bound (or the lower one), or even find the exact value of $t$. Can you show your proof for upper bound?