We say that a black square is row-happy if it's the only black square in its row, and column-happy if it's the only black square in its column. Note that each black square must be at least one of the two. We'll find the maximum $n$ for which we can color $n$ squares without leaving a right triangle. There can be at most $999$ row-happy black squares in the best case. If there are more than $1000$, two of them would be in the same row, contradiction. If there are exactly $1000$, there must be one of them in each row and each row could not contain any other squares, so there would be exactly $1000$ black squares in total. Analogously, in the best case there can be at most $999$ column-happy black squares. Since each square is at least one of the two, there can be at most $1998$ black squares in total. It's easy to find an example for $1998$: color the bottom row and the leftmost column, but leaving the bottom-left corner white. So we can color $1998$ squares without leaving a right triangle, and this is the maximum. Thus the required $n$ is $1999$.

Suppose that there are 1999 or more colored squares. If a colored square shares both a row and a column with another colored square, then we have the required right triangle. So in order for there to be no such right triangle, each colored square must be alone in either its row or column. We say that a colored square A "forbids" a square B if A shares a row with another colored square and shares a column with B, or vice versa. Thus if A forbids B, then B cannot be colored. A square can only be forbidden by two colored squares, one in its row and one in its column. If it is forbidden by three, then two of them must share a row or column and thus one of them cannot be colored. Each of the 1999 colored squares forbids 999 other squares, and so at least M = int(1999*999/2) squares are forbidden. M = int((2000-1)(1000-1)/2) = int((2000000-3000+1)/2) = 1000000-1500 So at most 1500 squares are not forbidden. However, there are 1999 colored squares, so at least 499 of them must be forbidden. Contradiction. Consider a board with 1999 colored squares such that each square in the leftmost column and the bottom row are all colored. Now uncolor the left-bottom corner, leaving 1998 colored squares. Clearly no colored square shares both a row and a column with another colored square, so we have a setup with 1998 colored squares such that no such right triangle can be formed. So n=1999.

Note that switching columns or rows will not change whether there is a right triangle or not, as squares which share the same row or column will still share the same row or column. Now suppose it was possible to color a $ nxn$ board with $ 2n-1$ squares. Since we have $ n$ rows, at least one row contains two black squares. Similarly, at least one column contains two black squares. Call the black squares that share a row $ R_1$ and $ R_2$, and call the black squares the share a column $ C_1$ and $ C_2$. Note that $ C_1$ or $ C_2$ cannot share a column with $ R_1$ or $ R_2$ or else there would be a triangle. Similarly, $ R_1$ and $ R_2$ cannot share a row with $ C_1$ or $ C_2$. Therefore we have four distinct squares. Shuffles the rows and columns in such a way that $ R_1$ and $ R_2$ lie in the first two squares on the first row, and $ C_1$ and $ C_2$ lie on the bottom two squares of the rightmost column. Note that any black square in the column of $ R_1$ or $ R_2$ or the row of $ C_1$ or $ C_2$ would form a triangle. So essentially we use four squares to cut out the leftmost two columns and bottom two rows. We now have $ 2(n-2)-1$ squares to color a $ (n-2)X(n-2)$ board. Continue this operation until we must color a $ 2X2$ board with $ 2(2)-1 = 3$ squares. Contradiction.

MithsApprentice wrote: Find the smallest positive integer $ n$ such that if $ n$ squares of a $ 1000 \times 1000$ chessboard are colored, then there will exist three colored squares whose centers form a right triangle with sides parallel to the edges of the board. I think I seen a very similar problem in st. petesburg´s olympiad.But i don´t remenber the year... But not only there, I think that i´ve seen it more then one time.Anyway, here is my solution:(it is really wweird, i don´t know if the correctors would accept this,but i had to post it fast) 1998 clearly can´t be.i´ll prove that it is 1999.Suppose for absurd that it is not 1999. we´ll have a columm with 2 painted squares.if we have another painjted square in one of these lines ,absurd.so we can "remove" these 2 lines from the board. But , if we have another painted one in this columm,we´l have to eliminate another line.So , to maximize the number of possible painted ones, we´ll have to have the other painted ones in a different columm. we also have to color in such a way that we remove the least possible number of new squares.so the next 2 painted ones will have to be in the same line,but not in the same collum as the first 2 .Continuing in such manner, we see that we will have one last coloring to make .But then we´ll have a triangle.Absurd. So n=1999

