We have sheet of paper, divided on $100\times 100$ unit squares. In some squares we put rightangled isosceles triangles with leg =$1$ ( Every triangle lies in one unit square and is half of this square). Every unit grid segment( boundary too) is under one leg of triangle. Find maximal number of unit squares, that don`t contains triangles.
Problem
Source: All russian olympiad 2016,Day1,grade 11,P3
Tags: combinatorics
sansae
12.06.2016 16:11
i can't understand the question ... what is 'unit grid segment' and under one leg of triangle?
sansae
12.06.2016 19:51
Can I know the answer? Maybe I can guess what question means from the answer ...
dgrozev
13.06.2016 20:04
In Russian, what is translated here as "Every unit grid segment( boundary too) is under one leg of triangle" means: Every segment with length 1 connecting neighbouring knots of the grid(including those on the boundary) is covered by exactly one leg of some triangle. I hope it's clearer.
MellowMelon
13.06.2016 20:28
Can two triangles be put in the same square?
dgrozev
13.06.2016 21:18
The original text only says the triangles are non overlapping, so I suppose - yes, it's permitted to put two triangles into one square.
anantmudgal09
13.06.2016 21:32
Is my interpretation correct? We have a $100 \times 100$ board and we place some right-angled isosceles triangles in it such that each grid-segment (a line segment connecting two adjacent knots on the grid, including the boundary) is a leg of exactly one triangle. What maximal number of unit squares do not have a triangle placed inside them?
MellowMelon
13.06.2016 22:50
My question was kind of dumb since any tiling requires some squares to have two triangles.... Anyways, here's a full solution.
Each triangle covers a vertical and horizontal segment. Consider the triangles in each row. There are 101 vertical segments and only triangles in the row cover them, so every row has 101 triangles. In the top row, there are 100 horizontal segments above it which must be covered by triangles in this row, so 100 of the top row's triangles cover a horizontal segment above, meaning exactly one covers a horizontal segment below. Then in the second row form the top, there are 99 horizontal segments above remaining to be covered, so 99 cover a top segment and 2 cover a segment below. This continues until we show that in row $k$ from the top ($1 \le k \le 100$), $101 - k$ triangles cover a horizontal segment above the row and $k$ triangles cover a segment below the row.
If a square has no triangles in it, this means the segment above the square and the segment below the square are not covered by triangles in that row. Therefore, in row $k$, we can have up to $\min(100 - (101 - k), 100 - k)$ squares that are blank before we run out of segments above or segments below that are not covered by triangles in that row. Summing this over all $k$ from 1 to 100 gives at most
\[ 0 + 1 + 2 + \cdots + 48 + 49 + 49 + 48 + \cdots + 2 + 1 + 0 = 49 \cdot 50 \]blank squares.
This obtains $49 \cdot 50$ blank squares, the upper bound shown above. Assuming rows and columns are numbered 1 to 100 and squares are identified by ordered pairs (column #, row #),
1. place upper-left oriented triangles in squares $(x,y)$ with $x+y \leq 51$,
2. place lower-left oriented triangles in squares $(x,y)$ with $y \geq 51+x$,
3. place upper-right oriented triangles in squares $(x,y)$ with $x \geq 51+y$,
4. place lower-right oriented triangles in squares $(x,y)$ with $x+y \geq 151$, and
5. in the remaining squares $(x,y)$ without any triangles yet, if $x+y$ is even, then place two triangles, and if $x+y$ is odd, leave it blank.
This is easily generalized to $2k \times 2k$ obtaining $k(k-1)$ blank squares. Here's what the pattern looks like for 10 by 10, where slashes are squares with one triangle, Os are squares with two triangles, and spaces are empty squares (there are $4 \cdot 5 = 20$ of them):
/////O\\\\
////O O\\\
///O O O\\
//O O O O\
/O O O O O
O O O O O/
\O O O O//
\\O O O///
\\\O O////
\\\\O/////
sansae
14.06.2016 20:09
Oh thank you guys I thought that I can put 1 or 0 triangles in one unit square ... So I got contradiction and confused Anyways, thanks!!! (Sorry for my English) BUT... isn't it possible? ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ ㅁㅇㅁㅇㅁㅇㅁㅇㅁㅁ ㅁㅁㅇㅁㅇㅁㅇㅁㅇㅁ ㅁㅇㅁㅇㅁㅇㅁㅇㅁㅁ ㅁㅁㅇㅁㅇㅁㅇㅁㅇㅁ ㅁㅇㅁㅇㅁㅇㅁㅇㅁㅁ ㅁㅁㅇㅁㅇㅁㅇㅁㅇㅁ ㅁㅇㅁㅇㅁㅇㅁㅇㅁㅁ ㅁㅁㅇㅁㅇㅁㅇㅁㅇㅁ ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ ( at 10 $\times$ 10) (ㅁ have triangles , ㅇ do not have triangle) Do I misunderstood the question?
MellowMelon
14.06.2016 20:41
You have not obeyed the "exactly one leg of some triangle" constraint. Some segments of that grid are covered by two triangles.
sansae
16.06.2016 20:31
OH... thanks!
yayups
05.07.2020 02:26
The answer is $50\cdot 49=\boxed{2550}$, achieved at the following example with $100$ replaced by $8$ (generalization clear).
Let's now show that this is optimal. Call a triangle up facing if its horizontal leg is the higher edge of the unit square it's in. Similarly define down facing triangles. Consider any row. We see that it has $101$ vertical segments, so it must contain exactly $101$ triangles. The top row has $100$ horizontal segments on top of it, so exactly $100$ of the triangles are up facing, so exactly one is down-facing. Consider the second row. Again, it has exactly $101$ triangles, but now only $99$ of the upper horizontal segments need to be touched by a triangle from the second row, so there are exactly $99$ up facing and $2$ down facing triangles. In general, we see that on row $k$, there are exactly $101-k$ up facing and $k$ down facing triangles. Thus, there are at most \[100-\max\{k,101-k\}\]empty squares on row $k$. Summing this from $k=1$ to $k=100$ gives the desired bound of $49\cdot 50$, so we're done.
khina
01.03.2021 00:48
@above multiplication... doesn't check out? I got roughly the same solution though.