All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 FIGURE it out ! (Posted on 2004-09-10)
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?

 No Solution Yet Submitted by SilverKnight Rating: 3.3333 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution | Comment 2 of 12 |

For a triangle, there can be 3, 2 or 1 color(s) making up the figure.

There are C(n,3) ways of choosing 3 colors, but any set of three can be set in either clockwise or counterclockwise order, so the three-color triangles contribute 2*C(n,3) = (n^3-3*n^2+2*n)/3 to the total.

For two colors, there are n ways of choosing the one that occurs on two sides, and (n-1) ways left of choosing the remaining side, for n^2-n ways.

There are n ways of choosing a one-color triangle.

Adding the terms and simplifying we get (n^3+2n)/3

For squares there are P(n,4) possible sequences of four colors, but since rotations do not count separately, that has to be divided by 4.  So four-color squares account for P(n,4)/4 of the total.

With a three-color square, there are two possibilities: the duplicated color is on two adjacent sides or two opposite sides.  If the former, there are n ways of choosing the duplicated color, n-1 ways of choosing the one clockwise from it and n-2 ways of choosing the one remaining. If the duplicated color is on opposite sides, there's still n ways of choosing it, but only C(n-1,2) = (n-1)(n-2)/2 ways of choosing the other two, as clockwise or counterclockwise doesn't matter.

With only two colors, they can be either 3 of one and one of another, with n(n-1) ways of choosing first the 3 and then the 1 (or the other way around if you like), or there can be two of each, in which case there are C(n,2) ways of choosing the two, but then this must be multiplied by two to reflect the fact that the like colors can be adjacent or opposite.

Of course there are still n ways of choosing a single-color square.

That makes P(n,4)/4 + (3/2)(n(n-1)(n-2)) + 2n(n-1) + n, or

n(n-1)(n-2)(n-3)/4 + (3/2)(n(n-1)(n-2)) + 2n(n-1) + n.

That leaves only simplification.

 Posted by Charlie on 2004-09-10 15:08:51

 Search: Search body:
Forums (0)