Click to reveal hidden text

Double post why?http://www.mathlinks.ro/Forum/viewtopic.php?t=99241

Continue the discussion here and lock my topic.

We remove $2(i-1)$ squares if $i\leq n$, and $2(2n-i)$ squares if $i>n$. Symmetry with respect to the line that separates $n$th row and $n+1$th row.

We remove the corresponding number of unit squares from every line or just from one?

Sorry for taking back this topic ! But if anyone has a solution please post it here. Thanks...

shobber wrote: Consider a $2n \times 2n$ board. From the $i$th line we remove the central $2(i-1)$ unit squares. What is the maximal number of rectangles $2 \times 1$ and $1 \times 2$ that can be placed on the obtained figure without overlapping or getting outside the board? I have tried to solve this problem for a long time. I want to ask you if the solutions are :if $n$ is odd we have $\frac{(n-1)^2}{2}$ if $n$ is even then $\frac{(n-1)^2+1}{2}$

Arberi1 wrote: shobber wrote: Consider a $2n \times 2n$ board. From the $i$th line we remove the central $2(i-1)$ unit squares. What is the maximal number of rectangles $2 \times 1$ and $1 \times 2$ that can be placed on the obtained figure without overlapping or getting outside the board? I have tried to solve this problem for a long time. I want to ask you if the solutions are :if $n$ is odd we have $\frac{(n-1)^2}{2}$ if $n$ is even then $\frac{(n-1)^2+1}{2}$ The solution is certain higher: we find for $n=1,2,3,4$ resp. $2,6,12,20$ $(=n(n+1))$ , because here we can full in all squares (there are there for each $n$ $2n(n+1)$ when we calculate that. The way to the solution: Divide the $2n*2n-square$ in $4$ $n*n-$suares. In this squares, we have $\frac{n(n+1)}{2}$ litle squares, when we colour this in the chesscoloring (black, white,...), we have ${\frac{(n+1)}{2}^2}$ black (the corner is black) and $\frac{n^2-1}{4}$ white squares. This mean we have $\frac{n+1}{2}$ black ones more, we can only use $2$ with an other litle square of the $n*n-squares.$ So we have $2(n-3)$ litle squares we can't fill in. We get $n^2+3$ rectangles we can set in the picture. One remark; this formula is other for only $3.$ Use we the same strategy, we find if $n$ is even, we can fill in the whole picture and then the answer is $n^2+4.$ Here the formula doesn't work for $2$ Edit: We can write the answer as $n(n+1)-2\lfloor{\frac{n-3}{2}}\rfloor$ where the floorfunction is 0 if the number is negative (wording of Alberi1)

Problem assumes that we remove $2(i-1)$ squares if $i\leq n$, and $2(2n-i)$ squares if $i>n$. Divide the entire board into 4 quadrants each containing $n^2$ unit squares. First we note that the $2$ squares on the center on each of the $4$ bordering lines of the board can always be completely covered by a single tile, so we can count in the first and last unit squares (which are diagonally opposite) of each quadrant as being filled in completely by a tile. So in each quadrant we have: if $n$ is even, there are exactly $(n-4)/2$ unit squares which cannot be filled by the tiles and if $n$ is odd, there are exactly $(n-3)/2$ unit squares which cannot be filled by the tiles. Above can be seen by drawing a diagram and noticing that alternate columns have even and odd number of unit squares (leaving a unit square uncovered by tiles in odd numbered blocks of columns). Also, note that the total number of unit squares which were removed from each quadrant = $(1 + 2+ 3 + ... n-1) = n(n-1)/2$ Let us consider the 2 cases for parity of $n$: $Case 1: n$ is even for $n = 2$, it can be seen easily that we can use a maximum of $6$ tiles. for $n \ge 4:$ Total number of squares that cannot be filled in each quadrant is: $n(n-1)/2 + (n-4)/2 = (n^2 - 4)/2$ So total number of squares that cannot be filled on the entire board = $2(n^2 - 4)$ So total number of squares that CAN be filled completely by the tiles = $4n^2 - 2(n^2 - 4) = 2n^2 + 8$ So the maximum number of tiles that can be used = $(2n^2 + 8)/2 = n^2 + 4$ $Case 2: n$ is odd for $n = 1$, it can be seen easily that we can use a maximum of $2$ tiles. for $n \ge 3:$ Total number of squares that cannot be filled in each quadrant is: $n(n-1)/2 + (n-3)/2 = (n^2 - 3)/2$ So total number of squares that cannot be filled on the entire board = $2(n^2 - 3)$ So total number of squares that CAN be filled completely by the tiles = $4n^2 - 2(n^2 - 3) = 2n^2 + 6$ So the maximum number of tiles that can be used = $(2n^2 + 6)/2 = n^2 + 3$