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 Squares | Comment 3 of 12 |


Again, I am going to this of this in chunks. Iíll just use letters a, b, c, d to help me describe certain color arrangements. So aaaa means all 4 toothpicks the same color. aaab is 3 of one color, one of another. aabb 2 of one color, 2 of another. aabc is 2 of one color, 1 of another, and the last is yet another color. And then we have abcd, where all 4 are different. So thatís 5 groups.

Similar to my triangle solution, I have this so far:
aaaa: n (reflections are not different)
aaab: n*(n-1) (reflections are not different)
abcd: 2*[n!/(4!(n-4)!)] = 1/12*n*(n-1)*(n-2)*(n-3) (the "times 2" is because reflections are different)

Now the aabb and aabc arrangements are a little different. I have to ask myself a couple questions to make sure I donít miss anything.

First, does the instruction "pick 2 toothpicks the same color, and 2 toothpicks another color" yield only one result? The answer is No. aabb could also appear as abab, which is a different solution. So that yields 2 results.

Second, are the reflections of aabb or abab different from the original arrangement? The answers are no and no.

Similarly, my third question is, does the instruction "pick 2 toothpicks the same color, the 3rd a different color, and the last yet another color" yield only one result? Again, the answer is No. aabc could appear as abac, which is a different solution. Again, this yields 2 results.

And finally, are the reflections of aabc or abac different from the original arrangement? The answers are yes and no.

Ok, so letís turn this information into some formulas.

aabb: recalling how I explained the color choosing method from the Triangles solution, notice here that "red, blue" is the same thing as "blue, red." Either way I will end up with 2 reds and 2 blues. Again, you donít want to pick "red, red" because that is already accounted for in the aaaa group. So this is n choose 2 combinations without replacement, which is n!/(2!(n-2)!) = 1/2*n*(n-1). Since we said that abab is a different solution to "choose 2 blues and 2 reds," we should multiply this by 2. Remember, no reflections should be accounted for, so the formula for this group is actually 2*1/2*n*(n-1) = n*(n-1)

aabc: This oneís crazy! Ok, here is the clearest way for me to think about it. Again with the color choosing method, letís say that the first color is for the "2 toothpicks," followed by the other two colors. So "red, blue, green" means 2 reds, a blue and a green. This does not determine any order. So 2 reds, a blue and a green could be RRBG, RRGB, RGRB. Those are the only unique possibilities. Also notice that "red, green, blue" is the same as "red, blue, green." But "green, red, blue" is NOT the same, since that has TWO greens, a red and a blue. So how to sort out the permutation vs. combination question. Hmmmm.

Well, if I thought about this like n choose 3 combinations without replacement the formula would be n!/(3!(n-3)!). But that would mean that if we have a square made up of red(s), green(s), and blue(s), this arrangement will only be counted once. But we know that it matters if the 2 toothpicks are both red, green, or blue, so I could take this combination formula and multiply it by 3. That would account for aabc, bbac, and ccab. Also, remember we determined that choosing 2aís, 1b and 1c actually yields 3 results (aabc, aacb, and abac). So we multiply the formula by 3 again. So we get 3*3*n!/(3!(n-3)!) = 3/2*n*(n-1)*(n-2).

If that doesnít sit well with you, then think about n choose 3 permutations without replacement. Back to my very specific color choosing method, remember that the first color is for the "2 toothpicks." In the permutation mind set, this means that "red, blue, green" and "green, red, blue" are counted differently, which is a good thing. But "red, blue, green" and "red, green, blue" are also counted differently, which is not good. Why? Because Iím planning on multiplying everything by 3 since, again, choosing 2aís, 1b and 1c actually yields 3 results (aabc, aacb, and abac). But choosing 2aís, 1 c and 1 b (which is counted differently) yields the same 3 results (aacb, aabc, acab). So I have to also divide by 2 to account for the duplicates. So the formula is 3/2*n!/(n-3)! = 3/2*n*(n-1)*(n-2).

Oy! I hope I made some sense in there. I apologize for flipping back and forth between abc and red green blue stuff. Anyways, here is the final formula:

S = (aaaa) + (aaab) + (aabb) + (aabc) + (abcd)
S = [n]+[n(n-1)]+[n(n-1)]+[3/2*n(n-1)(n-2)]+[1/12*n(n-1)(n-2)(n-3)]
S = [n]+[n^2-n]+[n^2-n]+[3/2(n^3-3n^2+2n)]+[1/12(n^4-6n^3+11n^2-6n)]
Ok, I wonít bore you with simplifying any more. If I messed up, someone will tell me =)
S = 1/12*[n^4 + 12n^3 Ė 37n^2 + 18n]

  Posted by nikki on 2004-09-10 15:20:44
Please log in:
Remember me:
Sign up! | Forgot password

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

Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information