A positive integer $k$ is given. Initially, $N$ cells are marked on an infinite checkered plane. We say that the cross of a cell $A$ is the set of all cells lying in the same row or in the same column as $A$. By a turn, it is allowed to mark an unmarked cell $A$ if the cross of $A$ contains at least $k$ marked cells. It appears that every cell can be marked in a sequence of such turns. Determine the smallest possible value of $N$.
Problem
Source: All-Russian Olympiad 2018
Tags: combinatorics, Hi
25.04.2018 04:20
Here is a currently incomplete solution: Call an $x$ stair to be a collection of cells such that there are x columns where there is 1 cell in the first column, 2 in the second, ..., x in the xth column.. If $k=2x$ is even, then I claim the minimum $N$ occurs when $N=x(x+1)$. We can confirm this works by considering two $x$ stairs of the same orientation such that their diagonals line up to form a long diagonal of side length $k$ If $k=2x+1$ is odd, then I claim the minimum $N$ occurs when $N=(x+1)^2$. We can confirm this works by considering an $x$ stair and an $x+1$ stair of the same orientation such that their diagonals line up to form a long diagonal with side length $k$ Now, assume there is a smaller value of $N$. Consider $C$, the set of all columns in which one of the initial cells lie in, and $R$, the set of all rows in which one of the initial cells lie in. In order for a cell that lies in a column outside of $C$ to become marked, then there must be at least $k$ other cells in its row, which means there are at least $k$ elements in $C$ and in $R$ Now, let us just "squeeze" the intersections between the elements of $C$ and $R$ in order to get an $m$ by $n$ rectangle, where $m, n\ge k$ We just need to prove it is impossible for $N$ to be less than our conjectured values.
26.04.2018 17:45
I completed based on lifeisgood03's post! Let $R$ be the $m\times n$ rectangle as lifeisgood03 mentioned. Let $c_1$ be the first cell in $R$ which mark first time. Then, we color cross of $c_1$ red. When we mark $c_1$, there are at least $k$ originally marked cell among cross of $c_1$. Let $c_2$ be the first uncolored cell in $R$ which mark first time. Then, we color cross of $c_2$ red. There are 2 colored cell on the cross of $c_2$. When we mark $c_2$, there must be at least $k$ marked cell among cross of $c_2$ and at most 2 cells (of colored cell) could be originally unmarked cell. Thus, there are at least $k-2$ originally marked cell among cross of $c_2$. Let $c_3$ be the first uncolored cell in $R$ which mark first time. Then, we color cross of $c_3$ red. In the same reason, there are at least $k-4$ originally marked cell among cross of $c_3$. We continue this procedure defining $c_4$, $c_5$, $\ldots$ and we find $k-6$, $k-8$, $\ldots$ originally marked cell among cross of these cells. Therefore, we must have $k+(k-2)+(k-4)+\cdots$ originally marked cells. Note: We must discuss the case that after defining $c_1, c_2, \ldots, c_i$ , we couldn't find $c_{i+1}$ for some $i$. In this case, after defining $c_i$, every uncolored cell is originally marked and there are $(n-i)^2$ originally marked cells. Thus we must have $k+(k-2)+\cdots+(k-2(i-1))+(n-i)^2$ originally marked cell. This value is too large and we can skip this case.
05.07.2018 22:14
maybe I am being dumb but can't we just use FMID to show the bounds in the second comment is optimal?Here is a sketch: First assume $k=2x$ WLOG there exist a row with at least $x$ marked squares.Delete that row now you have a configuration that satisfy for $2x-1$ so if we had less than $x(x+1)$ now we have less than $x^2$ marked cells when $k=2x-1$ which is a contradiction.The same can be done with odd $k$. EDIT:Thanks to Kayak I understood that this is not FMID but just induction.
04.01.2019 02:51
Taha1381 wrote: maybe I am being dumb but can't we just use FMID to show the bounds in the second comment is optimal?Here is a sketch: First assume $k=2x$ WLOG there exist a row with at least $x$ marked squares.Delete that row now you have a configuration that satisfy for $2x-1$ so if we had less than $x(x+1)$ now we have less than $x^2$ marked cells when $k=2x-1$ which is a contradiction.The same can be done with odd $k$. EDIT:Thanks to Kayak I understood that this is not FMID but just induction. correct me if im wrong, but is it circular logic to prove k= 2x by showing it is a contradiction of k=2x-1 case, but proving the k=2x-1 case will require proving the k=2x-2 case?
26.04.2019 01:04
Can someone explain what lifeisgood03 means when saying to Quote: "squeeze" the intersections between the elements of $C$ and $R$ in order to get an $m$ by $n$ rectangle, where $m, n\ge k$ . I can't quite visualize this. Also, what does toshihiro shimizu mean when he says let Quote: $c_1$ be the first cell in $R$ which mark first time
08.07.2019 05:45
Can someone confirm the validity of this solution? I claim the answer is $k + (k-2) + \dots $. A construction is marking one "diagonal" side of a $k\times k$ checkerboard given that diagonal is black. This works because the entire checkerboard will eventually be covered, thus covering the entire board. We call a $k$ configuration a configuration of marked squares such that they can mark the whole grid if a square is marked if its cross has $k$ marked squares. We proceed by induction for minimality. The base cases of $k = 1, 2$ are easy, first take one marked square for $k = 1$ and then take any two squares not in the same row for $2$, and since you must choose at least $k$ squares, these are obviously minimal. Now assume that the result has been shown for all $j$ such that $j<m$ for some $m >2$. We will now show the result is true for $m$. Consider a configuration that eventually marks the whole board if we mark a square if its cross contains $m$ marked squares. Let there be $r$ rows that initially have marked squares and $c$ columns that initially have marked squares, call these \textit{relevant} rows and columns. We must have $r, c \geq m$, otherwise we clearly can't mark all the rows and columns otherwise. Thus, unmark squares so that eventually we have unmarked at most one square from each relevant row and column until you have unmarked as many squares as possible and you still have a valid $m-2$ configuration, which is clearly possible because every $m$ configuration is a $m-2$ configuration. Assume for contradiction we have not unmarked at least $m$ squares, and we have not unmarked a square from relevant row $R$ (or relevant column $C$, it's the same either way). We should be able to tile every square in the grid, and since we have removed at most one square from each column, we can arbitrarily remove a square from row $R$ unless each column already has a square removed. But that implies we have already removed $m$ squares because there are at least $m$ relevant columns. Therefore we have to have removed at least $m$ squares, and thus the minimum number of squares for a $m$ configuration is $m$ plus the minimum number of squares for a $m-2$ configuration.
21.04.2020 18:59
Bumping it
27.08.2020 15:38
DragonFire1024 wrote: Can someone confirm the validity of this solution? Me too since I think that my solution is too simple. The answer is $m(m+1)$ for $k=2m$ and $m^2$ for $k=2m+1$ Construction: For $k=2m$ we take two ladder with dimension $m$. We place them on the checker board so that none of the cells from the two ladders share a row or column. For $k=2m+1$ we take a ladder with dimension $m$ and another one with dimension $m+1$. It is straightforward to see that they satisfy the condition. Proof of minimality: Let $f(n)$ be the minimal number for $k=n$ We use induction. Notice that there exists a row and column which contained at least $n$ marked cells. Remove that row and column, then the remaining board satisfies the condition for $k=n-2$. Hence $$f(n)\geq f(n-2)+n$$from which we deduce the bound.
27.12.2021 22:50
toshihiro shimizu wrote: I completed based on lifeisgood03's post! Let $R$ be the $m\times n$ rectangle as lifeisgood03 mentioned. Let $c_1$ be the first cell in $R$ which mark first time. Then, we color cross of $c_1$ red. When we mark $c_1$, there are at least $k$ originally marked cell among cross of $c_1$. Let $c_2$ be the first uncolored cell in $R$ which mark first time. Then, we color cross of $c_2$ red. There are 2 colored cell on the cross of $c_2$. When we mark $c_2$, there must be at least $k$ marked cell among cross of $c_2$ and at most 2 cells (of colored cell) could be originally unmarked cell. Thus, there are at least $k-2$ originally marked cell among cross of $c_2$. Let $c_3$ be the first uncolored cell in $R$ which mark first time. Then, we color cross of $c_3$ red. In the same reason, there are at least $k-4$ originally marked cell among cross of $c_3$. We continue this procedure defining $c_4$, $c_5$, $\ldots$ and we find $k-6$, $k-8$, $\ldots$ originally marked cell among cross of these cells. Therefore, we must have $k+(k-2)+(k-4)+\cdots$ originally marked cells. Note: We must discuss the case that after defining $c_1, c_2, \ldots, c_i$ , we couldn't find $c_{i+1}$ for some $i$. In this case, after defining $c_i$, every uncolored cell is originally marked and there are $(n-i)^2$ originally marked cells. Thus we must have $k+(k-2)+\cdots+(k-2(i-1))+(n-i)^2$ originally marked cell. This value is too large and we can skip this case. I think wrong solution, bcs initially marked cells can be computed several times
12.07.2023 16:36
The answer is $\lceil \tfrac{k}{2}\rceil+\lceil \tfrac{k-1}{2}\rceil+\cdots+\lceil \tfrac{1}{2}\rceil$. Construction: Checkerboard color the plane and then take some $k \times k$ isosceles right triangle whose hypotenuse is all colored. Then mark every colored cell in this triangle, which counting by rows clearly gives the answer. It is not hard to see that we can color in the entire triangle (starting from the "$90^\circ$ angle"), so then we can color a $k \times k$ square, so then we can color $k$ rows and $k$ columns in the plane, so then we can color the entire plane. Bound: Clearly we must be able to make some starting move, so some row or column has at least $\lceil \tfrac{k}{2}\rceil$ marked cells. Our job is made easier if we take this row or column and fill it in entirely "for free", but then if we hide this row/column we are solving the problem for $k-1$, so by induction we are done, since the base case of $k=1$ is trivial. $\blacksquare$
17.11.2024 18:11
But how can k be non zero unless atleast one cell is marked on the chess board
17.11.2024 18:13
Inshaallahgoldmedal wrote: But note that we want minimum value of N so we should neglect other cases