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

Home > General
FIGURE it out ! (Posted on 2004-09-10) Difficulty: 4 of 5
  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 Solution for Triangles | Comment 1 of 13

Triangles:

I’m not sure, but I think I’d like to break this up into three sums. One for triangles with "toothpicks all one color," another for triangles with "2 toothpicks one color, 1 toothpick another color," and a third for triangles with "all 3 toothpicks are different colors."

Ok, for triangles with toothpicks of all one color, the answer is simply n choose 1 permutations. With or without replacements doesn’t matter, because you just pick one and the other two have to match. So the answer is n either way (n^1=n and n!/(n-1)!=n). Any reflections or rotations of these triangles are the same, so there are no duplicates that have to be accounted for.

Now for triangles with 2 toothpicks one color, 1 toothpick another color. The way I think about it is like this: What I’m going to do is say "first choose the color of the 2 toothpicks, then choose the color of the other toothpick, but it can’t be the same color as what you first picked." In other words, "red, blue" is a valid construction (2 reds and a blue) but "red, red" is not (2 reds and a red = 3 reds which is accounted for in the first group). So this is n choose 2 without replacement. Also notice that "red, blue" is not the same as "blue, red" (2 blues and a red). So this is a permutation, not a combination. Well, n choose 2 permutations without replacement is n!/(n-2)! = n*(n-1). A reflection will not yield a unique arrangement, so there are no duplicates that need to be accounted for.

And finally we have triangles with all 3 toothpicks being different colors. So this is n choose 3 without replacement (if I allowed replacement I would get triangles that are already accounted for in the first two groups). But should it be permutations or combinations? Well, a permutation would say that "red, blue, green" = "blue, green, red" = "red, green, blue" … Now I have a little problem because some of those are considered different, but some are not. I suppose I could let it be permutations, but divide by 3 for repeats. Or if I looked at combinations, that would only count "red, blue, green" and none of the others. We’ll that’s good because it doesn’t double count rotations but it doesn’t count the one reflection that would be unique. So I could just use the combinations formula and double it. So for this group, it’s either n!/(n-3)!/3 or 2*[n!/(3!(n-3)!)] which is the same thing.

So in total I have

T = n + n*(n-1) + 1/3*n*(n-1)*(n-2) = n^3 + 2n = n/3*(n^2 + 2)

The squares sound a little trickier. I’ll have to try that later =)


  Posted by nikki on 2004-09-10 14:00:07
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information