AoPS - Problem

goo

18.01.2013 02:15

The best configuration I could find consists of 36 squares; but without any proof (or even hint) of optimality yet

mlequi

18.01.2013 03:25

I could find $40$. edit : it is wrong.

chaotic_iak

18.01.2013 16:37

I've found one with $39$ (X's are centers of blocks): .XX.X.XX. XX.X.X.XX X...X...X .X.X...X. X.X.X.X.X .X...X.X. X...X...X XX.X.X.XX .XX.X.XX. EDIT: Ok I also miss the all squares covered condition. ...that also brings me to an idea. Suppose that instead of a 10x10 grid, we have a 9x9 lattice grid where we want to mark points on them, but we have four forbidden configurations of marked points (including rotations): ... ..X ..X X.X XXX XX. XX. .X. ... .X. ..X X.X By the first configuration only, we have a bound of $54$ (every 3x1 rectangle has one non-marked point). If a 3x3 square has 6 points, then it must be this or its rotation (use brute force, considering that first configuration): XX. X.X .XX which means all 12 points adjacent to that square are not marked. Suppose that we divide the 9x9 grid to 3x3 boxes, and one of the boxes has the above configuration. XX.### X.X### .XX### ###OOO ###OOO ###OOO We can rotate to make sure that it has a neighbor to its right and its down (marked with number signs above). Now, note that the new squares that are marked dots are indeed dots; they can't have any marked point: XX..## X.X.## .XX.## ...OOO ###OOO ###OOO (yes, we can have the rotation of the offending square, but the result is the same; you can verify this) Now each 2x3 number signs rectangle can contain at most 4 marked points by first configuration, so in total these three squares can contain at most 14 marked points, which is less than 15 points that we get if all of these three squares contain at most 5 points. So our bound is currently $45$, since either all nine boxes have at most 5 points each, or any box has 6 points (cannot be more) which cause many other boxes to have only at most 4 points. Now I'm thinking whether that bound can be reduced or not...

MellowMelon

19.01.2013 00:41

Note: the below solution is wrong; it misses the condition that the blocks must cover the whole grid. See my next post for a possible fix. Here's how to get 42, using chaotic_iak's notation which I also found was a good way to phrase the problem: XX.XX.XX. XX.XX.X.X .......XX XX.XX.... XX.X.X.XX ....XX.XX XX....... X.X.XX.XX .XX.XX.XX I am not 100% sure this proof of optimality is correct, but here goes. This is based on a recursion that decreases the grid size by 1.5 in both directions. Notice that the notation above relies on considering the 9 by 9 array of vertices. The key realization is that the vertices and cells behave identically in the problem. The recursion here will actually swap their roles in the subcase with reduced grid size, which is why it's rather tricky to find. To elaborate on how vertices/cells are the same, notice that we can think of this problem as rather than laying 2 by 2 blocks all of which are needed to cover the board, we can think of this as placing matchings of a grid cell and an interior vertex. The interior vertex represents the center of a placed block, and the matched grid cell represents the cell of the board that only it covers. Furthermore, when we've placed a matching, we cannot use any other cell touching that vertex in a matching, and we cannot use any other vertex touching that cell. These are all the conditions we need to form a problem equivalent to the original one.

Let $S_k$ be the maximum number of matchings that can begotten $(3k+1) \times (3k+1)$ grid of cells (with corresponding $3k \times 3k$ grid of interior vertices). Clearly $S_0 = 0$ since there are no vertices to be matched. We now show that $S_k = S_{k-1} + (8k-2)$. This will obtain $S_3 = 42$, solving the problem. There's a lot of details to check while doing this, so I'm going to leave some of the more straightforward steps out. First, in a $(3k+1) \times (3k+1)$ grid, you can show that the maximum number of matchings you can have which use cells on the edge of the grid is $8k-2$. At most $2k$ cells on each edge by chaotic_iak's forbidden 1 by 3 pattern, but you need to use two corners to get everything to fit so 2 must be subtracted. Next, suppose we use a cell which is not on the border but is one cell away from it. Then you can show, smoothing style, that it can be pushed out to the border in a way that creates strictly less constraints on the remaining matchings than before. This requires checking some cases but is not hard. So we may WLOG assume none of these cells are used in any matching. Or rather, we can say that there are at most $8k-2$ matchings which use cells which are on the border or one away from the border. Now strip off all the grid cells that are either on the border or one away from the border, and also strip out all the interior vertices touching border cells. We lose at most $8k-2$ matchings when we do this. What's left? A $(3k-2) \times (3k-2)$ of vertices with corresponding $(3k-3) \times (3k-3)$ grid of interior cells, which satisfies all the same conditions as the original problem. Swap the role of vertices and cells and we have an instance for $k-1$, which by definition has $S_{k-1}$ maximum matchings that can be put on it. This completes the proof of the recursion.

