Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Quadrilaterals in a 3x3 Array of Dots


Date: 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/   
    
Associated Topics:
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/