AoPS Academy
be a triangle. Let 
be the feet of the altitudes from 
respectively. Let 
be the projections of onto line 
. Show that 
.
be real numbers such that ![\[ \frac{1}{x^2-1} + \frac{1}{y^2-1} + \frac{1}{z^2-1} = 1. \]](http://latex.artofproblemsolving.com/8/f/5/8f5d49c9b44e3db3cd85fea7b6521e1dc02d4269.png)
Prove that ![\[ \frac{1}{x+1} + \frac{1}{y+1} + \frac{1}{z+1} \le 1. \]](http://latex.artofproblemsolving.com/c/0/4/c0438d6eba686d0a11fd4decb4afa9a14aa50bac.png)
are non-negative integers.
such that if squares of a 
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.
for which we can color squares without leaving a right triangle. There can be at most 
row-happy black squares in the best case. If there are more than 
, two of them would be in the same row, contradiction. If there are exactly , there must be one of them in each row and each row could not contain any other squares, so there would be exactly black squares in total. Analogously, in the best case there can be at most column-happy black squares. Since each square is at least one of the two, there can be at most 
black squares in total. It's easy to find an example for : color the bottom row and the leftmost column, but leaving the bottom-left corner white. squares without leaving a right triangle, and this is the maximum. Thus the required is 
.
board with 
squares. Since we have 
rows, at least one row contains two black squares. Similarly, at least one column contains two black squares.
and 
, and call the black squares the share a column 
and 
. Note that or cannot share a column with or or else there would be a triangle. Similarly, and cannot share a row with or . Therefore we have four distinct squares. Shuffles the rows and columns in such a way that and lie in the first two squares on the first row, and and lie on the bottom two squares of the rightmost column. or or the row of or would form a triangle. So essentially we use four squares to cut out the leftmost two columns and bottom two rows. We now have 
squares to color a 
board. Continue this operation until we must color a 
board with 
squares. Contradiction.
such that if squares of a 
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.
such that if squares of a 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.
be the answer to this problem for an 
grid. I claim 
.
; here base cases are clear. To see 
take a row and a column and color all cells on them except for their intersection. WLOG, 
. If each row has two colored cells, we get 
colors. Else, pick that row with just one colored cell and look at the column containing it. Let there be 
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, 
so we may conclude that the original can have no more than 
cells. Our induction is complete. 
is the smallest such such that there is guaranteed to be a right triangle. For 
, 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 colored squares. Hence, we see that 
. 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.
column and 
row squares respectively. Since 
, we have that one of or must be greater than or equal to , so we are done, since there must be some "overlap". Now suppose that there are neither squares. We now have that there are neither squares, taking up 
rows and columns. Hence we have that there are 
rows/columns squares taking up 
rows and columns. Hence, there must be overlap, and we are done. 
shaded square be bad.
(
) grid and let the number of bad columns be 
, then the good columns (
shaded squares) is 
.
) then the total number of shaded squares is at most 
. bad column:, otherwise 
(out of 
) of these squares share a row. of these squares none of the good columns would have any shaded squares since those squares definitely would take up all rows. Total shaded squares is .
of these squares. The other columns have at most 
squares, giving a maximum of 
.
, thus, we have shaded squares at most if no right triangle ever forms.
then we will always find a right angle triangle.
we can construct an example where no right triangle appears, just shade the top row and left column except the top-left corner square.
, then setting 
, 
.
.
, take a punctured L as illustrated below (with replaced by 
): ![\[ \begin{bmatrix} 1 \\ 1 \\ 1 \\ & 1 & 1 & 1 \end{bmatrix}. \]](http://latex.artofproblemsolving.com/b/4/6/b46dcb21db9d210334744d964b7503815186fe89.png)
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] 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]](http://latex.artofproblemsolving.com/d/a/6/da6c8142df31280f0636ee1fa6966e68895ae77b.png)
tokens and that 
. Then obviously some column has more than two tokens, so at most tokens don't emit a death ray (namely, any token in its own column). Thus there are at least 
death rays. On the other hand, we can have at most 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, 
as desired.
. To show that fails, pick an arbitrary row, an arbitrary column, and color in both. Then uncolor their intersection, which clearly works. works. Now identify each cell in the chessboard as an ordered pair 
where 
represents the column number and 
the row number, so the bottom left is 
and the top right is 
. We can see that such a right triangle exists if and only if there exists some such that column contains at least two colored squares and row contains at least two colored squares. 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 
columns are colored then new solitary columns are created: one for each square colored in that column. Thus after some number of columns are colored, with cells being filled in, the total number of solitary rows is equal to:
hence after all the columns are colored there are:
Now note that any coloring without right triangles must have at most 
columns with one colored cell: is impossible since then we only color squares, and is impossible since it implies the row that doesn't have one colored cell has cells, and a right triangle can be clearly formed. Hence after the columns are all colored we have at least 
solitary rows, which is absurd since there are only rows in the chessboard. Hence such a coloring does not exist, so every coloring of squares contains a right triangle. 
. To see that 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 
doesn't work. 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.
minutes to solve, but hour to write up... I'm obviously inexperienced at Olympiad Combo. is the answer. colored square and non-singular if it contains or more. Notice that in order for a chessboard to be bad, every single colored square within a non-singular row must have 
additional colored squares in its own column. singular row, then the largest possible amount of colored squares within our non-singular rows is . singular rows, the maximum possible amount of colored squares contained within the non-singular rows is .
, as we cannot guarantee there will exist a non-singular row (by the Pigeonhole Principle) for these values of . If 
, then we can construct bad chessboards as follows:
Color the first 
squares of row from column to column ; Color the last squares of column (from row to row )., and we've satisfied all conditions necessary to form a bad chessboard, so we're done.. colored squares, then it must contain exactly singular rows. singular rows within our chessboard. Now, we have 
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). singular row on our chessboard. Then, the largest possible amount of colored squares contained within our non-singular rows is , implying the number of colored squares within our singular rows (for this case) is at least 
. Because our chessboard only has rows, however, we conclude that exactly singular rows are needed for this case. singular rows on our board to (possibly) construct a bad chessboard when . This means the number of colored squares here is just 
. Obviously, we have a contradiction as 
, so all chessboards with are good and we're done. 
, the rectangle 
can have at most 
colored cells while not having any right triangles.
clearly yields at most 2 colored cells. Otherwise, consider the row with the maximum number of colored cells, let this be 
. If 
, then the maximum number of cells is 
. If 
, then we are forced to have at most 
by filling out the final unfilled the row (This is the equality case).Otherwise, the other 
cells in the row, and the 
other cells in the column, all cannot be colored. Additionally, by the inductive hypothesis, the maximum number of cells in the remaining 
rectangle is 
if 
, and 
if 
. Thus, the total is at most![\[M + (b-M) +(a-1)-1 = b+a-2\]](http://latex.artofproblemsolving.com/d/4/7/d47e258b139e181673760e3832db6b0489cb8d9b.png)
and we're done. .
. To see that 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.
be the bipartite graph of the chessboard, where 
is the set of rows and 
is the set of the columns. We connect 
to 
iff their intersection on the chessboard is colored. We will prove that if 
, then 
has a path of size 
, which clearly implies that there is a right triangle. but has not a path of size . Then, for every with 
, its neighbors have degree exactly . The same is true for with 
. Therefore, is a disjoint union of trees, and has exactly 
vertices, so if has more than a tree, there will be less than 
vertices. Hence, is a tree. However, this clearly implies that there will be a size of path in , implying the desired result.
To show that does not work, simply consider the case where the first row and the first column is colored, but not their intersection. Define vertices 
and 
in a bipartite graph where 
is connected if and only if row 
and column 
is colored. Note that if there exists a path with two vertices in 
and two in , then there is a -path, implying that there is a right triangle. edges without creating a -path. Clearly there must be no cycles, so our bipartite graph is a forest. Consider any tree. It may not have two vertices in and two in , so WLOG assume it has only one vertex in . 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, 
contradiction.
. A counterexample for is just shading the first row and first column, but not the bottom left corner.. 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 good squares. Since there are only rows, 
. If 
, then each column has at most colored square, and if 
, each row has at most colored square, both result in at most colored squares, contradiction. If 
, then there are at most columns without good squares, which means at most 
total squares. However, 
, contradiction. Therefore a right triangle must exist.
and 
coordinates between and , inclusive. We claim that the answer is . The points 
show that this is a lower bound. satisfies the problem statement. Assume FTSOC that no colored point has another colored point with the same -coordinate and another colored point with the same -coordinate. If a colored point 
has a colored point with the same -coordinate, then consider the projection of to the -axis. Otherwise, consider the projection of to the -axis. These projections must be distinct: no two colored points with the same -coordinate can be projected to the -axis, and no two colored points with the same -coordinate can be projected to the -axis. Since there are colored points, the set of projected points must contain all of 
or 
. However, this means the 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. 
grid with 
, the maximum number of colored squares that can be placed while this doesn't hold is at most 
.
or 
grid is immediate. Else, take the row/column with the maximum number of squares, say 
.
, then the bound follows immediately. Else, this rules out at least rows/columns. Induct down on the smaller grid. grid with 
, the maximum number of colored squares that can be placed while this doesn't hold is at most 
.
or 
grid is immediate. Else, take the row/column with the maximum number of squares, say ., then the bound follows immediately. Else, this rules out 
rows/columns (including the row they are in). Using the weaker claim finishes. comes by coloring all of a row and a column besides their intersection. Thus, is the answer.
board where 
We claim that the answer is 
with the construction for being the union of the first row and first column, excluding the topleft corner.
will do the trick, by strong induction. The base case for a 
grid holds because if there were 
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.
rectangles, with 
and 
but 
Consider the top row of our board. If it has at most colored square, then there are colored squares in the remaining 
grid, yielding a right triangle by the inductive hypothesis. Thus assume that there are colored squares in the top row, residing in columns 
If there is another colored square in column 
for some 
then we are clearly done, so assume that there are no other colored squares in column for all 
Then we can effectively "delete" the columns 
since we cannot do anything with them anymore, and we can also delete the top row. What remains is a 
grid in which we must color 
squares. If 
then by the inductive hypothesis we are done. If 
what remains is a 
grid, in which we can color at most squares, yielding 
squares, which is bad. Finally, if 
then at least one other square is shaded, giving a right triangle. board is 
When 
this yields the answer of 
, therefore guaranteeing the th tile to be good. unmarked rows and columns. The first tile that we color will mark one row and one column, reducing our count to 
. Since each bad tile marks at least one row and/or column, we theoretically can color more bad tiles. Thus we can color 
bad tiles, with our 
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. 
. For the construction, simply extend the following colouring to a grid.![[asy]
size(6cm);
for (int i = 0; i <= 10; ++i) {
D((0, i)--(10, i),black);
D((i, 0)--(i, 10),black);
}
real draw(real p, real q) {
filldraw((p, q)--(p+1, q)--(p+1, q+1)--(p, q+1)--cycle,palered+opacity(0.5),black);
return p;
}
for (int i = 1; i < 10; ++i) {
draw(0, i);
draw(i, 0);
}
[/asy]](http://latex.artofproblemsolving.com/9/4/2/942dd2fb63ee0d4ca83999b57b0e478963eaee26.png)
is sufficient. Construct a bipartite graph on the sets of vertices and , label the vertices on each side , , 
, , and connect 
if 
is coloured, where we impose the coordinates on the chessboard in the obvious fashion. Suppose that at least squares are coloured, i.e. that has at least edges, and that there are no such right-angled triangles, i.e. that there are no paths of length in . Split into disjoint components 
, 
, , 
.
is either the union of edges 
for vertices 
, 
or 
, 
where ranges over 
for some positive integer , or a single vertex. is not a single vertex, so that has vertices in both and . Select a 
. By our assumption, the neighbourhood 
of 
is nonempty.
, then consider instead the neighbourhood 
of 
, where 
.
, then we're done as indeed satisfies our characterisation.
, then fix a 
and take another 
different from 
. Now can only be connected to as otherwise 
would be a valid path, where is another neighbour of , contradiction. Hence we can take 
, 
, as desired.
, then similarly fix a 
and take another 
different from . Now can only be connected to as otherwise 
would be a valid path, where is another neighbour of , another contradiction. Hence we can take 
, 
, as desired. has, say, elements and has, say, 
elements, where 
. Let 
, 
, , 
be the remaining components. Observe that each component 
has edges and 
vertices, where is defined in the above claim. Let be the value of for .
, then the maximum number of edges in is 
, contradiction.
, note that the total number of edges is 
, contradiction.
. For squares, consider a grid with the left and bottom rows filled except the overlapping corner.
. We say a row is good if and only if it has at most one black square. Now it is easy to see that if a row is not good, then the columns the black squares occupy cannot have another black square. Thus, if there are good rows and 
not good rows, then in each not good row we have at most squares in these rows. If good rows have no black squares, the bound is immediate. Otherwise, it occupies at least one column, so there are at most squares in a not good row. Moreover, there are at most good rows, so there are at most black squares in good rows. Concluding we must have .
.
board for 
.
squares are colored, then we have a right triangle. We use induction.
,
squares, we must have a right triangle.
board for 
colored squares, there must be a column that has no more than one colored square. Switch this column with the rightmost one.
,
(or more) squares are colored, there must be a colored right triangle. It's easy to show that 
might not have a colored right triangle (fill one column and one row, but not their intersection).
colored squares. Let 
,
denote the number of colored squares in column 
,
,
for 
.
,
.
,
not in columns 
.
.
.
board. A simple construction exists with 
colored squares and no right triangles: color the leftmost 
.
.
squares of a 
chessboard and have no right triangles. By the pigeonhole principle, there must be two colored squares in the same row, say 
and 
.
colored squares amongst the 
and 
,
and 
be the sum of all 
.
.
and 
.
there must exist at least 
rows having no more than 1 colored cell. Hence, there must exist a row containing the remaining 
colored cells. This, however, is impossible because then we get a right angled triangle for any cell not in that row. Similarly, 
.
black squares.
and 
is easy 
denotes the number of rows and 
grid with 
black squares
(by symmetry)
,
if all but one of its vertices are leaves. The existence of an example for 
,
steps, go to a non-leaf 
is 
.
implies the existence of a right triangle for the 
case. Suppose that at least 
squares are colored.
are colored. We can also swap the squares so that 
are colored (otherwise a right triangle would exist by the same logic as the k=3 case). It follows that there are no other colored squares in the first, second columns and last, second to last rows. Then there must exist at least 
colored squares among the top-right 
by 
,
.![\[1+(1999-x)=2000-x\]](http://latex.artofproblemsolving.com/6/f/f/6ff6079c4eca4dab39ec48e414041df0b12cd3ca.png)
but since 
,
.
squares need to be colored. Coloring all but one square of a column and coloring the remaining squares in the uncolored square's row is a valid counterexample for 
.
more squares. However, the rest of the columns have more than or equal to 
.
so 
.
,
.
colored squares, this means that the maximum number of colored squares occurs when as many of the 
,
colored squares. Therefore, the smallest positive integer 
.