MellowMelon

19.01.2013 01:43

I have little interest in trying to fully solve the correct version of the problem, which seems needlessly more complicated (although I suppose the one I solved is really awkward to state), so here's a sketch of how I believe my work above can be corrected: - The answer should be 38: XX.XX.X.X XX.XX.X.. .......XX XX.X.X... XX.....XX ...X.X.XX XX....... ..X.XX.XX X.X.XX.XX - There are two cases to the recursion now. If you've done the recursive step an even number of times (case A), you need all cells to be used. If you've done it an odd number of times (case B), you need all interior vertices to be used (which is so easy to do it can be ignored; there's too few of them). - Case B works exactly the same as in my solution. You get an extra $8k-2$. - For case A, the smoothing argument is even easier; any matching that uses a cell one away from the border has to cover the corresponding edge cell, in order for all cells to be used. So you can just switch which cell the matching uses without moving anything. - When computing the edge cells, case A requires you use all four corners. This makes the term you add be $8k-4$ instead of $8k-2$. Combining all this, you should get $(8 \cdot 3 - 4) + (8 \cdot 2 - 2) + (8 \cdot 1 - 4) = 38$ for the bound.

goo

19.01.2013 17:16

First of all, big kudos to chaotic_iak for introducing his notation for the positions of the squares on the board! In order to deal with the "board needs to be covered completely" condition, it should be sufficient to surround the 9x9 board by a frame consisting of empty squares and add one more forbidden configuration of 2x2 empty squares. Now, on the constructive side: I performed some computer search and it seems I've got some bad news for MellowMelon ; 39 looks to be possible in the original version of the problem. The search has not been exhaustive, so further improvements might be possible.XX.XX.X.X XX.X.X.XX ....X.... XX.X..X.X X.X..XX.X .X..XX... X..XX..XX .X....X.. XX.XX.X.X

Algie

29.01.2013 16:31

We call a cell unique, if it is covered by exactly one block. Each block covers its own unique cell. We divide square $10\times 10$ in $2$ parts: central square $6\times 6$ and a "frame" around it. It's not difficult to establish that there are no more than $20$ blocks, which are entirely situated inside the "frame". Also note that if a block is situated (maybe, not entirely) in square $6\times6$ then its unique cell is situated there too. Suppose that there are more than $19$ blocks, which are situated (maybe, not entirely) in central square $6\times 6$. We'll divide this central square in four squares $3\times 3$. Each of it has a central cell, which is covered by a block entirely situated in the square $3\times 3$. Note that there can't be a unique cell, which is situated between $2$ unique cells, (if all these three unique cells are covered by different blocks). So each of these 4 squares $3\times 3$ has exactly $5$ unique cells, which are covered by different blocks. $4$ of these unique cells are situated like in the picture (1). (The square can be rotated). Consider 2 cases $1)$ There exists a square $3\times 3$, which has corner-unique cell situated in center square $2\times 2$ of square $6\times 6$. Then we get the situation like in picture (2). Contradiction. $2)$ There doesn't exist a square $3\times 3$, which has corner-unique cell situated in center square $2\times 2$ of square $6\times 6$. Then we get the situation like in picture (3). Contradiction. So there are no more than $19$ blocks, which are situated (maybe, noy entirely) in central square $6\times 6$. Therefore $n \leq 20 + 19 =39$. Picture (4) contains an example.

Attachments:

alexiaslexia

21.12.2020 09:42

