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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted

Similar Discussions: Interesting Question
  1. Interesting question (Replies: 8)

  2. Interest/loan question (Replies: 2)

  3. An Interesting Question (Replies: 27)