MathDB

4

Part of 2000 USAMO

Problems(1)

USAMO 2000 Problem 4

Source:

10/1/2005
Find the smallest positive integer nn such that if nn squares of a 1000×10001000 \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.
USA(J)MOUSAMOinductionpigeonhole principleContradictioncombinatoricsgrid