MithsApprentice wrote: Find the smallest positive integer $n$ such that if $n$ squares of a $1000 \times 1000$ chessboard are colored, then there will exist three colored squares whose centers form a right triangle with sides parallel to the edges of the board. Let $f(m, n)$ be the answer to this problem for an $m \times n$ grid. I claim $\boxed{f(m, n)=m+n-1}$. Induct on $k=m+n$; here base cases are clear. To see $f(m, n) \ge m+n-1$ take a row and a column and color all cells on them except for their intersection. WLOG, $m \ge n$. If each row has two colored cells, we get $2m>m+n-1$ colors. Else, pick that row with just one colored cell and look at the column containing it. Let there be $s \ge 1$ colored cells on this column. Then, none of the rows containing them can have a colored cell. Delete this column and these rows; "glue" together the rectangular pieces of the board so formed in the natural way to get a new board. For this board, $k \mapsto k-s-1$ so we may conclude that the original can have no more than $k-1$ cells. Our induction is complete. $\blacksquare$

Construction by StanPZ28 We claim that $n=1999$ is the smallest such $n$ such that there is guaranteed to be a right triangle. For $n=1998$, take two lines, one vertical and one horizontal and color every square on those lines except for their intersection. Clearly there are no right triangles, and $1998$ colored squares. Hence, we see that $n\geq1998$. Now we show that $1999$ squares is enough. Denote a square a column square if the square has another colored square in the same column, and define a row square analogously. Furthermore, denote a square to be neither if it is neither a row nor a column square. If a square is simultaneously a row and a column square, then we are done, so assume that this is not the case. Suppose that all the squares are either row or column squares. Let there be $r$ column and $c$ row squares respectively. Since $r+c=1999$, we have that one of $r$ or $c$ must be greater than or equal to $1000$, so we are done, since there must be some "overlap". Now suppose that there are $n$ neither squares. We now have that there are $n$ neither squares, taking up $k$ rows and $k$ columns. Hence we have that there are $1999-k$ rows/columns squares taking up $1000-k$ rows and $1000-k$ columns. Hence, there must be overlap, and we are done. $\square$

(There is a generalized form in the Pranav combinatorics book.) Let a column with more than $1$ shaded square be bad. Firstly find the max shaded squares where we can ever possibly make no right triangle form. Take an $n\times n$ ($n\ge2$) grid and let the number of bad columns be $a$, then the good columns ($0/1$ shaded squares) is $n-a$. If there are no bad columns ($a=0$) then the total number of shaded squares is at most $n-0=n$. If there is at least $1$ bad column: The shaded squares in a bad column can't share a row with another other square otherwise a right triangle forms. In particular the total number of shaded squares in the bad columns is at most $n$, otherwise $2$ (out of $n+1$) of these squares share a row. If there were exactly $n$ of these squares none of the good columns would have any shaded squares since those $n$ squares definitely would take up all $n$ rows. Total shaded squares is $n$. Otherwise there are at most $n-1$ of these squares. The other $n-a$ columns have at most $n-a\le n-1$ squares, giving a maximum of $2(n-1)$. Clearly $2(n-1)\ge n$, thus, we have $2(n-1)$ shaded squares at most if no right triangle ever forms. On the converse, if $m \ge 2n-1$ then we will always find a right angle triangle. For $m = 2(n-1)$ we can construct an example where no right triangle appears, just shade the top row and left column except the top-left corner square. We proved the minimum is $2n-1$, then setting $n=1000$, $2*1000-1=1999$.

