A rectangle is partitioned into finitely many small rectangles. We call a point a cross point if it belongs to four different small rectangles. We call a segment on the obtained diagram maximal if there is no other segment containing it. Show that the number of maximal segments plus the number of cross points is $3$ more than the number of small rectangles.
Problem
Source:
Tags: geometry, rectangle, combinatorics unsolved, combinatorics
03.11.2010 21:43
We can construct all possibilities by repeating the operation above: $operation:$ Select two points $p_1,p_2$ from two parallel maximal segment $s_1,s_2$ respectively, such that the segment $[p_1,p_2]$ will be perpendicular to $s_1$ and $s_2$, and then draw the segment $[p_1,p_2]$.(Note that a segment which we draw shouldn't be destroy any previous maximal segment's maximality.) After the $i$'th and before the $i+1$'th operations, let $ds_i$ is the change of the total number of maximal segments, let $dn_i$ is the change of the total number of cross points, and let $dr_i$ is the change of the total number of small rectangles. Then $ds_i=1$. If the segment $[p_1,p_2]$ do not intersects with any segment except $s_1$ and $s_2$, then $dn_i$ will be $0$ and $dr_i$ will be $1$. If $[p_1,p_2]$ cuts one segment, then $dn_i$ will be $1$ and $dr_i$ will be $2$. If $[p_1,p_2]$ cuts two segments, then $dn_i$ will be $2$ and $dr_i$ will be $3$, and so on. Thus ${ds_i}+{dn_i}=dr_i$. Before the first operation, $s=4$ (sides of the main rectangle), $n=0$ and $r=1$. After $k$ operation, $s$ will be $s=4+{ds_1}+{ds_2}+\ldots +{ds_k}=4+k$. $n$ will be $n={dn_1}+{dn_2}+\ldots +{dn_k}$. $r$ will be $r=1+{dr_1}+{dr_2}+\ldots +{dr_k}$. Since for each $i$, ${ds_i}+{dn_i}={dr_i}$, $({ds_1}+{ds_2}+\ldots +{ds_k})+({dn_1}+{dn_2}+\ldots +{dn_k})=({dr_1}+{dr_2}+\ldots +{dr_k})$. So, $(s-4)+n=(r-1)$ so $s+n=r+3$.
03.11.2010 23:14
hasan bilgin bicer wrote: We can construct all possibilities by repeating the operation above: $operation:$ Select two points $p_1,p_2$ from two parallel maximal segment $s_1,s_2$ respectively, such that the segment $[p_1,p_2]$ will be perpendicular to $s_1$ and $s_2$, and then draw the segment $[p_1,p_2]$.(Note that a segment which we draw shouldn't be destroy any previous maximal segment's maximality.) After the $i$'th and before the $i+1$'th operations, let $ds_i$ is the change of the total number of maximal segments, let $dn_i$ is the change of the total number of cross points, and let $dr_i$ is the change of the total number of small rectangles. Then $ds_i=1$. If the segment $[p_1,p_2]$ do not intersects with any segment except $s_1$ and $s_2$, then $dn_i$ will be $0$ and $dr_i$ will be $1$. If $[p_1,p_2]$ cuts one segment, then $dn_i$ will be $1$ and $dr_i$ will be $2$. If $[p_1,p_2]$ cuts two segments, then $dn_i$ will be $2$ and $dr_i$ will be $3$, and so on. Thus ${ds_i}+{dn_i}=dr_i$. Before the first operation, $s=4$ (sides of the main rectangle), $n=0$ and $r=1$. After $k$ operation, $s$ will be $s=4+{ds_1}+{ds_2}+\ldots +{ds_k}=4+k$. $n$ will be $n={dn_1}+{dn_2}+\ldots +{dn_k}$. $r$ will be $r=1+{dr_1}+{dr_2}+\ldots +{dr_k}$. Since for each $i$, ${ds_i}+{dn_i}={dr_i}$, $({ds_1}+{ds_2}+\ldots +{ds_k})+({dn_1}+{dn_2}+\ldots +{dn_k})=({dr_1}+{dr_2}+\ldots +{dr_k})$. So, $(s-4)+n=(r-1)$ so $s+n=r+3$. Edit: Before drawing a partition $A$ with the operation on my previous post, It seems that another operation is required. It is as follows: Repeat this procedure $i)$ until there isn't a maximal segment $[p_1,p_2]$ on $A$ which satisfies that at least one of the points from $p_1,p_2$, is not on any sides of the main rectangle: $i)$ Change the maximal segment $[p_1,p_2]$ with the segment $[{p_1}',{p_2}']$ which includes the points $p_1,p_2$ and each point from ${p_1}',{p_2}'$ is on a side of the main rectangle. For its each step, this procedure will be produce ${dn_i}'$ additional cross points and ${dr_i}'$ additional small rectangles and ${ds_i}'$ additional maximal segments(${ds_i}'$ will be negative or zero). Since ${ds_i}'+{dn_i}'$ will be equal to ${dr_i}'$ , if $s+n=r+3$ is true for this modified partition, then $s+n=r+3$ will be true for the original partition.
06.04.2019 19:59
Anonymous wrote: hasan bilgin bicer wrote: We can construct all possibilities by repeating the operation above: $operation:$ Select two points $p_1,p_2$ from two parallel maximal segment $s_1,s_2$ respectively, such that the segment $[p_1,p_2]$ will be perpendicular to $s_1$ and $s_2$, and then draw the segment $[p_1,p_2]$.(Note that a segment which we draw shouldn't be destroy any previous maximal segment's maximality.) After the $i$'th and before the $i+1$'th operations, let $ds_i$ is the change of the total number of maximal segments, let $dn_i$ is the change of the total number of cross points, and let $dr_i$ is the change of the total number of small rectangles. Then $ds_i=1$. If the segment $[p_1,p_2]$ do not intersects with any segment except $s_1$ and $s_2$, then $dn_i$ will be $0$ and $dr_i$ will be $1$. If $[p_1,p_2]$ cuts one segment, then $dn_i$ will be $1$ and $dr_i$ will be $2$. If $[p_1,p_2]$ cuts two segments, then $dn_i$ will be $2$ and $dr_i$ will be $3$, and so on. Thus ${ds_i}+{dn_i}=dr_i$. Before the first operation, $s=4$ (sides of the main rectangle), $n=0$ and $r=1$. After $k$ operation, $s$ will be $s=4+{ds_1}+{ds_2}+\ldots +{ds_k}=4+k$. $n$ will be $n={dn_1}+{dn_2}+\ldots +{dn_k}$. $r$ will be $r=1+{dr_1}+{dr_2}+\ldots +{dr_k}$. Since for each $i$, ${ds_i}+{dn_i}={dr_i}$, $({ds_1}+{ds_2}+\ldots +{ds_k})+({dn_1}+{dn_2}+\ldots +{dn_k})=({dr_1}+{dr_2}+\ldots +{dr_k})$. So, $(s-4)+n=(r-1)$ so $s+n=r+3$. Edit: Before drawing a partition $A$ with the operation on my previous post, It seems that another operation is required. It is as follows: Repeat this procedure $i)$ until there isn't a maximal segment $[p_1,p_2]$ on $A$ which satisfies that at least one of the points from $p_1,p_2$, is not on any sides of the main rectangle: $i)$ Change the maximal segment $[p_1,p_2]$ with the segment $[{p_1}',{p_2}']$ which includes the points $p_1,p_2$ and each point from ${p_1}',{p_2}'$ is on a side of the main rectangle. For its each step, this procedure will be produce ${dn_i}'$ additional cross points and ${dr_i}'$ additional small rectangles and ${ds_i}'$ additional maximal segments(${ds_i}'$ will be negative or zero). Since ${ds_i}'+{dn_i}'$ will be equal to ${dr_i}'$ , if $s+n=r+3$ is true for this modified partition, then $s+n=r+3$ will be true for the original partition. WHAT A PROOF BRILLIANT