Consider a rectangle $R$ partitioned into $2016$ smaller rectangles such that the sides of each smaller rectangle is parallel to one of the sides of the original rectangle. Call the corners of each rectangle a vertex. For any segment joining two vertices, call it basic if no other vertex lie on it. (The segments must be part of the partitioning.) Find the maximum/minimum possible number of basic segments over all possible partitions of $R$.
Problem
Source: China Mathematical Olympiad 2017 Q3
Tags: rectangle, combinatorial geometry, combinatorics, China
25.11.2016 14:23
29.08.2020 11:12
Let $E$ be the number of basic segments. We claim $4122 \le E\le 6049$. Let $N=2016$. Let $n_i$ be the number of vertices with $i$ edges coming out. Note that $n_2=4$. Part 1: Maximum. We double-count certain quantities to get equations in terms of the $n_i$'s. $2n_2+3n_3+4n_4=2E$. The LHS counts the total number of edges coming out of each vertex, and each basic segment has two endpoints. $n_2+2n_3+4n_4=4N$. Each $n_2$ vertex is a corner of 1 rectangle, each $n_3$ is a corner of 2 rectangles, and each $n_4$ vertex is a corner of 4 rectangles. There are a total of $N$ rectangles, and each is counted once each of the 4 corners. Note that $2n_3=4N-4-4n_4$, so $n_3 \le 2N-2$, with equality at $n_4=0$. Also note that $n_3+2n_4=2N-2$. Now, \begin{align*} E &=4+\tfrac32 n_3 + 2n_4 = 4+(2N-2) + \tfrac12 n_3 \\ &\le 4+(2N-2) + \tfrac12 (2N-2) = 3N+1=6049. \end{align*}We can achieve equality by splitting into $N=2016$ congruent side-by-side rectangles. Note that $n_4=0$ in this construction, as expected. Part 2: Minimum. For each $n_3$ vertex, launch an edge in the one barren direction till it hits a side of $R$. Doing this induces a grid structure; $R$ is now split into an $a\times b$ grid for some $a,b$. We make some weak bounds motivated by (and tight at) the equality case of an initial grid splitting: $ab\ge N$. No old rectangles are destroyed, and possibly new ones are created. $2a+2b \le 4+n_3$. The total number of points on the sides of $R$ where a line touches is $2a+2b$. Out of the old points that lied on the sides of $R$, the 4 corners are $n_2$'s and the rest are $n_3$'s. We know from before $E = 2N+2 + \tfrac12 n_3$. So \begin{align*} E&\ge 2N+2 + \tfrac12 (2a+2b-4) \\ &\ge 2N+2 + \tfrac12 (2a + 2N/a - 4) \\ &= 2N + a + \tfrac{N}{a}. \end{align*}This is maximized when $a\mid 2016$ is closest to $\sqrt{2016}$, i.e. at $a=42$. The minimum is then $2\cdot 2016 + 42 + 48 = 4122$, as claimed.
25.09.2020 10:09
Notice that a vertex (not including the four corners of $R$) can be the corner of either four or two different small rectangles. In the first case, it is incident to exactly four basic segments, and in the second case it is incident to exactly three basic segments. Let $a$ be the number of vertices in the first case and $b$ be the number of vertices in the second case. Then by the above we have \[S = \#(\text{segments}) = \frac12(4a + 3b + 2\cdot 4)\]and \[4\cdot 2016 = 4a + 2b + 1\cdot 4\]so we get $b=2(2015-a)$ and $S = 6049 - a$. Clearly $a\ge 0$ so $S\le 6049$, and equality can be achieved by, for example, all vertical stripes. To find the minimum, we want to maximize $a$, that is to minimize $b$. Let $x$ be the number of lines in the partition in the vertical direction (not including the sides of $R$), and let $y$ be the number of lines in the horizontal direction (not including the sides of $R$). Claim. $b \ge 2(x+y)$. Proof. Consider the two endpoints of each line. Each must be a vertex that lies in the interior of some basic segment. On the other hand, $(x+1)(y+1) \ge 2016$ by extending all lines until they reach the edges of $R$. So $b+4\ge 2(x+y+2) \ge 4\sqrt{2016}$, which means that $S \ge 4032 + 2\sqrt{2016} = 4122$. Equality happens when $R$ is divided into $42\times 48$ grids.
02.01.2021 04:03
$\textbf{Maximum:}$ The idea is to double count using the setup of the number of edges emanating from each vertex (up, down, left, right). Let an $\textit{i-vertex}$ denote a vertex with $i$ edges emanating from it, and let $n_1$, $n_2$, $n_3$, $n_4$ be the counts of these respectively. Evidently $n_1 = 0$ because no duh. Additionally, $n_2 = 4$ because 2-vertices other than the primary corners contradicts the fact that we need rectangular areas. Additionally, it is obvious that 4-vertices cannot lie on the sidelines. The key double counts are: \begin{align*} 4 \cdot [ \text{rectangles} ] &= 4 + 2n_3 + 4n_4 \\ 2 \cdot [ \text{basic edges} ] &= 4 \cdot 2 + 3n_3 + 4n_4. \end{align*}The first one comes from double counting the corners using the observation that 2-vertices act as the corner for one rectangle, 3-vertices for two rectangles, and 4-vertices for four rectangles. The second one comes from simply double counting the edges. Now we can simply algmanip to get the desired maximum: \begin{align*} [ \text{basic} ] &= \frac{4 + (4 + 2n_3 + 4n_4) + n_3}{2} \\ &= \frac{4 + 4 \cdot 2016 + 2 \cdot 2016 - 2 - 2n_4}{2} \\ &= 6049 - n_4 \\ &\leq 6049, \end{align*}which is achieved by just having a rectangle and then doing a ton of parallel horizontal lines with no vertical ones. $\square$ $\textbf{Minimum:}$ We will delve a little deeper into the double count as follows: Let $a$ be the number of distinct x coordinates that appear amongst the vertices disregarding sidelines, and $b$ the number of distinct y coordinates that appear amongst the vertices also disregarding sidelines. Additionally, let $x_1, x_2, \cdots, x_a$ be the counts for the number of 4-vertices that appear in each x coordinate, and define $y_1, y_2, \cdots, y_b$ similarly. The key observation is that at the highest and lowest points at each x coordinate (vice versa for y), there must be a 3-vertex. This is simply because if there's a 4-vertex, then we can extend our path further which contradicts max/minimality. Thus, we get the following relations: \begin{align*} 2n_4 &= x_1 + x_2 + \cdots + x_a + y_1 + \cdots + y_b \\ n_3 &\geq 2a + 2b. \end{align*} Now we once again algmanip to finish. We have \begin{align*} n_3 = 4030 - 2n_4 &\geq 2a + 2b \implies \\ 2015 &\geq a + b + n_4 \\ &= a + b + \frac{x_1 + \cdots + x_a + y_1 + \cdots + y_b}{2}. \end{align*}Noting that each $x_i$ has maximum $b$, and each $y_i$ has maximum $a$, we see that $a + b$ is minimized when we have $a$ and $b$ pushed together. In other words, $ab + a + b = 2015$, which has the solution $a = 41$, $b = 47$. To finish, calculate \begin{align*} [\text{basic}] &= \frac{8 + 3n_3 + 8060 - 2n_3}{2} \\ &= 4034 + \frac{n_3}{2} \\ &\geq 4034 + a + b \\ &\geq 4122. \end{align*}Equality holds when we have a $42$ by $48$ grid.
02.09.2021 16:30
The maximum value is $3\times 2016+1=6049$, achieved when the rectangle is partitioned into a $2016\times 1$ chessboard. We prove the bound. We define a vertex to be Class A,B,C if it has two, three and four basic segments connected to it respectively. Class A vertices are the four corners of $R$. Let $v_1,v_2$ be the number of Class $B$ and $C$ vertices. Notice that each Class $A$ vertex is a vertex of one rectangle, Class $B$ vertex is a vertex of two rectangles and a Class $C$ vertex is a vertex of four rectangles. Therefore, by a simple double counting, $$4+2v_1+4v_2=2016\times 4\hspace{20pt}(1)$$$$8+3v_1+4v_2=2S\hspace{20pt}(2)$$Hence $$2S=2016\times 4+4+4v_1\leq 2016\times 4+4+2015\times 2=2016\times 6+2$$as desired. The minimum value is $4122$, achieved when the rectangle is partitioned into a $42\times 48$ chessboard. Now we set-up an xy-plane, where the axes of the coordinate plane is parallel to the sides of $R$. Denote the vertical segment except the sides with the smallest $x$-coordinate by $l$. We will make refinements such that $l$ intersects both horizontal sides of $R$. [asy][asy] size(4cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -0.4, xmax = 6.29, ymin = -1.095, ymax = 2.835; /* image dimensions */ pen zzttqq = rgb(0.6,0.2,0); draw((0,0)--(3,0)--(3,2)--(0,2)--cycle, linewidth(0.8) + zzttqq); /* draw figures */ draw((0,0)--(3,0), linewidth(0.8) + zzttqq); draw((3,0)--(3,2), linewidth(0.8) + zzttqq); draw((3,2)--(0,2), linewidth(0.8) + zzttqq); draw((0,2)--(0,0), linewidth(0.8) + zzttqq); draw((0.395,0.7275)--(0.395,0), linewidth(0.8)); draw((0,0.7275)--(0.395,0.7275), linewidth(0.8)); draw((0,1.335)--(0.62,1.335), linewidth(0.8)); /* dots and labels */ dot((0,0),linewidth(4pt) + dotstyle); label("$A$", (0.0275,0.06), NE * labelscalefactor); dot((3,0),dotstyle); label("$B$", (3.0275,0.075), NE * labelscalefactor); dot((3,2),dotstyle); label("$C$", (3.0275,2.0775), NE * labelscalefactor); dot((0,2),dotstyle); label("$D$", (0.0275,2.0775), NE * labelscalefactor); label("$R$", (1.4975,1.005), NE * labelscalefactor,zzttqq); dot((0.395,0),dotstyle); label("$E$", (0.425,0.075), NE * labelscalefactor); dot((0.395,0.7275),dotstyle); label("$F$", (0.425,0.8025), NE * labelscalefactor); dot((0,1.335),dotstyle); label("$G$", (0.0275,1.41), NE * labelscalefactor); dot((0.62,1.335),dotstyle); label("$H$", (0.65,1.41), NE * labelscalefactor); dot((0,0.7275),linewidth(4pt) + dotstyle); label("$I$", (0.0275,0.7875), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] Suppose $l=EF$. If both of them lies on the sides of $R$ then we are done. Otherwise suppose $F$ does not. Then it must be a Class $B$ vertex, hence $FI$ is a segment where $I$ lies on $AD$. Suppose $G$ is the vertex right above $I$ on $AD$. Moreover, since $l$ is the leftmost line, the segment at $G$ parallel to $AB$ must extend over $EF$. Suppose $FE$ meet this segment at $J$. We replace the segment $IF$ by $FJ$, it is easy to see that the number of rectangles remain the same while the number of class $B$ vertex does not increase, hence by $(1)$ and $(2)$ the number of basic segments does not increase as well. [asy][asy] size(4cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -0.925, xmax = 5.765, ymin = -1.095, ymax = 2.835; /* image dimensions */ pen zzttqq = rgb(0.6,0.2,0); draw((0,0)--(3,0)--(3,2)--(0,2)--cycle, linewidth(0.8) + zzttqq); /* draw figures */ draw((0,0)--(3,0), linewidth(0.8) + zzttqq); draw((3,0)--(3,2), linewidth(0.8) + zzttqq); draw((3,2)--(0,2), linewidth(0.8) + zzttqq); draw((0,2)--(0,0), linewidth(0.8) + zzttqq); draw((0.395,0.7275)--(0.395,0), linewidth(0.8)); draw((0.395,0.7275)--(0.395,1.335), linewidth(0.8)); draw((0,1.335)--(0.62,1.335), linewidth(0.8)); /* dots and labels */ dot((0,0),linewidth(4pt) + dotstyle); label("$A$", (0.0275,0.06), NE * labelscalefactor); dot((3,0),dotstyle); label("$B$", (3.0275,0.075), NE * labelscalefactor); dot((3,2),dotstyle); label("$C$", (3.0275,2.0775), NE * labelscalefactor); dot((0,2),dotstyle); label("$D$", (0.0275,2.0775), NE * labelscalefactor); label("$R$", (1.4975,1.005), NE * labelscalefactor,zzttqq); dot((0.395,0),dotstyle); label("$E$", (0.425,0.075), NE * labelscalefactor); dot((0.395,0.7275),dotstyle); label("$F$", (0.425,0.8025), NE * labelscalefactor); dot((0,1.335),dotstyle); label("$G$", (0.0275,1.41), NE * labelscalefactor); dot((0.62,1.335),dotstyle); label("$H$", (0.65,1.41), NE * labelscalefactor); dot((0.395,1.335),linewidth(4pt) + dotstyle); label("$J$", (0.425,1.395), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] Now applying this algorithm we are able to made the endpoint of $l$ lie on both $CD$ and $AB$. Now consider the vertical segment to the immediate right of $l$ (here $l=LN$). Again suppose $F$ does not lie on $CD$, and $M$ is the vertex right above $OP$ on $l$. If $M$ is of Class $B$ we proceed as in the previous case. Otherwise, we replace $OP$ by $JF$ and it is easy to see that the number of Class B vertices decrease so we are done. [asy][asy] size(4cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -0.8213636363636381, xmax = 5.2604545454545475, ymin = -0.9893181818181824, ymax = 2.583409090909088; /* image dimensions */ pen zzttqq = rgb(0.6,0.2,0); draw((0,0)--(3,0)--(3,2)--(0,2)--cycle, linewidth(0.8) + zzttqq); /* draw figures */ draw((0,0)--(3,0), linewidth(0.8) + zzttqq); draw((3,0)--(3,2), linewidth(0.8) + zzttqq); draw((3,2)--(0,2), linewidth(0.8) + zzttqq); draw((0,2)--(0,0), linewidth(0.8) + zzttqq); draw((0.9581818181818176,0.7275)--(0.9581818181818176,0), linewidth(0.8)); draw((0,1.335)--(1.5104545454545453,1.335), linewidth(0.8)); draw((0.5695454545454537,0)--(0.5695454545454537,1.335), linewidth(0.8)); draw((0.5695454545454537,1.335)--(0.5695454545454537,2), linewidth(0.8)); draw((0,0.7275)--(0.9581818181818176,0.7275), linewidth(0.8)); /* dots and labels */ dot((0,0),linewidth(4pt) + dotstyle); label("$A$", (0.02409090909090793,0.05386363636363501), NE * labelscalefactor); dot((3,0),dotstyle); label("$B$", (3.02409090909091,0.0675), NE * labelscalefactor); dot((3,2),dotstyle); label("$C$", (3.02409090909091,2.06522727272727), NE * labelscalefactor); dot((0,2),dotstyle); label("$D$", (0.02409090909090793,2.06522727272727), NE * labelscalefactor); label("$R$", (1.4968181818181816,1.001590909090907), NE * labelscalefactor,zzttqq); dot((0.9581818181818176,0),dotstyle); label("$E$", (0.9854545454545448,0.0675), NE * labelscalefactor); dot((0.9581818181818176,0.7275),dotstyle); label("$F$", (0.9854545454545448,0.7970454545454527), NE * labelscalefactor); dot((0,1.335),dotstyle); label("$G$", (0.02409090909090793,1.403863636363634), NE * labelscalefactor); dot((1.5104545454545453,1.335),dotstyle); label("$H$", (1.5377272727272724,1.403863636363634), NE * labelscalefactor); dot((0.9581818181818175,1.335),linewidth(4pt) + dotstyle); label("$J$", (0.9854545454545448,1.3902272727272704), NE * labelscalefactor); dot((0.5695454545454537,0),dotstyle); label("$L$", (0.596818181818181,0.0675), NE * labelscalefactor); dot((0.5695454545454537,1.335),linewidth(4pt) + dotstyle); label("$M$", (0.596818181818181,1.3902272727272704), NE * labelscalefactor); dot((0.5695454545454537,2),linewidth(4pt) + dotstyle); label("$N$", (0.596818181818181,2.0515909090909066), NE * labelscalefactor); dot((0,0.7275),linewidth(4pt) + dotstyle); label("$O$", (0.02409090909090793,0.7834090909090891), NE * labelscalefactor); dot((0.5695454545454537,0.7275),linewidth(4pt) + dotstyle); label("$P$", (0.596818181818181,0.7834090909090891), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] [asy][asy] size(4cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -0.8174157427937931, xmax = 5.116065410199559, ymin = -1.012034368070955, ymax = 2.473553215077604; /* image dimensions */ pen zzttqq = rgb(0.6,0.2,0); draw((0,0)--(3,0)--(3,2)--(0,2)--cycle, linewidth(0.8) + zzttqq); /* draw figures */ draw((0,0)--(3,0), linewidth(0.8) + zzttqq); draw((3,0)--(3,2), linewidth(0.8) + zzttqq); draw((3,2)--(0,2), linewidth(0.8) + zzttqq); draw((0,2)--(0,0), linewidth(0.8) + zzttqq); draw((0.9581818181818176,0.7275)--(0.9581818181818176,0), linewidth(0.8)); draw((0,1.335)--(1.5104545454545453,1.335), linewidth(0.8)); draw((0.5695454545454537,0)--(0.5695454545454537,1.335), linewidth(0.8)); draw((0.5695454545454537,1.335)--(0.5695454545454537,2), linewidth(0.8)); draw((0.9581818181818176,0.7275)--(0.9581818181818175,1.335), linewidth(0.8)); draw((0.5695454545454537,0.7275)--(0.9581818181818176,0.7275), linewidth(0.8)); /* dots and labels */ dot((0,0),linewidth(4pt) + dotstyle); label("$A$", (0.027373614190686343,0.05226718403547532), NE * labelscalefactor); dot((3,0),dotstyle); label("$B$", (3.027373614190688,0.0655709534368057), NE * labelscalefactor); dot((3,2),dotstyle); label("$C$", (3.027373614190688,2.0677882483370276), NE * labelscalefactor); dot((0,2),dotstyle); label("$D$", (0.027373614190686343,2.0677882483370276), NE * labelscalefactor); label("$R$", (1.4974401330376939,1.0034866962305975), NE * labelscalefactor,zzttqq); dot((0.9581818181818176,0),dotstyle); label("$E$", (0.9852450110864741,0.0655709534368057), NE * labelscalefactor); dot((0.9581818181818176,0.7275),dotstyle); label("$F$", (0.9852450110864741,0.7972782705099766), NE * labelscalefactor); dot((0,1.335),dotstyle); label("$G$", (0.027373614190686343,1.4025997782705089), NE * labelscalefactor); dot((1.5104545454545453,1.335),dotstyle); label("$H$", (1.537351441241685,1.4025997782705089), NE * labelscalefactor); dot((0.9581818181818175,1.335),linewidth(4pt) + dotstyle); label("$J$", (0.9852450110864741,1.3892960088691784), NE * labelscalefactor); dot((0.5695454545454537,0),dotstyle); label("$L$", (0.5994356984478929,0.0655709534368057), NE * labelscalefactor); dot((0.5695454545454537,1.335),linewidth(4pt) + dotstyle); label("$M$", (0.5994356984478929,1.3892960088691784), NE * labelscalefactor); dot((0.5695454545454537,2),linewidth(4pt) + dotstyle); label("$N$", (0.5994356984478929,2.0544844789356973), NE * labelscalefactor); dot((0,0.7275),linewidth(4pt) + dotstyle); label("$O$", (0.027373614190686343,0.7839745011086462), NE * labelscalefactor); dot((0.5695454545454537,0.7275),linewidth(4pt) + dotstyle); label("$P$", (0.5994356984478929,0.7839745011086462), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] Now after applying this algorithm for finitely many times all vertical segments are from $CD$ to $AB$. By symmetry all horizontal segments are from $AD$ to $CB$. In other words, the chessboard are partitioned into a $m\times n$ subgrid where $mn=2016$. In this case the number of basic segments is $$m(n+1)+n(m+1)=2mn+m+n\leq 2\times 2016+48+42=4122$$as desired.
02.09.2021 23:33
Nonrigorous: Since the shape of $R$ is arbitrary, if we call a partitioned $R$ ordered if each rectangle is of the same size, then we claim that basic segments are maximized in an ordered rectangle. Proof: Take a subset of $3$ rectangles, $1$ of which shares sides with the other two, and is exactly twice as large. The number of basic segments is $8$. However, when extending the line between two rectangles to meet the larger rectangle at a $2$nd point distinct from the first, we yield $12$ basic segments. Since this can be extended to a larger subset of rectangles, the claim is proven $\square$ Now, utilizing an ordered arrangement, if we partition the rectangle into $x=mn$ partitions such that $m$ and $n$ are side lengths of $R$, then we claim the maximum number of basic segments are obtained when $m=x$ and $n=1$, and the minimum number of basic segments are obtained when $|m - n|$ is as small as possible. Proof of Max: Trivially the number of basic segments in an $m \times n$ ordered $R$ is $m(n+1)+n(m+1)$. If $m$ is maximized and $n=1$, then $3m+1$ is our maximum. In this case $3(2016)+1=\boxed{6049}$ Proof of Min: If $m$ and $n$ are about the same, then $2mn+m+n$ will be minimized since $mn$ is fixed and $m+n$ changes according to values of $\{m,n \}$. This occurs when $m=42$ and $n=48$, which means $2(48)(42)+48+42=\boxed{4122}$ $\blacksquare$
06.09.2021 20:02
Let $m$ be the number of vertices, and let $k$ be the number of vertices that are part of $4$ basic segments. Claim: $m=4034-k$. Proof: There are $4$ vertices that are part of only one rectangle, $m-k-4$ vertices that are part of two rectangles, and $k$ vertices that are part of $4$ rectangles. There are at most $2016 \cdot 4=8064$ rectangles. However, we counted $m-k-4$ vertices twice and $k$ vertices $4$ times. Thus, there are $m=8064-(m-k-4)-3k=8068-m-2k$. Thus, $m=4034-k$. Claim: The number of basic segments is $6049-k$. Proof: Let the vertices be vertices of a graph, and let the edges be the basic segments. We have that the sum of the degrees of each vertex is $$4 \cdot 2+3(m-k-4)+4k=3m+k-4=3(4034-k)+k-4=12098-2k.$$Since the number of edges is half of the sum of degrees, we know that the number of basic segments is $6049-k$. Thus, we want to minimize and maximize $k$. The minimum value $k=0$ can be achieved by a brick wall pattern. To maximize $k$, we want to minimize the number of vertices that are part of at most $3$ basic segments. Consider $X$, the set of all $x$-coordinates of the vertices, and $Y$, the set of all $y$-coordinates of the vertices. Notice that for each $x \in X$, there cannot be exactly one vertex with $x$-coordinate $x$, since that means the vertex cannot be a part of any rectangle. A similar statement can be made for $Y$. Now, notice that the top and bottom vertex with $x$-coordinate $x$ cannot be part of $4$ basic segments. Thus, the number of vertices that are part of at most $3$ basic segments is at least $2|X|+2|Y|-4$, since we overcounted the four corner vertices. We also know that $|X||Y| \geq 2016$, so we have that the maximum value of $2|x|+2|y|-4$ is $176$ by AM-GM. This is achieved when the partition is a $42 \times 48$ grid, when $k=41 \cdot 47=1927$. Thus, the minimum number of basic segments is $6049-1927=4122$.
29.12.2022 01:51
Sketch: Maximum: Maximum is achieved when with parallel cuts. Because $V-E+F = 2$, and $F=2017$, we have that $E = V + 2015$, so it suffices to maximize $V$. Double count pairs $(\text{Rectangle}, \text{Vertex})$, with the vertex being a vertex of the rectangle; fixing $(\text{Rectangle}$, we get there are $2016 \cdot 4$ pairs. Noting that apart from the 4 original vertices of $R$, all vertices can belong to either $2$ or $4$ rectangles. As we want to maximize vertices, we let all the non-corner vertices belong to $2$ rectangles. This gives a total of $4030+4=4034$ vertices, and subsequently $4034 + 2015 = \boxed{6049}$ edges. Minimum: Minimum is achieved when it is almost grid-like in structure, except shortening a few edges as the bound is not tight for $2016$ (a bit lazy to give exact construction). Let $v_2$ and $v_4$ denote the number of vertices belonging to 2 and 4 rectangles, respectively. The same double counting gives $2v_2 + 4v_4 = 2016 \cdot 4 - 4 = 8060.$ Consider the maximal lines (i.e. we combine collinear basic segments) in the partition (not counting the sides of $R$). Clearly the number of maximal lines is not greater than $\frac{v_2}{2}$, by considering the endpoints of each maximal line. Note that every vertex belonging to 4 rectangles can be uniquely identified by the maximal horizontal line and maximal vertical line that intersects at the vertex. Subsequently, AM-GM can give that $v_4 \le \left(\frac{v_2}{4}\right)^2$. Combining this with the previous equation in terms of $v_2$ and $v_4$ gives that $v_2 \ge 176$. Since we are minimizing $v_2$ and maximizing $v_4$ to attain the minimum, we can get a bound of $v_2 + v_4 + 4 + 2015 = 176 + 1927 + 4 + 2015 = \boxed{4122}$.
26.01.2023 07:15
The upper bound is $2016 \cdot 3 + 1 = 6049$. Take the obvious graph interpretation. For a proof of the general case, see https://artofproblemsolving.com/community/c6h285864p26943494. To find the lower bound, first observe that each vertex has degree at most four. Claim. For each vertex with degree four, there exists at least two vertices of degree $3$ that shares an $x$-coordinate with that vertex and one that shares a $y$-coordinate. Proof. This is quite immediate: the vertical edge emanating up from the vertex of degree four must terminate at a vertex of degree $3$, or another vertex of degree $4$, at which point we can repeat the argument. The case is similar for the other three vertices. $\blacksquare$ Thus, assume that the vertices of degree $4$ determine $a$ horizontal projections and $b$ vertical projections. This means that the total degree count is at most $$2E = \text{totdeg} \leq 4ab + 6(a+b) + 8,$$where $V = ab+2(a+b)+4$. Using Euler's Formula, we have $$E = V+F-2=2019+ab+2(a+b),$$so we have the inequality $$2019+ab+2(a+b) \leq 4ab+6(a+b)+8 \iff (a+1)(b+1) \geq 2016.$$This means that $a+b+2 \geq \lceil 2\sqrt{2016} \rceil = 90$ or $a+b \geq 88$, with equality at $(41, 47)$. As a result, $$E = 2019+ab+2(a+b) \leq 2019+(a+1)(b+1) - 1 + 88 = \boxed{4122}.$$Equality occurs when we construct a $42 \times 48$ grid of rectangles.
23.06.2023 09:49
I read a quora post about China problems once and still have an ingrained fear from that post. Anyways, Let $n = 2016$ be the number of rectangles. Claim: It is equivalent to maximize the number of vertices. Proof. By Euler's formula $v + n - 1 = e$. As such, it is equivalent to minimize and maximize the number of vertices. $\blacksquare$ Claim: The maximum number of vertices is $2n + 2$. Proof. Besides the outer vertices, every vertex is shared by at least $2$ rectangles. As such, $v \le \frac{4}{2} \cdot (n - 4) + 4 = 2n + 2$. This bound can be achieved by creating two new vertices with every rectangle through cutting a pre-existing rectangle in half. $\blacksquare$ Claim: The minimum number of vertices for $n = 2016$ is $2107$. Proof. Let $v_i$ be the number of vertices which are the corner of exactly of $i$ rectangles. Then $v_1 = 4$ and \[ v_1 + 2v_2 + 4v_4 = 4n \]and we want to minimize $v_1 + v_2 + v_4$. Since $v_1$ is constant, it follows that maximizing $v_4$ is optimal. Furthermore, each vertex with $4$ rectangles with a different coordinate implies a vertex with $2$ rectangles offset in one of the axes. As such, $v_2$ is at least the minimal number of projections onto the sides of the rectangle. More formally, if we define $s$ such $s^2 \le v_4 < (s+1)^2$ and $S$ as $2s + 2$ if $v_4 \in (s(s+1) + 1, (s+1)^2)$ and else $2s + 1$, it follows that $v_2 \ge 2S$. Cutting in $42 \times 48 = 2016$ smaller rectangles gives $v_4 = 41 \cdot 47 = 1927$, $v_2 = 2 \cdot (41 + 47) = 88$. Then, it follows that there are $4 + 176 + 1927 = 2107$ vertices and that $4 + 2 \cdot 176 + 4\cdot 1927 = 4 \cdot 2016$ holds. If $v_4 > 1927$, it follows that since $1928 \in (43 \cdot 44, 44^2)$ that $v_2 \ge 2 \cdot (2 \cdot 44) = 176$, however then $v_1 + 2v_2 + v_4 > 4n$, contradiction. $\blacksquare$ Thus, $e$ has a maximal value of $2n + 2 + (n - 1) = 6049$ and a minimal value of $2107 + (n - 1) = 4122$.
20.10.2023 05:18
The answer is the minimum is $4122$ and the maximum is $6049.$ First of all, by Euler's formula we have $$e=v+2015,$$so it suffices to find the minimum and maximum of $v$. We claim that the maximum of $v$ is 4034. This can be achieved by having 2016 rectangles stacked on top of each other. Note that the degree of each non-corner vertex is at least 3. Thus, $$2e\geq 3v-4$$$$2v+4030\geq 3v-4$$$$v\leq 4034.$$ We then claim that the minimum of $v$ is $2107=43\cdot 49.$ This is achieved by making a $42$ by $48$ grid. Let $x$ be the number of distinct x-coordinates occupied by vertices in the interior of the rectangle, and define $y$ similarly. There can be at most $(x+1)(y+1)$ regions, so $$(x+1)(y+1)\geq 2016.$$However, if $x+y=87$, by AM-GM $$(x+1)(y+1)\leq 1980.25,$$which means that $x+y\geq 88$. Thus, $2(x+y)\geq 176$, so there are at least 176 vertices of degree 3 (that lie on the sides of the rectangle). Since there are also 4 vertices of degree 2, the total "loss" compared to all degree 4 is at least 184. Hence, the sum of the degrees is at most $4v-184$, so $$2e\leq 4v-184$$$$2v+4030\leq 4v-184$$$$2v\geq 4214$$$$v\geq 2107,$$as desired.
20.11.2023 21:51
variables The answer is $4122\le b\le 6049$. For the minimum, construct a $45\times 44$ grid of unit squares, then add a $45\times 1$ composed of $35$ $1\times 1$ squares and one $10\times 1$ rectangle to the end. For the maximum, just consider a $2016\times 1$ split into 2016 unit squares. Now let's prove bounds. There are a few technicalities to get through, but we'll ignore them. Suppose there are $f$ four-way intersections inside the rectangle. Notice that there are $8064$ corners in the rectangle. We can assign: $1$ corner to each of $4$ vertices. These represent the corners of the large rectangle. $4$ corners to each of $f$ vertices. These are the four-way intersections. $2$ corners to all of the other $4030-2f$ vertices. Evidently since $V-E+F=1$ with $V=4034-f$, $F=2016$ we can calculate $E=6049-f$. This immediately proves $E\le 6049$. Now I claim $f+2\sqrt{f}\le 2015$ which finishes since it implies $f\le 1927$. Count again, this time double-counting the number of edges. Let's suppose the $f$ four-way intersections can be categorized along $h$ horizontal and $v$ vertical lines. The number of vertices adjacent to three edges is at least $2h+2v$, since each one of the lines provides $2$ such vertices. We'll say there are $k+2h+2v$ vertices adjacent to three edges. There are $4$ vertices adjacent to two edges: the corners of the rectangle. There are $f\le hv$ vertices adjacent to four edges. So we can calculate $V=2h+2v+k+4+f$, $E=3h+3v+1.5k+4+2f$, $F=2016$. \[h+v+f+0.5k=2015\]\[f+2\sqrt{f}\le h+v+f\le h+v+f+0.5k=2015\]and we're done.
01.11.2024 05:26
Suppose there are $n$ basic segments. We claim the answer is $4122\le n\le 6049$. Let $a$ be the number of $\perp$ intersections and let $b$ be the number of $+$ intersections. First notice that each $a$ counts $180^\circ$ of vertices of the rectangles around it, and each $b$ counts $360^\circ$. Adding in the four vertices of $R$, we obtain $\tfrac a2+b=2015$. Next count how many fully extended segments there are. Notice each segment except the four sides of $R$ has two endpoints, which are distinct $\perp$ intersections. Thus there are $4+\tfrac a2$ segments. Now we count how many basic segments there are. One vertex is added along a fully extended segment for each $\perp$ intersection stemming from it, and each $+$ intersection on it. The empty full segment has one basic segment, so there is one more basic segment than number of vertices. Summing over all segments, each $\perp$ intersection stems from one segment and each $+$ intersection is on two segments, so we get $n=4+\tfrac a2+a+2b$. Substituting $\tfrac a2+b=2015$, we get $n=4+3\cdot 2015-b=6049-b$. The upper bound $n\le 6049$ is clear. For the lower bound, notice that there are $\tfrac a2$ fully extended segments other than the sides of $R$, and every $+$ intersection is the intersection of a distinct pair of horizontal and vertical segments, so AM-GM implies $b\le(\tfrac a4)^2$. From $\tfrac a2+b=2015$ we get $2015\le\tfrac a2+(\tfrac a4)^2$, which becomes $\tfrac a2\ge 88$, so $b\le 1927$ and $n\ge 4122$. To construct the lower bound, take a $42\times 48$ grid of rectangles. To construct the upper bound, take a row of $2016$ rectangles.
21.11.2024 14:34
Okay, here we go: Convert the given plane into a planar graph where nodes are vertices of triangles. Note that (Euler's Formula for planar graphs): $$V+F=E+2$$where $F=2017$ and basically $E$ is the no of basic segments. Let $a, b$ denote the vertices having degree $3, 4$ respectively. Then: $$E = \frac{2 \cdot 4 + 3 \cdot a + 4 \cdot b}{2}$$with $V=a+b+4$. Plugging back gives us: $4030 = a+2b.$ Notice that: $$E = \frac{2 \cdot 4 + 3 \cdot a + 4 \cdot b}{2} = 4+2b+\frac{3a}{2} = 4034+\frac{a}{2}.$$Note that $a \le 4030$ which gives us the upper bound. It holds when we divide the rectangle into $2016$ congruent rectangles each having the width same as the original rectangle $R$, having no vertices of degree $4$ For lower bound, we tend to maximize the number of degree $4$ vertices or variable $b$. Now, consider two edges having same line when extended completely to be similar and the set of similar lines to be called as batch. Notice that each batch has at-least $2$ vertices of degree $3$. We tend to minimize no of batches. Let there be $p$ vertical and $q$ horizontal batches. It creates $(p+1)(q+1) = 2016$ rectangles. By AM-GM, $p+q \ge 86$ which plugging back gives $1929 \ge pq$. Note that: $pq \ge b$. Thus: $b \le 1929$ which leads to $a \ge 172$ and $E \ge 4122$. Construction for lower bound: Divide it into $42 \times 48$ rectangles which gives us the result.