The answer is $n = 1999$. For a construction with $n = 1998$, take a punctured L as illustrated below (with $1000$ replaced by $4$): \[ \begin{bmatrix} 1 \\ 1 \\ 1 \\ & 1 & 1 & 1 \end{bmatrix}. \] We now show that if there is no right triangle, there are at most $1998$ tokens (colored squares). In every column with more than two tokens, we have token emit a bidirectional horizontal death ray (laser) covering its entire row: the hypothesis is that the death ray won't hit any other tokens. [asy][asy] size(6cm); for (int i=1; i<=8; ++i) { if ((i-1)*(i-3)*(i-5) != 0) draw( (0.5,i)--(8.5,i), red+1, Arrows(TeXHead) ); for (int j=1; j<=8; ++j) { if ( (i-j)%2 == 0 ) filldraw(shift(i-0.5,j-0.5)*unitsquare, invisible, grey); else draw(shift(i-0.5,j-0.5)*unitsquare, grey); } } draw( (3,2)--(3,7), blue); draw( (5,4)--(5,8), blue); void token(pair P) { fill(circle(P, 0.2), black); } token( (1,1) ); token( (2,1) ); token( (3,2) ); token( (3,6) ); token( (3,7) ); token( (4,1) ); token( (5,4) ); token( (5,8) ); token( (6,5) ); token( (7,3) ); token( (8,1) ); [/asy][/asy] Assume there are $n$ tokens and that $n > 1000$. Then obviously some column has more than two tokens, so at most $999$ tokens don't emit a death ray (namely, any token in its own column). Thus there are at least $n-999$ death rays. On the other hand, we can have at most $999$ death rays total (since it would not be okay for the whole board to have death rays, as some row should have more than two tokens). Therefore, $n \le 999 + 999 = 1998$ as desired.

The answer is $n=1999$. To show that $n=1998$ fails, pick an arbitrary row, an arbitrary column, and color in both. Then uncolor their intersection, which clearly works. Now I will show that $n=1999$ works. Now identify each cell in the chessboard as an ordered pair $(i,j)$ where $i$ represents the column number and $j$ the row number, so the bottom left is $(1,1)$ and the top right is $(1000,1000)$. We can see that such a right triangle exists if and only if there exists some $(i,j)$ such that column $i$ contains at least two colored squares and row $j$ contains at least two colored squares. Suppose FTSOC that there exists some coloring of $1999$ squares and no right triangles are formed. View the coloring column-by-column, so we first color some squares in the first column, then the next, and so on. At some point in time, call a row solitary if there can be at most one colored square in it, otherwise a right triangle is formed. Hence every time we color a column, we create some (possibly zero) solitary rows. Since we cannot color cells lying in already solitary rows, it is clear that no new solitary columns are created by coloring a column with a single square or no squares, and if $k \geq 2$ columns are colored then $k$ new solitary columns are created: one for each square colored in that column. Thus after some number of columns are colored, with $k$ cells being filled in, the total number of solitary rows is equal to: $$k-\text{the number of columns with 1 square colored},$$hence after all the columns are colored there are: $$1999-\text{the number of columns with 1 square colored}.$$Now note that any coloring without right triangles must have at most $998$ columns with one colored cell: $1000$ is impossible since then we only color $1000$ squares, and $999$ is impossible since it implies the row that doesn't have one colored cell has $1000$ cells, and a right triangle can be clearly formed. Hence after the columns are all colored we have at least $1001$ solitary rows, which is absurd since there are only $1000$ rows in the chessboard. Hence such a coloring does not exist, so every coloring of $1999$ squares contains a right triangle. $\blacksquare$

The answer is $n=1999$. To see that $n=1998$ doesn't work, color the 999 squares that are in the topmost row and rightmost column, but not the square in both. It is easy to see that then $n<1998$ doesn't work. Now to prove that $n=1999$ works. For a coloring of 1999 squares, consider the columns where at least 1 square is colored and pick 1 square is each of those columns to be called interesting. Note that there are between at most 1000 interesting squares, each column has at most 1 interesting square, and columns without an interesting square have no colored squares. If all the interesting squares are in the same row, then we can chose any colored squared and it would form a right triangle with 2 interesting squares. So, assume not all the interesting squares are in the same row. For the other 999 (possibly more) colored squares that are not interesting, if any two are in the same row, we are done since each of these colored non interesting square is in the same column as an interesting square. The right triangle is then formed by the two colored non interesting squares in the same row and the interesting square in the same column as one of these 2 squares. The other case is if the 999 colored non interesting squares are all in different rows. Since the interesting squares are in at least 2 rows, one of these 999 colored non interesting squares is in the same row as an interesting square, and by definition of interesting that specific colored non interesting square has to be in the same column as an interesting square as well, so we have the right triangle.

