math_comb01 wrote: All the squares of a $2024 \times 2024$ board are coloured white. In one move, Mohit can select one row or column whose every square is white, choose exactly $1000$ squares in that row or column, and colour all of them red. Find maximum number of squares Mohit can colour in a finite number of moves. is this a typo? Bold = corrected version

I think It was an easy construction 2024x1000 and 1000x1024

Assume that $1000$ squares in the same row was colored in the first turn, then at most $2024-1000=1024$ columns get to have $1000$ of its squares colored. So total number of colored squares has maximum \[1000\times2024+1024\times1000=3048000.\]

why have u multiplied by 1024 additionally (he had an extra 1024 earlier)

I believe that all these solutions above are incomplete, because we have not proved that it is the maximum value.

No its proved

Proposed by Pranjal Srivastava

This was first ever in my life I used the word trivial while writing a solution . While writing up during test, I had to continuously strike everything off and start writing from scratch due to messing up ordering of lemmas. Being frustrated, I called the bound for the maximal colored cells using column moves trivial. We generalize the problem by taking $n=2024$ and $k = 1000$. I claim that the answer is $k(2n-k)$. For our current conditions, the value turns out to be $3048000$. For the construction, firstly we can fill the topmost $k$ cells of each column. Then we can fill the rightmost $k$ cells of each of the remaining rows. This gives us $kn + k(n-k) = k(2n-k)$ shaded cells. Now we prove the bound. Call a move on some row as row move. Define column move similarly. Note that if a row move is already applied on some row, then we cannot apply any row move on it for the second time. Similarly for the columns too, we have that there are at most $1$ column moves that can be made in a column. Now WLOG assume the first move is a column move (otherwise just rotate the board). This restricts the $k$ rows containing a red cell from the first column move from giving any row move on them. Thus there are $n-k$ possible rows in which we can give a row move. Since in each move we color exactly $k$ many cells, so at most we can color $k(n-k)$ many cells using just row moves. Now note that we have $n$ columns and we can give at most $1$ column move in each of them. So we can color at most $nk$ many cells using just column moves. Thus in total, we can color $k(n-k) + nk = k(2n-k)$ many cells by using both row moves and column moves.

namanrobin08 wrote: I believe that all these solutions above are incomplete, because we have not proved that it is the maximum value. Is there anything wrong with my solution?

Quantum-Phantom wrote: Assume that $1000$ squares in the same row was colored in the first turn, then at most $2024-1000=1024$ columns get to have $1000$ of its squares colored. So total number of colored squares has maximum \[1000\times2024+1024\times1000=3048000.\] That's just the contruction. You haven't proved that this is the maximum possible value? How are you sure there is no better way to fill the grid?

Anulick wrote: Quantum-Phantom wrote: Assume that $1000$ squares in the same row was colored in the first turn, then at most $2024-1000=1024$ columns get to have $1000$ of its squares colored. So total number of colored squares has maximum \[1000\times2024+1024\times1000=3048000.\] That's just the contruction. You haven't proved that this is the maximum possible value? How are you sure there is no better way to fill the grid? They did prove it's the maximum look closely

Call a row/column "intact" if all of it's squares are white, and "ruined" otherwise. Let's assume on the first move we colored a column, this would ruin $1$ column and $1000$ rows, and gives $1000$ red squares. Now there are $2023$ intact columns and $1024$ intact rows, which means we can't get more than $1000(1+1024+2023)=3048000$ red squares. A construction is given by coloring the top $1000\times 2024$ rectangle, then color the bottom left $1024\times 1000$ rectangle, leaving the rest of the squares to be white, this would gives $3048000$ red squares.

If you start colouring by picking a row. After you colour a row atmost $1024$ columns could be coloured and the maximum number if rows which could be coloured is $2024$, so the maximum amount of cells which could be coloured is $3048\cdot 1000$. For construction just take the first thousand cells from left to right in each row and colour them and then pick the columns (from the $1001$th one to the $2024$th one) and colour them just as you like.That finishes the proof $\blacksquare$

Answer is 3048000 by two 1000x2024s Bound given as max number of moves possible $= 2024 \cdot 2 - 1000 = 3048$, and each move adds $1000$ red squares

