In my first post on counting in two ways, I left as exercises to find combinatorial explanations for several identities. In this post, I will explain the first two of them. The first identity was
\[\sum_{k=0}^n {n\choose k} = 2^n.\] If you're not familiar with the notation,
\[\sum_{k=0}^n {n\choose k} = {n\choose 0} +{n\choose 1} + \cdots + {n\choose n-1} + {n\choose n}.\]
So to use the example from a previous post, the left hand side is equal to the number of different ice cream cones you can have if there are $n$ different flavors and all the scoops are of distinct flavors (it counts the cones by the number of scoops since \(n\choose i\) counts the number of cones with $i$ scoops). We want to show that the expression on the right hand side, $2^n$, counts the same thing.
Now when we make a cone, for each flavor we have exactly two choices: either we include the flavor or we do not. Since we have to make this choice for each of the $n$ flavors, the total number of possible cones is $2^n$.
The second identity I posted was
\[ \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} {n \choose 2k} = 2^{n-1}. \] The notation $\lfloor\frac{n}{2}\rfloor$, pronounced 'floor of $\frac{n}{2}$', means that we take the largest integer less than or equal to $\frac{n}{2}$. That is, if $n$ is even then $\lfloor\frac{n}{2}\rfloor=\frac{n}{2}$ and if $n$ is odd then $\lfloor\frac{n}{2}\rfloor=\frac{n-1}{2}$. For simplicity, we will explain the identity when $n$ is even, but it will work just as well when $n$ is odd. So when $n$ is even, the left had side is \[ \sum_{k=0}^{\frac{n}{2}} {n \choose 2k}={n\choose 0} + {n\choose 2} + \cdots + {n\choose n-2} + {n\choose n}.\] We can see that this just sums the number of ice cream cones with an even number of scoops. Since $2^{n-1} = \frac{2^n}{2}$, it suffices to show that the number of cones with an even number of scoops is equal to the number of cones with an odd number of scoops. Let one of the flavors be vanilla. Then the number of even scoop cones that contain vanilla is equal to the number of odd scoop cones that don't include vanilla (just remove vanilla from the cone!). Similarly, the number of even scoop cones that do not include vanilla equals the number of odd scoop cones that do include vanilla (just add vanilla to the odd scoop cone). This shows that the number of odd scoop cones equals the number of even scoop cones, and we are done.
Thursday, April 11, 2013
Monday, April 8, 2013
Just adding
According to legend, when the mathematician Carl Friedrich Gauss was 7 years old, his first grade teacher assigned the class to add up the first one hundred natural numbers. The teacher of course hoped that this would occupy the students for a while and refused to believe young Gauss when the latter almost immediately claimed to have completed the task. The answer was correct, and the quick solution consisted mainly of one simple observation: \[1+100 = 2+99 = 3+98 =\cdots = 50+51.\] Thus, adding 1 through 100 is equal to adding 101 to itself 50 times so the answer is \(101*50=5050\).
Here is a geometric way of seeing what is going on (where we use 4 instead of 100 as our example).
The first row contains one pin, the second one contains two, the third three and the fourth four pins.
Now if we rotate this configuration 180 degrees and add it to itself we get the following picture:
We can easily see that we have four rows with five pins each and so the total number of pins is
\(4 \times 5 = 20\). Hence \(2 \times (1+2+3+4)=20\) and so \(1+2+3+4=10\). Yes, we could have
easily computed this in our heads, but now we can see that we can replace 4 in this picture by any arbitrary integer $n$ and we will have $n$ rows with $n+1$ pins each, and so we obtain the formula
\[1+2+\cdots+n=\frac{n(n+1)}{2}.\]
This formula can also be proved using the principle of mathematical induction (which we will not do here as it is not particularly enlightening) and is a classic example for teaching someone about induction.
Now try to find a formula for the sum of the first $n$ odd numbers and one for the sum of the first $n$ even numbers both by using Gauss' trick and geometrically.
Here is a geometric way of seeing what is going on (where we use 4 instead of 100 as our example).
The first row contains one pin, the second one contains two, the third three and the fourth four pins.
\(4 \times 5 = 20\). Hence \(2 \times (1+2+3+4)=20\) and so \(1+2+3+4=10\). Yes, we could have
easily computed this in our heads, but now we can see that we can replace 4 in this picture by any arbitrary integer $n$ and we will have $n$ rows with $n+1$ pins each, and so we obtain the formula
\[1+2+\cdots+n=\frac{n(n+1)}{2}.\]
This formula can also be proved using the principle of mathematical induction (which we will not do here as it is not particularly enlightening) and is a classic example for teaching someone about induction.
Now try to find a formula for the sum of the first $n$ odd numbers and one for the sum of the first $n$ even numbers both by using Gauss' trick and geometrically.
Sunday, April 7, 2013
Paper-folding geometry 1
Origami is a popular hobby around the world. Many books were written and many clubs were organized around the world to learn this art of paper folding. Our school also has such a club, and its president happens to be a co-president of our Math club. I thought of learning origami and trying to use it for geometry. Once I found in the Google library a book that was first printed in 1901. It was about paper-folding geometry, and I had a lot of fun doing some problems described by T. Sundara Rao. But all problems used a square as a base. I started to look around internet and found some more good sources that can be used at early stages of learning geometry. But I believe that we can do hands-on paper-folding geometry starting, possibly, from day one.
Let me try to build something basic around simple paper-folding that may be useful even for younger kids. One big advantage of this method is that we simultaneously develop 3D imagination and first "knowledge" in geometry. For example, if we fold a sheet of paper,
we will get a straight line, and everyone can see that two planes intersect at straight line. If we fold our paper in different direction, we will get two intersecting lines.
Straighten a paper out, and you will see, that two lines define only one plane and intersect at one point.
Do straight lines always intersect? Fold a paper in half, then fold one half again, and you get two parallel lines.
Take a toothpick, punch a hole at any point that does not belong to one of your folding lines and leave a toothpick inside. Our toothpick will define a third line that intersects the plane (paper), but, will never intersect the other two lines that belong to our plane. So we model skew lines.
We can ask a lot of questions based only on the experiments that were done, for example,
Let me try to build something basic around simple paper-folding that may be useful even for younger kids. One big advantage of this method is that we simultaneously develop 3D imagination and first "knowledge" in geometry. For example, if we fold a sheet of paper,
Do straight lines always intersect? Fold a paper in half, then fold one half again, and you get two parallel lines.
Take a toothpick, punch a hole at any point that does not belong to one of your folding lines and leave a toothpick inside. Our toothpick will define a third line that intersects the plane (paper), but, will never intersect the other two lines that belong to our plane. So we model skew lines.
- · How many common points do a paper sheet and a toothpick have?
- · Is it possible that they have only two common points? Three or more?
- · Show how they can have more than one point of intercept.
- · How many planes can your ‘toothpick straight line’ belong to? etc.
Wednesday, April 3, 2013
Solution to the Napoleon's problem and one more not so typical construction problem
A few days ago I posted the following problem, that many books called the Napoleon's problem.
Given a segment of the length one, construct a segment of the length $\sqrt{2}$ units using a compass only.
Most people start with trying to construct a triangle with the sides 1, 1, $\sqrt {2}$. But this does not work for compass only construction. Instead, it is much easier to construct a triangle $\sqrt{3}$, $\sqrt{3}$, 2, as shown below.
Given a segment of the length one, construct a segment of the length $\sqrt{2}$ units using a compass only.
Most people start with trying to construct a triangle with the sides 1, 1, $\sqrt {2}$. But this does not work for compass only construction. Instead, it is much easier to construct a triangle $\sqrt{3}$, $\sqrt{3}$, 2, as shown below.
Step by step:
1. Draw a circle of radius 1 with a center at arbitrary point A.
2. Choose arbitrary point B on this circle. Draw a circle of radius 1 with the center at B.
3. The second circle intercepts the first one at points C and D. CD = $\sqrt{3}$
4. Draw the third unit circle with the center at C. It intercepts the first one at B and E. DE = 2.
5. Draw two circles of radius $\sqrt{3}$ with centers at D and E. The distance from any of two points of their intersection to A is equal to $\sqrt{2}$.
The picture was made with Geogebra, and I apologize for its quality due to my first try of this program.
And at the end one more construction problem that involves both traditional instruments - straight edge and compass.
Given three arbitrary parallel lines on a plane, construct an equilateral triangle with vertices on these lines.
Fun with toothpicks: solutions plus one more puzzle
First the new puzzle:
Make seven equilateral (and equal) triangles using nine toothpicks.
Now the solutions.
1) For this one my dad pointed out to me that it suffices to move just three toothpicks. This is the result after you move them (of course if you really want to move four you can just move the right-most square a bit over to the right).
2) After moving the toothpick
3) This is what it looks like after moving the toothpicks. Hopefully it's easy to figure out which ones got moved.
4) Here is a picture with the toothpicks that you have to move slanted
and here is a picture with them moved (and slanted in their new positions)
And finally, four triangles with six toothpicks. You make a tetrahedron as in the picture.
This is my favorite because you have to realize that you can use the third dimension!
Make seven equilateral (and equal) triangles using nine toothpicks.
Now the solutions.
1) For this one my dad pointed out to me that it suffices to move just three toothpicks. This is the result after you move them (of course if you really want to move four you can just move the right-most square a bit over to the right).
2) After moving the toothpick
3) This is what it looks like after moving the toothpicks. Hopefully it's easy to figure out which ones got moved.
4) Here is a picture with the toothpicks that you have to move slanted
And finally, four triangles with six toothpicks. You make a tetrahedron as in the picture.
Tuesday, April 2, 2013
Back to the robots problem
Here is the problem from my previous post.
Four robots are initially at the vertices of a unit square. They start moving simultaneously with the same speed, each one keeping its direction to the right closest neighbor. Where do they meet and what distance will each one cover to the meeting point?
The answer to the first question is obvious due to the symmetry of the problem - they meet at the center of the square. In order to answer the second question we can introduce a rotating frame of reference.
The origin is where the robot A is at the moment. The axis x is always directed to the robot D, and the axis y is always directed to the robot B. Due to the symmetry of the problem the robots will always be at the vertices of the shrinking square up to the moment they meet at the origin. If we look at the motion of the robot B, it moves along the axis y from the point (0, 1) to the origin. So it moves exactly one unit to the meeting point. The same is true about distances for other robots due to the symmetry as mentioned before.
I have known this problem since, probably, age 14, but today I did a Google search and found a lot of sites talking about it. So I was planning to discuss the same situation for different regular polygons but decided just to put a link to the site with the short and meaningful discussion.
http://www.cut-the-knot.org/Curriculum/Geometry/FourTurtles.shtml
On a different note, I asked my algebra students to solve the following problem.
Two cars start moving towards each other from A and B respectively with speeds 60 mph and 40 mph. The
distance AB is 750 mi. What will be the distance between these cars 1 hour before they meet?
It took them a few minutes to realize how simple it is, and at the end the strongest students were a bit upset at themselves.
Four robots are initially at the vertices of a unit square. They start moving simultaneously with the same speed, each one keeping its direction to the right closest neighbor. Where do they meet and what distance will each one cover to the meeting point?
The answer to the first question is obvious due to the symmetry of the problem - they meet at the center of the square. In order to answer the second question we can introduce a rotating frame of reference.
I have known this problem since, probably, age 14, but today I did a Google search and found a lot of sites talking about it. So I was planning to discuss the same situation for different regular polygons but decided just to put a link to the site with the short and meaningful discussion.
http://www.cut-the-knot.org/Curriculum/Geometry/FourTurtles.shtml
On a different note, I asked my algebra students to solve the following problem.
Two cars start moving towards each other from A and B respectively with speeds 60 mph and 40 mph. The
distance AB is 750 mi. What will be the distance between these cars 1 hour before they meet?
It took them a few minutes to realize how simple it is, and at the end the strongest students were a bit upset at themselves.
Monday, April 1, 2013
Just counting
As I already mentioned in a previous post, many people get intimidated by a problem if it contains unfamiliar notation. Indeed, even for mathematicians, it often takes some time to start feeling comfortable with new terminology and abstract concepts. In this post I would like to get the reader to feel at home with the \({n \choose k}\) notation that I used in my first post. Often, a good way of doing this is to think about specific objects and quantities rather than abstract ones.
So imagine you walk into an ice cream store and there are five flavors available. You realize that you like them all equally. How many different ice cream cones can you end up with if you only want one scoop (this is a small local shop so there is only one type of cone)? Let us denote this quantity by \({5 \choose 1}\) (pronounced "five choose one"). Clearly, \({5 \choose 1} = 5\), the number of flavors. Your friend, on the other hand (did I mention you brought five friends with you?), wants two scoops on her cone, not both of the same flavor. How many different cones can she end up with (two cones are the same if they contain the same flavors)? We can compute this quantity, denoted by \({5 \choose 2}\) ("five choose two"), by noting that she has five choices for the first flavor and four choices for the second one (given the first choice). Now $5 \times 4=20$, but we have over-counted because by choosing pistachio first and strawberry second she ends up with the same cone as if she chose strawberry first and pistachio second. Hence, we need to divide by 2, and so ${5 \choose 2} = 10$. Now your second friend wants exactly three scoops, all of distinct flavors. We can compute this in a similar fashion, or we can just observe that choosing three flavors is equivalent to 'not choosing' two flavors. Hence, ${5 \choose 3} = {5 \choose 2} = 10$. You might have already guessed that your third friend wants exactly four scoops of distinct flavors, and again observing that choosing four flavors is equivalent to not choosing one, we get ${5 \choose 4} = {5 \choose 1} = 5$. Your fourth friend wants five scoops and your fifth friend wants zero scoops, just an empty cone. We can trivially see that ${5 \choose 5} = {5 \choose 0} = 1$. Luckily you have no sixth friend and so we're done with discussing ice cream!
Now there is nothing special about ice cream or the number five here. In general, ${n \choose k}$ denotes the number of ways we can select $k$ elements from a set of $n$ elements. I would like to finish this post by making another attempt at explaining the formula from my first post: \[{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.\]
Again, we do this by considering a specific scenario and concrete numbers. Five thousand students applied to university Uni (it's a very small school) and the size of the freshman class is to be one thousand. Uni accepts its students completely by lottery. The question is how many different freshman classes can they end up with? In our notation from above, this is \({5000 \choose 1000}\). Now Stu is one of the students who applied to Uni. Every possible freshman class will either contain Stu or not contain him. The total number of possible classes is the number of possible classes that contain Stu plus the number that do not contain him. The number of possible classes that do not contain Stu is ${4999 \choose 1000}$ because we want a class of 1000 students and we are choosing from everyone minus Stu. The number of possible classes that contain Stu is ${4999 \choose 999}$ since we need to choose 999 from everyone minus Stu. Hence, \[{5000 \choose 1000} = {4999 \choose 1000} + {4999 \choose 999}.\] Now replace 5000 by $n$ and 1000 by $k$!
So imagine you walk into an ice cream store and there are five flavors available. You realize that you like them all equally. How many different ice cream cones can you end up with if you only want one scoop (this is a small local shop so there is only one type of cone)? Let us denote this quantity by \({5 \choose 1}\) (pronounced "five choose one"). Clearly, \({5 \choose 1} = 5\), the number of flavors. Your friend, on the other hand (did I mention you brought five friends with you?), wants two scoops on her cone, not both of the same flavor. How many different cones can she end up with (two cones are the same if they contain the same flavors)? We can compute this quantity, denoted by \({5 \choose 2}\) ("five choose two"), by noting that she has five choices for the first flavor and four choices for the second one (given the first choice). Now $5 \times 4=20$, but we have over-counted because by choosing pistachio first and strawberry second she ends up with the same cone as if she chose strawberry first and pistachio second. Hence, we need to divide by 2, and so ${5 \choose 2} = 10$. Now your second friend wants exactly three scoops, all of distinct flavors. We can compute this in a similar fashion, or we can just observe that choosing three flavors is equivalent to 'not choosing' two flavors. Hence, ${5 \choose 3} = {5 \choose 2} = 10$. You might have already guessed that your third friend wants exactly four scoops of distinct flavors, and again observing that choosing four flavors is equivalent to not choosing one, we get ${5 \choose 4} = {5 \choose 1} = 5$. Your fourth friend wants five scoops and your fifth friend wants zero scoops, just an empty cone. We can trivially see that ${5 \choose 5} = {5 \choose 0} = 1$. Luckily you have no sixth friend and so we're done with discussing ice cream!
Now there is nothing special about ice cream or the number five here. In general, ${n \choose k}$ denotes the number of ways we can select $k$ elements from a set of $n$ elements. I would like to finish this post by making another attempt at explaining the formula from my first post: \[{n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}.\]
Again, we do this by considering a specific scenario and concrete numbers. Five thousand students applied to university Uni (it's a very small school) and the size of the freshman class is to be one thousand. Uni accepts its students completely by lottery. The question is how many different freshman classes can they end up with? In our notation from above, this is \({5000 \choose 1000}\). Now Stu is one of the students who applied to Uni. Every possible freshman class will either contain Stu or not contain him. The total number of possible classes is the number of possible classes that contain Stu plus the number that do not contain him. The number of possible classes that do not contain Stu is ${4999 \choose 1000}$ because we want a class of 1000 students and we are choosing from everyone minus Stu. The number of possible classes that contain Stu is ${4999 \choose 999}$ since we need to choose 999 from everyone minus Stu. Hence, \[{5000 \choose 1000} = {4999 \choose 1000} + {4999 \choose 999}.\] Now replace 5000 by $n$ and 1000 by $k$!
Subscribe to:
Posts (Atom)