Oops why did this take me like $15$ minutes to solve, but $1$ hour to write up... I'm obviously inexperienced at Olympiad Combo. Also why are all the other solutions so short and appealing, especially Evan's, unlike mine. We claim $n = 1999$ is the answer. Call a chessboard good if it contains a right triangle and bad otherwise. Observe that a chessboard is good if and only if it contains a colored square that has another colored square within its own row and column. Now, we will try to construct bad chessboards. Let a row be singular if it contains exactly $1$ colored square and non-singular if it contains $2$ or more. Notice that in order for a chessboard to be bad, every single colored square within a non-singular row must have $0$ additional colored squares in its own column. Claim: Suppose we are constructing a bad chessboard. If our chessboard has at least $1$ singular row, then the largest possible amount of colored squares within our non-singular rows is $999$. Proof. Since colored squares within non-singular rows must have their own column (distinct from all other colored squares), the result easily follows, as the colored squares located within singular rows could all share a single column. $\square$ Similarly, we conclude that for boards containing $0$ singular rows, the maximum possible amount of colored squares contained within the non-singular rows is $1000$. It's easy to see there exists a bad chessboard for $1 \le n \le 1000$, as we cannot guarantee there will exist a non-singular row (by the Pigeonhole Principle) for these values of $n$. If $1001 \le n \le 1998$, then we can construct bad chessboards as follows: $\bullet$ Color the first $n - 999$ squares of row $1$ from column $1$ to column $n - 999$; $\bullet$ Color the last $999$ squares of column $1000$ (from row $2$ to row $1000$). Obviously, the total number of colored squares (here) is $n$, and we've satisfied all conditions necessary to form a bad chessboard, so we're done. Now, we will utilize contradiction to prove there exist no bad chessboards for $n = 1999$. Claim: If a bad chessboard has $1999$ colored squares, then it must contain exactly $1000$ singular rows. Proof. Suppose we have $0$ singular rows within our chessboard. Now, we have $1999 > 1000$ colored squares left for the non-singular rows of our board, implying a bad chessboard cannot be constructed for this case (due to the corollary of our first claim). Now, assume we have at least $1$ singular row on our chessboard. Then, the largest possible amount of colored squares contained within our non-singular rows is $999$, implying the number of colored squares within our singular rows (for this case) is at least $1999 - 999 = 1000$. Because our chessboard only has $1000$ rows, however, we conclude that exactly $1000$ singular rows are needed for this case. $\square$ The last claim implies there must exist $1000$ singular rows on our board to (possibly) construct a bad chessboard when $n = 1999$. This means the number of colored squares here is just $1 \cdot 1000 = 1000$. Obviously, we have a contradiction as $1000 \ne 1999$, so all chessboards with $n = 1999$ are good and we're done. $\blacksquare$

We offer a stronger claim. Claim: For $a,b\geq 2$, the rectangle $a\times b$ can have at most $a+b-2$ colored cells while not having any right triangles. Proof: . First note that we can always achieve this by covering a full row and full column, minus the intersection. Induction. The base case $2\times 2$ clearly yields at most 2 colored cells. Otherwise, consider the row with the maximum number of colored cells, let this be $M$. If $M=b$, then the maximum number of cells is $b\leq a+b-2$. If $M=b-1$, then we are forced to have at most $b-1+a-1 = a+b-2$ by filling out the final unfilled the row (This is the equality case).Otherwise, the other $b-M$ cells in the row, and the $a-1$ other cells in the column, all cannot be colored. Additionally, by the inductive hypothesis, the maximum number of cells in the remaining $(b-M)\cdot (a-1)$ rectangle is $(b-M)+(a-1)-2$ if $a-1\geq 2$, and $(b-M)\leq (b-M)+(a-1)-1$ if $a-1=1$. Thus, the total is at most \[M + (b-M) +(a-1)-1 = b+a-2\]and we're done. $\square$. This gives us an answer of $1000+1000-2+1 = \fbox{1999}$

