Batred625 wrote: Hossna is playing with a $m*n$ grid of points.In each turn she draws segments between points with the following conditions. **1.** No two segments intersect. **2.** Each segment is drawn between two consecutive rows. **3.** There is at most one segment between any two points. Find the maximum number of regions Hossna can create. If two segments share a vertex, are they considered as intersecting? Also, what does it mean by "each segment is drawn between two consecutive rows"?

NikoIsLife wrote: Batred625 wrote: Hossna is playing with a $m*n$ grid of points.In each turn she draws segments between points with the following conditions. **1.** No two segments intersect. **2.** Each segment is drawn between two consecutive rows. **3.** There is at most one segment between any two points. Find the maximum number of regions Hossna can create. If two segments share a vertex, are they considered as intersecting? Also, what do you mean by "each segment is drawn between two consecutive rows"? First question no second question the endpoint of the segment must lie in two consecutive layers.

This is assuming that the outside region is not counted.

NikoIsLife wrote: This is assuming that the outside region is not counted.

When you are dividing into squares you are also using segments which both endpoints lie in the same row

Batred625 wrote: NikoIsLife wrote: This is assuming that the outside region is not counted.

When you are dividing into squares you are also using segments which both endpoints lie in the same row They also lie on two consecutive rows:

well my answer is $(n-1)m $ i get really stupid when its about rows and columns so just reverse everything i say if im misstaking . well first by induction we show that the $2,n$ grid ($n $is the number of rows) can be devided into $n$ regions and for sure we can say that the $m,n$ grid CAN be devided into $(n-1)m$ regions so first of all we know that every region has a min surface of a half we show that we dont have any regions that have the surface $S>1$ for the sake of contradiction , let us have a region with more than $1$ surface we say a region is in prison of$ (i,j)$ , if the region starts at the row$ i$ and is finished in row $j $ we call that region with $surface>1$ ,$A $ so lets have$ A$ is in prison of$ (b,c) $ now we show if we have $b+2<c$ we can devide the region$ A $into smaller regions (ops i forgot to say we have a grid which has the most number of regions we can create) in the row$ b $let us have the point which is in$ A $called $M$ if the is another point in row $b $which is in $A$ we get contradiction by looking at the row $b+1 $so its only$ M $ and we have that the segment of $MT$ and$ MY $are there and$ T,Y$ are points in$ A$ now lets say in the row $b+2 $(since $c>b+2 $the row $b+2 $has some points from$ A$) are $2$ points in $A $called$ G $and $H$ we know that if the segment$ GY$ is there then we dont have the segment $GT$ so if we add $GT $the segment most cut another segment and since the segment$ TH $is there if a segment is cut by$ GT $then lets say $KL $than $K$ and $L $are between$ T,Y$ and$ G,H $and this gives us contradiction by the fact that we could just draw $MG $ instead of$ MT$ and have a more regions which gives us contradiction now we have that if we have the region $S $then we should have that $S$ in prison of $(i,i+2)$ (bc there is only $1 $point in row $b+2$) now lets name it $N$ we have the region $MTYN$ has a surface bigger than one so the triangle $MTY $has a surface more than a half so there is a point between $TY$ and we are done ... so if the region $A $is in prison of $(i,i+2) $it has a surface of$ 1 $ and one can easily check if the surface $B$ is in prison of$ (i,i+1)$ it has a surface of a half (remember we are checking the best kind of drawing segments) lets have $A $regions with surface $1 $and $B$ regions with the surface of a half we have$ A+B>mn-m$ and $2A+B=2mn-2m-2n+2$ so we should have $B>2n-2$ now one can easly check a region of surface a half is in prison of $(1,2) $or $(m-1,m) $ so we have that at the very least$ n $regions are in prison of $(1,2)$ and since a region of size a half uses two consecutive points in the first row of the grid and since we have$ n-1 $consecutive points in the $m,n$ grid then by pigeon hole one of them is in $2$ regions of size a half ... and we are done

