Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Interesting Question

  1. Jan 17, 2008 #1
    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?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

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