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

Number of triangles in a square grid of unknown size

  1. Aug 13, 2013 #1
    Hello.

    I came up with this problem while I was waking up this morning, and some of the finer aspects have me pretty confused.

    First off, I made the simplification of a square grid because I'm not yet ready to deal with non-square grids, but maybe we can get to that later. Here's where I got with the problem:


    The number of groups of 3 points in a grid of unknown size is:

    [itex]{x \cdot y \choose 3}[/itex]

    Where [itex]x[/itex] and [itex]y[/itex] are the dimensions of the grid.


    But we now need to subtract the number of 3 point groups that are lines and not triangles. We'll break these line groups into sections. The number of horizontal 3 point lines in a grid of unknown size (assuming x > 3) is:

    [itex]{x \choose 3} \cdot y[/itex]


    The number of vertical 3 point lines in a grid of unknown size (assuming y > 3) is:

    [itex]{y \choose 3} \cdot x[/itex]


    The number of diagonal lines increases following an infinite sum, as the number of types of such lines (each type corresponding to a certain slope) increases as the grid's size increases. Now I'm going to start going analytical because this is getting complicated. Below are grid sizes and the number of diagonal lines present in each grid.

    Diagonal lines of slope 1 or -1:
    3x3 grid: [itex]{3 \choose 3} \cdot 2[/itex]
    4x4 grid: [itex]{3 \choose 3} \cdot 4 + {4 \choose 3} \cdot 2[/itex]
    5x5 grid: [itex]{3 \choose 3} \cdot 4 + {4 \choose 3} \cdot 4 + {5 \choose 3} \cdot 2[/itex]
    6x6 grid: [itex]{3 \choose 3} \cdot 4 + {4 \choose 3} \cdot 4 + {5 \choose 3} \cdot 4 + {6 \choose 3} \cdot 2 [/itex]
    7x7 grid: [itex]{3 \choose 3} \cdot 4 + {4 \choose 3} \cdot 4 + {5 \choose 3} \cdot 4 + {6 \choose 3} \cdot 4 + {7 \choose 3} \cdot 2 [/itex]
    8x8 grid: [itex]{3 \choose 3} \cdot 4 + {4 \choose 3} \cdot 4 + {5 \choose 3} \cdot 4 + {6 \choose 3} \cdot 4 + {7 \choose 3} \cdot 4 + {8 \choose 3} \cdot 2 [/itex]

    Diagonal lines of slope 2, -2, 1/2 or -1/2
    5x5 grid: [itex]{3 \choose 3} \cdot 4 \cdot 3[/itex]
    6x6 grid: [itex]{3 \choose 3} \cdot 4 \cdot 4 \cdot 2[/itex]
    7x7 grid: [itex]{3 \choose 3} \cdot 4 \cdot 2 + {3 \choose 3} \cdot 4 \cdot 5 + {4 \choose 3} \cdot 4 \cdot 4[/itex]
    8x8 grid: [itex]{3 \choose 3} \cdot 4 \cdot 2 \cdot 2 + {4 \choose 3} \cdot 4 \cdot 5 \cdot 2[/itex]

    Diagonal lines of slope 3, -3, 1/3, or -1/3
    7x7 grid: [itex]{3 \choose 3} \cdot 4 \cdot 5[/itex]
    8x8 grid: [itex]{3 \choose 3} \cdot 4 \cdot 6 \cdot 2[/itex]


    So these appear to be infinite series. I tried to write out the terms as logically as I could. And this as far as I've gotten... Anyone feel like helping out? :)


    -Mator
     
    Last edited: Aug 13, 2013
  2. jcsd
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



Similar Discussions: Number of triangles in a square grid of unknown size
  1. Probability on a Grid (Replies: 5)

Loading...