Quadrilaterals in a 3x3 Array of DotsDate: 03/10/99 at 00:06:57 From: David Allen Subject: Quadrilaterals from nine Dots If you have a square three dots by three dots, how many quadrilaterals can you make by connecting them? (You can go diagonally too.) Please send me a picture so I can compare your answer with mine. Date: 03/10/99 at 12:01:30 From: Doctor Rob Subject: Re: Quadrilaterals from nine Dots I started by numbering the nine dots, as follows: 1 2 3 8 9 4 7 6 5 Now you can pick any four of these to be the vertices of a polygon. This is the same as choosing a subset of 4 from a set of 9 objects. It can be done in 9C4 = 9!/(4!*5!) = 126 ways. However, that is not the answer: There are two problems with this count, which we'll adjust accordingly. The first problem is that some of the sets of four points, if connected, would give a quadrilateral with a straight angle at one of the vertices, such as the set {1,2,3,4}, which would give a straight angle at vertex 2. You may or may not wish to count this as a triangle instead of a quadrilateral. There are 36 such sets of 4, containing as a subset one of {1,2,3}, {1,5,9}, {1,7,8}, {3,4,5}, {3,7,9}, or {5,6,7}. Just add one of the six other points to each of these six triplets, and there will be 6*6 = 36 such sets. The second problem is that of the remaining sets of vertices: some will be vertices of three different quadrilaterals, and some will be vertices of just one. For example, the set {1,3,6,9} can be connected up in the clockwise cyclic orders 1369, 1396, or 1936, but the set {1,2,8,9} can only be connected up in the clockwise cyclic order 1298. (By definition, a quadrilateral cannot have two sides that cross, as would happen if you tried the order 1289 or 1928.) This tripling happens if and only if one point is contained inside the triangle formed by the other three. The only point that can be interior to a triangle is point 9, the very center. There are 8 of these situations: {1,3,6,9}, {1,4,6,9}, {1,4,7,9}, {2,4,7,9}, {2,5,7,9}, {2,5,8,9}, {3,5,8,9}, {3,6,8,9}. These represent the 8*3 = 24 concave quadrilaterals (one interior angle greater than a straight angle). Instead of counting each of these eight sets once, we have to count them three times, which adds an additional 8*(3 - 1) = 16 to the total count. That means that there are either 126 + 16 = 142 quadrilaterals (counting those with a straight angle) or 142 - 36 = 106 (not counting those with a straight angle). In either case, 24 are concave, and the rest are convex. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ Date: 03/10/99 at 12:21:09 From: Doctor Rob Subject: Re: Quadrilaterals from nine Dots See previous answer. I forgot to include mention of the quadrilaterals containing the straight angles {2,6,9} or {4,8,9} plus any fourth point. That means that instead of 36 quadrilaterals containing a straight angle, there are 6*8 = 48. So the correct total is either 142 or 142 - 48 = 94. Sorry about that! I think this answer is now correct, as I checked it by writing out all 126 combinations, of which 48 had a straight angle and 8 had three concave quadrilaterals. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/