Closely resembles a puzzle rather than a $``\text{theoritical}"$ combinatorial problem. Was convinced that $38$ is the answer, when an extra block can be squeezed. A brief introduction of notations: We represent a $2 \times 2$ block by its center, which coincides with some vertex of the grid; and following the problem condition, each block has a $\textbf{redeeming cell}$ --- at least 1 out of 4 of the cells it covers which is only covered by that block. So, with each block's presence, we draw an arrow from its center to the $\textbf{redeeming cell}$'s center. Aside from that, say the grid is formed by $22$ lines: $x = i$ for $0 \leq i \leq 10$ and $y = j$ for $0 \leq j \leq 10$, and represent each cell by its lower left corner's coordinate. This means that the lowest and leftmost square has $``\text{ID}"$ (0,0), and the highest and rightmost square is the $(9,9)$ square. Whenever we say that a set of blocks cover a grid, unless stated otherwise, we always assume that it has to cover the entire grid, and a removal of one block will result in an uncovered grid (as with the problem statement.) $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{\text{Reduction to 6 by 6.}}$ We have the following Claims; There must be a block with center $(1,1)$, $(1,9)$, $(9,1)$ and $(9,9)$. Given a $2 \times 6$ grid, where its block centers must lie on its horizontal midline. Then, there exists either $3$ or $4$ blocks in that grid. The maximum total number of blocks is $20+k$, where $k$ is the maximum number of blocks which can be placed in a $6 \times 6$ grid. There's a catch here: that block centers may lie in the grid's boundary (so squares can lie in a $8 \times 8$ grid, but only the $6 \times 6$ grid is required to be whole-ly covered.) $\color{green} \textbf{\text{Proof 1.}}$ We proceed chunk by chunk: Chunk 1. If one of these blocks are absent, then the corner of the $10 \times 10$ grid corresponding to those blocks are uncovered. Chunk 2. Since there are $12$ squares in a $2 \times 6$ grid, there are at least $3$ blocks to cover them all. However, if there are at least $5$ blocks in that grid, by Pigeonhole Principle, there is a $2 \times 3$ grid which has at least 3 redeeming cells (since each block is matched with a redeeming cell.) It's easy to see that this is impossible. Chunk 3. Consider the 2-width border of the grid (i.e. the squares with does not lie in the $6 \times 6$ center.) Dissecting it into four corner $2 \times 2$ blocks and four $2 \times 6$ grids as above, we get that there must be at least $16$ and at most $20$ blocks there. Consider the redeeming cells of the blocks. We might as well place them on the outermost border of the grid, as when a block's redeeeming cell is located on the second outermost border, the matching square on the outermost border is also a redeeming cell of that block (draw a diagram to convince yourself of this statement.) That leaves us with the second outermost border free of redeeming blocks; and let $k$ be the maximum blocks we can place in the center $6 \times 6$ blocks. Again, we can optimize the placement of the redeeming blocks in the borders to force the existence of $20$ blocks --- because they are uninfluenced by the middle blocks' range. $\blacksquare$ $\color{blue} \rule{25cm}{2pt}$ $\color{blue} \textbf{\text{Further dissections.}}$ Since each block has a unique redeeming cell, say a block belongs to a grid if its redeeming cell is located inside that grid. Dissect the $6 \times 6$ grid into four $3 \times 3$ grids. Then, a $3 \times 3$ grid has at most $5$ blocks belonging to it, and it has to be in the following form:

note that a slight adjustment in squares $(4,5)$ and $(5,4)$ are required to curb the middle intersection of the blocks. This is a valid move since the redeeming cells still follow the same formation. $\blacksquare$ $\blacksquare$ $\blacksquare$

