## Archive for September, 2010

### How to Count…Better

This post is an introduction to combinatorics, which is how to count without actually counting.  For example, you have 12 pairs of shoes, 16 shirts, and 8 pairs of pants in your closet.  How many different outfits can you make out of these, assuming that you have to wear a pair of shoes, a shirt, and a pair of pants (and assuming everything matches :)).

Listing out all of the combinations would be tedious!  Better is to use the following method.  There are 12 choices for shoes and 16 shirts.  So there are $12 \cdot 16$ shirt-pant combinations!  If this is unclear, think about drawing a grid with 12 slots on one side and 16 on the other.  Each box represents a different combination, and there are $12 \cdot 16$ boxes.  This method generalizes to more than 2 things; there are $12 \cdot 16 \cdot 8 = 1536$ shoe-shirt-pant combinations.  Don’t try listing that out 😛

Now suppose that there are 20 people in a class, and you need to pick a class president, vice president, and secretary.  How many ways are there to do this?  This is an application of our method.  It doesn’t matter, but say you pick the president first.  There are 20 choices for the president.  Now, the vice president can be anyone except the person who you just designated as president, so there are 19 choices.  Lastly, there are 18 choices for secretary.  Following our method, we get that there are $20 \cdot 19 \cdot 18 = 6840$ different combinations of people for the three positions.

Now I’ll change the problem a bit.  There are 20 people in the class and you need to choose 3 class representatives from them.  This may seem the same as the previous problem, except that in this case if Alison, Bob, and Charlotte are representatives that’s the same as Bob, Alison, and Charlotte being representatives, whereas in the previous problem order mattered, since Alison being president and Bob being vice president was different from Bob being president and Alison being vice president.  Order is a very important factor to consider in combinatorics.  So what do we do?  Well, we can still use the above method, but keep in mind that we counted all arrangements of the students Alison, Bob, and Charlie as different.

How many arrangements are there?  Well, there’s 1.  A,B,C  2.  A,C,B  3.  B,A,C  4.  B,C,A,  5.  C,A,B  6.  C,B,A.  So 6 arrangements.  Therefore, if we take our answer from before and divide by 6, that will correct for our over-counting.  So there are $\frac{6840}{6}=1140$ ways to choose 3 representatives!

Being able to count things in this way is essential for calculating the probability of events happening, which is extremely useful in playing games and analyzing real-world events.  Lastly, if you like this and want to see more, this and much more is covered in the Art of Problem Solving’s Introduction to Counting and Probability textbook.  See the resource page on the left side for a link to the Art of Problem Solving website and more.

### The 3n+1 conjecture

Hi everyone!  First of all, note that there’s now a button to share a post with all of your friends by email, facebook, or twitter.  If you do share that would be great!

In a typical middle or high school math class it may be hard to tell, but math is constantly evolving.  There are many important problems in various fields which we don’t know the answer to.

Here’s one good problem that is easy to state, but that has stumped the best mathematicians in the world since 1937!  It is called the Collatz Conjecture (a conjecture is an unsolved problem) after the guy who came up the problem, Lothar Collatz.

Pick a number, any (positive whole) number.  If your number is even, divide it by 2.  Otherwise if it’s odd, do three times your number and add 1.  Do this procedure over and over, if your current number is even divide by 2, if odd multiply by 3 and add 1.  The conjecture is that eventually, no matter what your number is, you will get the number 1.

For example, for the number 6, the steps are as follows:

$6 \rightarrow 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$.

Try it out for yourself!

Due to the power of computers, we know that every number up to $10^{18}$ satisfies the 3n+1 conjecture.  That’s 1,000,000,000,000,000,000.  While this is enough evidence to convince most people, it will only be proven when it shown for every single whole number (see my first post for why we prove things).

Also see my friend’s article about “The Art of Math” which came out recently in an online magazine called KidSpirit.  It covers other nice proofs, some of which I may write about in the future too 🙂  http://kidspiritonline.com/2010/09/the-art-of-mathematics/