We claim that $n=1999$. To see that $n=1998$ fails, pick a cell and color all the cells lying on the same row and column of it, and do not color the picked cell. Thus, there are no right triangles. Now, let $G= A \cup B$ be the bipartite graph of the chessboard, where $A$ is the set of rows and $B$ is the set of the columns. We connect $a \in A$ to $b \in B$ iff their intersection on the chessboard is colored. We will prove that if $|E(G)| \geq 1999$, then $G$ has a path of size $3$ $a-b-c-d$, which clearly implies that there is a right triangle. Thus, suppose for the sake of the contradiction that $|E(G)| \geq 1999$ but $G$ has not a path of size $3$. Then, for every $a \in A$ with $deg (a) \geq 2$, its neighbors have degree exactly $1$. The same is true for $b \in B$ with $deg (b) \geq 2$. Therefore, $G$ is a disjoint union of trees, and $G$ has exactly $2000$ vertices, so if $G$ has more than a tree, there will be less than $2000-1=1999$ vertices. Hence, $G$ is a tree. However, this clearly implies that there will be a size of path $3$ in $G$, implying the desired result. $\blacksquare$

The answer is $1999.$ To show that $1998$ does not work, simply consider the case where the first row and the first column is colored, but not their intersection. Define vertices $R=\{r_1,r_2,\dots, r_{1000}\}$ and $\{g_1,g_2,\dots, g_{1000}\}$ in a bipartite graph where $(r_i,g_j)$ is connected if and only if row $r_i$ and column $g_j$ is colored. Note that if there exists a path with two vertices in $R$ and two in $G$, then there is a $3$-path, implying that there is a right triangle. Assume that we can draw $1999$ edges without creating a $3$-path. Clearly there must be no cycles, so our bipartite graph is a forest. Consider any tree. It may not have two vertices in $R$ and two in $G$, so WLOG assume it has only one vertex in $R$. That means that one the forest has at least two trees. Therefore, the number of vertices is at least two more than the number of edges, $2000\ge 1999+2$ contradiction.

e claim that the answer is 1999. A counterexample for 1998 is when a cell is shaded if and only if it is in the first row or first column but not both. We will then show that any coloring of 1999 cells works. We will try to construct a case with no triangles and show that it is impossible. Note that in order for there to be no triangles, if any two rows share a colored cell in the same position, then that shared position must be the only colored cell in both of those rows. Call a row orz if it contains exactly one colored cell, and unorz otherwise. Note that there can be at most 999 orz rows, so there must be at least 1000 colored cells that are in an unorz row. Case 1: There is at least one orz row. Then, we cannot have any unorz row that shares a colored cell in the same position as in a orz row (since otherwise there will be a triangle), so we have at most 999 columns available for unorz rows. However, since there are at least 1000 cells in unorz rows, we must have two colored cells in unorz rows that are in the same column, which causes a triangle. Case 2: There are no orz rows. Then, all 1999 colored cells are in unorz rows. Therefore, clearly, there exist some two colored cells that are in the same column in two unorz rows, which causes a triangle, so we are done.

The answer is $\boxed{1999}$. A counterexample for $1998$ is just shading the first row and first column, but not the bottom left corner. Suppose that a right triangle did not exist for $n = 1999$. Call a square good if it is in a column with two or more colored squares. Clearly, each good square is the only colored square in its row. Assume that there were $k$ good squares. Since there are only $1000$ rows, $0\le k\le 1000$. If $k = 0$, then each column has at most $1$ colored square, and if $k = 1000$, each row has at most $1$ colored square, both result in at most $1000$ colored squares, contradiction. If $0<k<1000$, then there are at most $999$ columns without good squares, which means at most $k + 999$ total squares. However, $k + 999<1999$, contradiction. Therefore a right triangle must exist.

Similar to (but much easier than) USA TST 2011/8. Interpret the chessboard as the lattice points with $x$ and $y$ coordinates between $1$ and $1000$, inclusive. We claim that the answer is $1999$. The points $(2,1),(3,1),\ldots,(1000,1),(1,2),(1,3),\ldots,(1,1000)$ show that this is a lower bound. We claim that $n=1999$ satisfies the problem statement. Assume FTSOC that no colored point has another colored point with the same $x$-coordinate and another colored point with the same $y$-coordinate. If a colored point $P$ has a colored point with the same $x$-coordinate, then consider the projection of $P$ to the $y$-axis. Otherwise, consider the projection of $P$ to the $x$-axis. These $1999$ projections must be distinct: no two colored points with the same $x$-coordinate can be projected to the $x$-axis, and no two colored points with the same $y$-coordinate can be projected to the $y$-axis. Since there are $1999$ colored points, the set of projected points must contain all of $(1,0),(2,0),\ldots,(1000,0)$ or $(0,1),(0,2),\ldots,(0,1000)$. However, this means the $1000$ colored points that created these projections must be in pairwise distinct rows and columns, which means no other colored point can be added, a contradiction. $\square$