Disclaimer: This problem is so puzzle-oriented, hence the wordy explanation of my Solution. The motivation of said Solution, will of course be doubly wordy, as well --- added with a plethora of configurations which I say to $``\text{lead}"$ to the ultimate configuration. We use a similar notation of blocks, redeeming cells, squares' ID and coordinates as above. $\rule{25cm}{1.5pt}$ Unlike most $\#6$s, this problem has a linear structure at first: it's fairly easy to come up with some Claims using rather straightforward observations (doesn't mean the later parts and the quadruple dissections are as easy.) When $n = 10$ is replaced with $n = 3$, $n = 4$ or $n = 5$, one thing is constant throughout all configurations: the four corners of the grid can only be covered by one block --- so that block must exist. In the first two $n$s, only those blocks can exist, as they alone can completely cover the grid. However, for $n = 5$, it doesn't completely work like that, since the squares $(2,0),(2,4),(0,2)$ and $(4,2)$ have two blocks which can cover them, and the square $(2,2)$ cannot be covered by any of those blocks --- which results in a total of exactly nine blocks. This rough idea brought up the bounding of the $``\text{2-width border}"$ bounding, seeing that the blocks with center $(x,1)$ will cover up sets of 2 squares of $(x,0)$ and $(x,1)$. For example, the $(3,1)$ block covers two squares from $(2,0),(2,1)$ and two squares from $(3,0),(3,1)$, so it makes sense to lump the 2 squares $(x,0),(x,1)$ together. Equivalently, any redeeming cell $(x,1)$ can be moved away to the border in $(x,0)$, because any block which uniquely covers $(x,1)$ will also uniquely cover $(x,0)$. $\rule{25cm}{1.5pt}$ With the outer squares being irrelevant to the inner $6 \times 6$ grid, the important bound lies in how the blocks around the $6 \times 6$ behave. Copying roughly the idea used in the border above, I opted for a $(2,2)$ and a $(2,8)$ block because their redeeming cells seem economically efficient, and I shaped the other blocks to have an (even,even) center, but there's immediately a problem: [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.9] \fill[gray!30!white,shift={(-2,-3)}](2,3)--(2,4)--(3,4)--(3,3)--cycle; \fill[gray!30!white,shift={(-2,2)}](2,3)--(2,4)--(3,4)--(3,3)--cycle; \fill[red!10!white,shift={(-1,-2)}](2,3)--(2,4)--(3,4)--(3,3)--cycle; \foreach \i in {0,1,2,3} \draw[blue,thick](\i,0)--(\i,6); \foreach \j in {0,1,2,3,4,5,6} \draw[blue,thick](0,\j)--(3,\j); \draw[green,thick,shift={(0,0)},->](0,0)--(0.5,0.5); \draw[green,thick,shift={(0,2)},rotate=-90,->](0,0)--(0.5,0.5); \draw[green,thick,shift={(0,4)},rotate=0,->](0,0)--(0.5,0.5); \draw[green,thick,shift={(0,6)},rotate=-90,->](0,0)--(0.5,0.5); \draw[green,thick,shift={(2,0)},rotate=90,->](0,0)--(0.5,0.5); \draw[green,thick,shift={(1,3)},rotate=-90,->](0,0)--(0.5,0.5);\draw[green,thick,shift={(2,4)},rotate=90,->](0,0)--(0.5,0.5); \draw[green,thick,shift={(2,6)},rotate=180,->](0,0)--(0.5,0.5);\draw[green,thick,shift={(3,2)},rotate=180,->](0,0)--(0.5,0.5); \draw[red,semithick,shift={(1,1)}] (-0.13,-0.13)--(0.13,0.13); \draw[red,semithick,shift={(1,1)}] (0.13,-0.13)--(-0.13,0.13); \draw[red,semithick,shift={(1,2)}] (-0.13,-0.13)--(0.13,0.13); \draw[red,semithick,shift={(1,2)}] (0.13,-0.13)--(-0.13,0.13); \draw[red,semithick,shift={(2,1)}] (-0.13,-0.13)--(0.13,0.13); \draw[red,semithick,shift={(2,1)}] (0.13,-0.13)--(-0.13,0.13); \draw[red,semithick,shift={(2,2)}] (-0.13,-0.13)--(0.13,0.13); \draw[red,semithick,shift={(2,2)}] (0.13,-0.13)--(-0.13,0.13); \end{tikzpicture} \begin{tikzpicture} \node at (0,0) {}; \node at (0,2.6) {$\quad \Rightarrow \quad$}; \end{tikzpicture} \begin{tikzpicture}[scale=0.9] \fill[gray!30!white,shift={(-2,-3)}](2,3)--(2,4)--(3,4)--(3,3)--cycle; \fill[gray!30!white,shift={(-2,2)}](2,3)--(2,4)--(3,4)--(3,3)--cycle; \fill[red!10!white,shift={(-1,-2)}](2,3)--(2,4)--(3,4)--(3,3)--cycle; \foreach \i in {0,1,2,3} \draw[blue,thick](\i,0)--(\i,6); \foreach \j in {0,1,2,3,4,5,6} \draw[blue,thick](0,\j)--(3,\j); \draw[green,thick,shift={(0,0)},->](0,0)--(0.5,0.5); \draw[green,thick,shift={(0,2)},rotate=-90,->](0,0)--(0.5,0.5); \draw[green,thick,shift={(0,4)},rotate=0,->](0,0)--(0.5,0.5); \draw[green,thick,shift={(0,6)},rotate=-90,->](0,0)--(0.5,0.5); \draw[red,thick,shift={(2,1)},rotate=90,->](0,0)--(0.5,0.5); \draw[green,thick,shift={(1,3)},rotate=-90,->](0,0)--(0.5,0.5);\draw[green,thick,shift={(2,4)},rotate=90,->](0,0)--(0.5,0.5); \draw[green,thick,shift={(2,6)},rotate=180,->](0,0)--(0.5,0.5);\draw[red,thick,shift={(3,3)},rotate=180,->](0,0)--(0.5,0.5); \end{tikzpicture}");[/asy][/asy] if we do not have a block with center $(3,3),(3,4),(4,3)$ or $(4,4)$, the strategically central square $(3,3)$ will not be covered (hence the formulation in $\color{blue} \textbf{\text{Further dissections}}$, which takes advantage of a block which covers 4 out of 9 squares in a $3 \times 3$ grid.) After I sacrificed the dream of having lots of tight centers, I obtained my first $6 \times 3$ grid with $9$ blocks. Then, another problem surfaced up when I attempted to extend this configuration to a $6 \times 6$ block: how to count the blocks with centers $(5,x)$. Here, the thought to represent a block solely on its redeeming cell came up, because the block largely affects the board condition if it contributes a cell $\textbf{which cannot be occupied by other blocks.}$ --- making the board a bit heavier on other blocks which are supposed to $``\text{belong}"$ there. After roughly an hour of trying, I found two configurations of reference here, with 18 blocks (I abandoned the idea of having four corners being redeeming cells, and took the liberty to start with the block arrangement on the lower left corner.) [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.9] \foreach \i in {0,1,2,3,4,5,6} \draw[blue,thick](0,\i)--(3,\i); \foreach \i in {0,3,4,5,6} \draw[blue,thick](\i,0)--(\i,6); \draw[blue,thick](3,0)--(6,0); \draw[blue,thick](3,6)--(6,6); \foreach \i/\j/\k in {0/1/0,0/3/-90,0/4/0,0/6/-90,1/0/0,2/2/180,2/3/90,2/5/180,3/0/90,3/2/-90,3/3/0,3/5/-90,4/6/-90,5/1/90,5/3/180,5/4/90,6/6/180} \draw[green,thick,shift={(\i,\j)},rotate=\k,->](0,0)--(0.5,0.5); \foreach \i/\j/\k in {0/1/0,0/3/-90,0/4/0,0/6/-90,1/0/0,2/2/180,2/3/90,2/5/180,3/0/90,3/2/-90,3/3/0,3/5/-90,4/6/-90,5/1/90,5/3/180,5/4/90,6/6/180} \fill[green] (\i,\j)circle(2.5pt); \end{tikzpicture} \begin{tikzpicture}[scale=0.9] \fill[red!10!white,thick](4,2)--(4,3)--(5,3)--(5,2)--cycle; \fill[red!10!white,thick,shift={(1,1)}](4,2)--(4,3)--(5,3)--(5,2)--cycle; \foreach \i in {0,1,2,3,4,5,6} \draw[blue,thick](0,\i)--(3,\i); \foreach \i in {0,1,2,3,4,5,6} \draw[blue,thick](\i,0)--(\i,6); \draw[blue,thick](3,0)--(6,0); \draw[blue,thick](3,6)--(6,6); \draw[red,thick](4,3)--(6,3); \draw[red,thick](4,2)--(5,2); \draw[red,thick](5,4)--(6,4); \foreach \i/\j/\k in {0/1/0,0/3/-90,0/6/-90,1/0/0,1/4/-90,2/2/180,2/6/180,3/0/90,3/3/-90,3/4/90,3/6/-90,4/4/0,4/1/90,5/6/180,6/0/90,6/2/180,6/5/180} \draw[green,thick,shift={(\i,\j)},rotate=\k,->](0,0)--(0.5,0.5); \foreach \i/\j/\k in {0/1/0,0/3/-90,0/6/-90,1/0/0,1/4/-90,2/2/180,2/6/180,3/0/90,3/3/-90,3/4/90,3/6/-90,4/4/0,4/1/90,5/6/180,6/0/90,6/2/180,6/5/180} \fill[green] (\i,\j)circle(2.5pt); \draw[orange,thick,<->](4.5,2.5)--(5.5,3.5); \fill[orange] (5,3) circle (3pt); \end{tikzpicture}");[/asy][/asy] $\rule{25cm}{1.5pt}$ After I analyzed how an $18$ can be found (its occurence is rare, too), I concluded that there needs to be 9 redeeming cells both on the right and left $6 \times 3$ grid, and as a bonus, 9 redeeming cells on both the upper and lower $3 \times 6$ grid. It turns out that since a $6 \times 3$ block can be divided further nicely into $3 \times 3$ blocks, I put all my luck in proving and continuing from the $\color{blue} \textbf{\text{Further dissections}}$ section, and the Solution is pretty straightforward from there.

Diego17

18.04.2021 18:21

Here's an interesting question. https://artofproblemsolving.com/community/c6h2523894_hard_combo_question