This was the easiest problem on the test I think so

mannshah1211 wrote: Anulick wrote: Quantum-Phantom wrote: Assume that $1000$ squares in the same row was colored in the first turn, then at most $2024-1000=1024$ columns get to have $1000$ of its squares colored. So total number of colored squares has maximum \[1000\times2024+1024\times1000=3048000.\] That's just the construction. You haven't proved that this is the maximum possible value? How are you sure there is no better way to fill the grid? They did prove it's the maximum look closely Not how maximization proofs work. I am near certain based on USAMO 1998/4 that you need a rigorous proof for such a question. While it is easy, it is also a fake solve trap. A possible answer would be as follows: In a $n \times n$ grid, Call a row/column bad if it has at least one red square. After the first move, there are exactly $k+1$ bad rows and columns: if a row was picked, then that row and the $k$ columns corresponding to the chosen squares are all bad. Any subsequent move increases the number of bad rows/columns by at least 1. Since there are only $2n$ rows and columns, we can make at most $2n - (k + 1)$ moves after the first one, and so at most $2n - k$ moves can be made in total. Thus we can have at most $k(2n - k)$ red squares.

Fair I suppose. In any case though, this problem is pretty trivial

Is this valid? It is easily observed that the order of the moves does not matter, since each move colours disjoint cells. Then, WLOG assume the first move is a column. The cells are $a_1,a_2,\ldots a_{1000}$ ($a_i$ non necessarily equal to $i$). Now, he cannot colour row no.s $a_1,a_2,\ldots a_{1000}$, so it is optimal if he colours these thousand cells in all columns. Then, he can colour 1000 cells in the remaining 1024 rows.

D_S wrote: Is this valid? It is easily observed that the order of the moves does not matter, since each move colours disjoint cells. Then, WLOG assume the first move is a column. The cells are $a_1,a_2,\ldots a_{1000}$ ($a_i$ non necessarily equal to $i$). Now, he cannot colour row no.s $a_1,a_2,\ldots a_{1000}$, so it is optimal if he colours these thousand cells in all columns. Then, he can colour 1000 cells in the remaining 1024 rows. I'm sorry, but no. Reordering the moves isn't valid, because say you colored the 1st, 2nd, ..., 1000th cells in the 1000th column red, and then colored 1st, 2nd, ..., 1000th cells in the 1001th row red. This is valid. But, after reordering, you can't do the first move after the second, because the 1000th column already has a red cell in it. But, assuming that the first move is a column is indeed valid, so I think you should get most of the points for it (the correct justification is to rotate the board, because rotation doesn't change anything).

I wrote color the 2024 columns with red and then color then remaining 1024 rows. For the construction part. This is valid Right?

lelouchvigeo wrote: I wrote color the 2024 columns with red and then color then remaining 1024 rows. For the construction part. This is valid Right? If you have provided the proof, you'll probably get 17. Or else, nothing. I am predicting that only construction will not carry any marks.

Yes i have given the proof

My solution - Consider a row/column with all white cells as "useful" and a row/column with at least one red cell as "useless". Before move 1, useful rows + useful columns = 2024+2024 = 4048. After the first move, WLOG assume all cells he colours are in 1 column, then useful columns = 2024-1 = 2023 and useful rows = 2024-1000=1024. Sum is 3047. On each move, at least 1 useful row/column becomes useless, so a maximum of 3047 moves can be done after move 1, giving us the maximum bound of 3048 moves. Forming a construction for 3048 moves is trivial.

Anulick wrote: mannshah1211 wrote: Anulick wrote: That's just the construction. You haven't proved that this is the maximum possible value? How are you sure there is no better way to fill the grid? They did prove it's the maximum look closely Not how maximization proofs work. I am near certain based on USAMO 1998/4 that you need a rigorous proof for such a question. While it is easy, it is also a fake solve trap. A possible answer would be as follows: In a $n \times n$ grid, Call a row/column bad if it has at least one red square. After the first move, there are exactly $k+1$ bad rows and columns: if a row was picked, then that row and the $k$ columns corresponding to the chosen squares are all bad. Any subsequent move increases the number of bad rows/columns by at least 1. Since there are only $2n$ rows and columns, we can make at most $2n - (k + 1)$ moves after the first one, and so at most $2n - k$ moves can be made in total. Thus we can have at most $k(2n - k)$ red squares. No, the proof is correct, the only thing left to say is that after coloring a row/column you cannot do it again (which is trivial). The way he proves it is exactly how you prove the general case. If you notice, the proofs of @kamatadu and @Quantum-Phantom are the same.