im tired just by looking at what i wrote

I think the solution is $f \le mn-m-2n+3$ if $m$ is the number of rows. We have $V+f=e+2$ and $V=mn$ $e \le (m-1)(2n-1)$ Am I right? Edit: this is wrong

I think we can use area method to solve it Every area is$S'\ge1$ And the sum of it is$S\le(m-2)(n-1)$ Because periphery area is at least$\frac12(n-1)*2$ which should be subtract So the answer is $\boxed{(m-2)(n-1)}$

@2above That's ok But just a side note: There was 1 or 2 (that I lost at exam coz' I said it's trivial ) point for proving that in the maximum condition , the graph is connected. ( It's necessary for the euler bounds Ig) Anyway, it's a pretty easy problem. I solved at the exam in like 3min at most.

Mr.C wrote: well my answer is $(n-1)m $ i get really stupid when its about rows and columns so just reverse everything i say if im misstaking . well first by induction we show that the $2,n$ grid ($n $is the number of rows) can be devided into $n$ regions and for sure we can say that the $m,n$ grid CAN be devided into $(n-1)m$ regions so first of all we know that every region has a min surface of a half we show that we dont have any regions that have the surface $S>1$ for the sake of contradiction , let us have a region with more than $1$ surface we say a region is in prison of$ (i,j)$ , if the region starts at the row$ i$ and is finished in row $j $ we call that region with $surface>1$ ,$A $ so lets have$ A$ is in prison of$ (b,c) $ now we show if we have $b+2<c$ we can devide the region$ A $into smaller regions (ops i forgot to say we have a grid which has the most number of regions we can create) in the row$ b $let us have the point which is in$ A $called $M$ if the is another point in row $b $which is in $A$ we get contradiction by looking at the row $b+1 $so its only$ M $ and we have that the segment of $MT$ and$ MY $are there and$ T,Y$ are points in$ A$ now lets say in the row $b+2 $(since $c>b+2 $the row $b+2 $has some points from$ A$) are $2$ points in $A $called$ G $and $H$ we know that if the segment$ GY$ is there then we dont have the segment $GT$ so if we add $GT $the segment most cut another segment and since the segment$ TH $is there if a segment is cut by$ GT $then lets say $KL $than $K$ and $L $are between$ T,Y$ and$ G,H $and this gives us contradiction by the fact that we could just draw $MG $ instead of$ MT$ and have a more regions which gives us contradiction now we have that if we have the region $S $then we should have that $S$ in prison of $(i,i+2)$ (bc there is only $1 $point in row $b+2$) now lets name it $N$ we have the region $MTYN$ has a surface bigger than one so the triangle $MTY $has a surface more than a half so there is a point between $TY$ and we are done ... so if the region $A $is in prison of $(i,i+2) $it has a surface of$ 1 $ and one can easily check if the surface $B$ is in prison of$ (i,i+1)$ it has a surface of a half (remember we are checking the best kind of drawing segments) lets have $A $regions with surface $1 $and $B$ regions with the surface of a half we have$ A+B>mn-m$ and $2A+B=2mn-2m-2n+2$ so we should have $B>2n-2$ now one can easly check a region of surface a half is in prison of $(1,2) $or $(m-1,m) $ so we have that at the very least$ n $regions are in prison of $(1,2)$ and since a region of size a half uses two consecutive points in the first row of the grid and since we have$ n-1 $consecutive points in the $m,n$ grid then by pigeon hole one of them is in $2$ regions of size a half ... and we are done i also arrived to this!

OK LET ME CLEAR ALL CONFUSION. The problem has two interpretations depending on how you calculate regions. If you assume there is a rectangular boundary to the grid and we are dissecting this rectangle into regions we get the answer $(n-1)m$ as in post #7. If you do not assume this rectangular boundary exists and count the entire outside region as $1$ then answer is $(n-1)(m-2)+1$ as in post #10,#11. #4 is just a fakesolve .