# Interesting Question

1. Jan 17, 2008

### rbzima

Suppose you have a checkerboard with 1000 squares on a side and all the cells colored white. Suppose he colors n of the cells red. What is the smallest n such that he guarantees to have three red cells that create a right triangle whose non-hypotenuse sides are parallel to the board's edges?

Essentially, I'm currently working on this for a senior level undergraduate seminar class, and I really think this is an interesting question. I'm currently at the beginning stages of this problem, which is basically trial and error for the first few cases where I have a 4 sided board, 5 sided, etc. I'm beginning to think there is definitely a pattern though. If I want to guarantee something, I basically want worst case scenario to deal with. Here's how I think this can work out...

Color all cells on the top edge and left edge with the exception of the cell to the top-most left. This fills 999*2 cells in. Then, all that's needed is to fill one cell in anywhere else on the board, and you will definitely have a right triangle whose edges are parallel to the board. Does this make sense, or is there something I'm missing?