Rather dirty induction done twice. Claim: For a general $m \times n$ grid with $m, n \ge 1$, the maximum number of colored squares that can be placed while this doesn't hold is at most $m + n - 1$. Proof. The base case of a $0 \times n$ or $n \times 0$ grid is immediate. Else, take the row/column with the maximum number of squares, say $C$. If $C = 1$, then the bound follows immediately. Else, this rules out at least $C$ rows/columns. Induct down on the smaller grid. $\blacksquare$ Claim: For a general $m \times n$ grid with $m, n \ge 2$, the maximum number of colored squares that can be placed while this doesn't hold is at most $m + n - 2$. Proof. The base case of a $2 \times n$ or $n \times 2$ grid is immediate. Else, take the row/column with the maximum number of squares, say $C$. If $C = 1$, then the bound follows immediately. Else, this rules out $C + 1$ rows/columns (including the row they are in). Using the weaker claim finishes. $\blacksquare$ A construction of $n = 1998$ comes by coloring all of a row and a column besides their intersection. Thus, $n = 1999$ is the answer.

No one posted here in 2024??? Generalize to an $a \times b$ board where $a,b \ge 2.$ We claim that the answer is $\boxed{n=a+b-1},$ with the construction for $a+b-2$ being the union of the first row and first column, excluding the topleft corner. Now we will show that $n = a+b-1$ will do the trick, by strong induction. The base case for a $m \times 2$ grid holds because if there were $m+1$ colored squares, by Pigeonhole one of the rows must be completely colored, say WLOG the top row, and then at least one other square is shaded, yielding a right triangle. For the inductive step, assume that the problem holds for all $x \times y$ rectangles, with $2 \le x \le a$ and $2 \le y \le b$ but $(x,y) \ne (a,b).$ Consider the top row of our $a \times b$ board. If it has at most $1$ colored square, then there are $a+b-2$ colored squares in the remaining $(a-1) \times b$ grid, yielding a right triangle by the inductive hypothesis. Thus assume that there are $k$ colored squares in the top row, residing in columns $a_1, \dots, a_k.$ If there is another colored square in column $a_i$ for some $i,$ then we are clearly done, so assume that there are no other colored squares in column $a_i$ for all $i.$ Then we can effectively "delete" the columns $a_1, \dots, a_k$ since we cannot do anything with them anymore, and we can also delete the top row. What remains is a $(a-1) \times (b-k)$ grid in which we must color $a+b-k-1 > a+b-k-2$ squares. If $k < b-1,$ then by the inductive hypothesis we are done. If $k = b-1,$ what remains is a $(a-1) \times 1$ grid, in which we can color at most $a-1$ squares, yielding $(a-1) + (b-1) = a+b-2$ squares, which is bad. Finally, if $k = b,$ then at least one other square is shaded, giving a right triangle. Therefore, with all cases having been exhausted, the induction is complete, and so the answer for an $a \times b$ board is $a+b-1.$ When $a=b=1000,$ this yields the answer of $\boxed{1999}.$

We claim the answer is $\boxed{1999.}$ Call a tile good if coloring it makes such a triangle and any row or column unmarked if there are no colored tiles in it. Note that if we color a tile that is in both a marked row and column, it is good. We will show that the maximum number of bad tiles you can color is $1998$, therefore guaranteeing the $1999$th tile to be good. We want to maximize our number of bad tiles by minimizing the number of marked rows and columns each colored tile creates (since if all rows and columns are marked, then we are guaranteed to color a good tile). Notice that the coloring of a bad tile will mark at least one row and/or column. Also keep in mind that if we color a tile and the number of unmarked rows and columns does not change, that tile is good. We begin with $1999$ unmarked rows and columns. The first tile that we color will mark one row and one column, reducing our count to $1997$. Since each bad tile marks at least one row and/or column, we theoretically can color $1997$ more bad tiles. Thus we can color $1+1997=1998$ bad tiles, with our $\boxed{1999\text{th}}$ tile forming the triangle. Finally, we show such a configuration exists. Imagine coloring the entire bottom row and entire left-most column, leaving the bottom left corner uncolored. Clearly every row and column is marked, and thus we are done. $\square$