1. With an unlimited supply of toothpicks of n different colors, how many different triangles can be formed on a flat surface, using three toothpicks for the sides of each triangle?
   (Reflections are considered different, but rotations are not.)

2. How many different squares?

This solution is independent, but it will probably go along the same lines as the previous solutions.
_____________________________________
Part 1: Triangles

Every possible triangle has three possible rotations.  Some of the triangles are rotations of themselves.  So the possible triangles come in two types: (1) a group of 3 triangles that rotate to each other, and (2) a single triangle that is a rotation of itself.  The total number of triangles, counting each group of type 1 as three is n^3.

The only possible way to form the second type is if the whole triangle is the same color.  So there are n of these triangles.

The rest of the triangles (n^3-n) are all type 1, so we only count a third of them.  So, there are (n^3-n)/3 of these triangles.

The total number of triangles is n+(n^3-n)/3, which factors to n/3(2+n^2).
______________________________________
Part 2: Squares

Every square has four possible rotations.  Like the triangles, some squares rotate to themselves.  Also, some squares come in groups of four, all rotating to each other.  Furthermore, there are even squares that come in groups of two that rotate to each other.  The three types of squares are the following: (1) a square that rotates to itself, (2) a pair of squares that rotate to each other, and (3) a group of 4 squares that rotate to each other.  Again, counting each group by its individual rotations, there are n^4 squares.

The only squares that are type 1 are squares of one color.  There are n of these.

The only pairs of squares that rotate only to each other (type 2) are ones that have two colors, each color on opposite sides.  There are n*(n-1)/2 such pairs.

The rest of the squares (n^4-n-n*(n-1)/2) are type 3.  Each group of four counts as one, so there are (n^4-n-n*(n-1)/2)/4 squares of type 3.  This simplifies to n/8(2n^3-n-1).

Summing it all together, there are n+n*(n-1)/2+n/8(2n^3-n-1).  This simplifies to n/8(2n^3+3n+3).
________________________________________
Last notes

There is a mistake in the square solution.  See above comments for my correction.

That's all!  This problem is somewhat similar to the "Unique Necklaces" problem, but much easier in my opinion.  For one thing, there are no reflections, and this makes a big difference using my method.  Second of all, the variable is the number of sides/beads rather than the number of colors, making my method almost impossible and probably impractical.

Edited on September 10, 2004, 8:45 pm

Edited on September 10, 2004, 11:45 pm

Posted by Tristan on 2004-09-10 20:44:12