# 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?

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted