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

If you have a square three dots by three dots, how many quadrilaterals
can you make by connecting them? (You can go diagonally too.)

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

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
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

- 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
Math Forum Home || Math Library || Quick Reference || Math Forum Search