Answer: 3048000 Construction: Mohit should color the first $1000$ cells in each of the rows and then color $1000$ cells in each of the last $1024$ columns. Bound: WLOG assume Mohit makes his first move in a row. Then in the future he can make at most $2024-1000=1024$ future moves in a column. Thus at the end there can be at most $1000(2024+1024)=3048000$ red cells.

OG! We claim answer is (2024x2-1000)x 1000 =3048000 \ Proof that this is the maximum: THERE ARE 2024 COLUMNS AND 2024 ROWS, SINCE WE CAN colour each row or column exactly once, there fore we are permitted to do at most 2024+2024=4048 moves. In the first move let us say WLOG we chose a row then there are 1000 sqaures in that row that are coloured, each square corresponds to a unique column, so the 1000 squares correspond to 1000 columns, now note that in any subsequent moves we can't chose these 1000 columns, as they already have 1 square coloured due to the first move. So since we can't chose these 1000 columns, we are left with 4048-1000 = 3048 moves and thus we can colour at most 3048000 squares. \ Construction: Construction: This is trivial, first select all 2024 rows and colour the leftmost 1000 squares of all these rows. Now select the rightmost 1024 columns and colour any 1000 squares in each of these columns. Thus, we have 2024x1000+1024x1000=3048000 colored squares as desired. Remark: For an $n \times n$ grid, where we can colour only $k$ squares in a non-coloured row/column, the answer is $k(2n-k)$

First move :- WLOG column move -> 1000 red squares , removing the possibility of picking the rows with the red squares so 2024 - 1000 = 1024 rows can maximally be picked (this follows from the fact we cant paint the same row (or column) twice ). Now notice we can pick at most 2023 columns of which we have picked 1 alrdy. So maximum no. of squares we can paint red is (1024 + 2024)1000 = 3048000.

i dont know am i fakesolved or not ? SOLUTION: if a row or column have 0 red square then we define the "value" of this row or column =0 else =1 it is easy to see that the total value of this graph initially is 0 and the maximum value of the graph is 2*2024=4048 and our first move will let this value increase to 1001 inevitably the moves after the first move will let the value of the graph increaes at least 1 so it is easy to say that we can only take 4048-1001+1=3048 moves?

Assume we have colored $x$ rows and $y$ columns. Then the number of red squares $S$ is less than or equal to $k(x+y)$, where $k=1000$ in our problem. Also note $x<=n$,$y<=n-k$ Proof: First claim is trivial, if $y>n-k$ , we can assume first move was a row move otherwise just rotate the board. Then atleast $k$ rows are non-empty or $y<=n-k$, a contradiction. Combining these two I get $S<=k(2n-k)$ and I can easily show the upper bound is attained by coloring the first $k$ cells of each of the $n$ row, and then coloring each of the bottommost $k$ cells of the $n-k$ columns. Is this a fakesolve???As this seems too good to be true and I am not experienced with combinatorial proofs

I have discussed this question in my INMO 2024 video on my channel "little fermat". Here is the Video

the number of red squares is equal to $1000$ times the number of moves therefore, we just need to maximize the number of moves we claim that the maximum number of moves is $2024+1024=3048$. this is achievable by just coloring the first $1000$ squares of all $2024$ rows, and then doing moves on the last $1024$ columns. after our first move, we "block" $1000$ rows/columns which are perpendicular to the row/column we picked. since there are a total of $2024+2024=4048$ rows and columns, and $1000$ are blocked, this proves the maximum of $4048-1000=3048$ moves. therefore, the answer is $1000\cdot 3048=\boxed{3048000}$