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$!
Sunday, March 31, 2013
I continue my list of favorite problems
I remember this problem amazed me. I was surprised by its beautiful solution that I will show you later not to spoil some fun to those of you who wants to try to solve it.
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?
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?
Saturday, March 30, 2013
Fun with toothpicks
There are many fun problems that involve constructions with toothpicks. One nice thing about them is that they can be enjoyed by adults and kids alike, starting at a fairly young age. Here is by far my favorite problem of this type.
It is easy to make 4 equilateral triangles using 9 toothpicks (see below), but can you make 4 equilateral (and equal) triangles using just 6 toothpicks?
Here are a few easier problems with toothpicks that I got from this book by Martin Gardner.
Warning: the solution to the problem above is completely different from the ones below.
1) Move four toothpicks to make three identical squares (with no toothpicks left over).
I apologize for the image. I had some trouble aligning the toothpicks!
2) Move one toothpick and make the house face east instead of west.
3) Move two toothpicks to make four identical squares (with no toothpicks left over).
4) Move three toothpick so that the triangular pattern points down instead of up.
Please share your favorite toothpick problems!
It is easy to make 4 equilateral triangles using 9 toothpicks (see below), but can you make 4 equilateral (and equal) triangles using just 6 toothpicks?
Warning: the solution to the problem above is completely different from the ones below.
1) Move four toothpicks to make three identical squares (with no toothpicks left over).
I apologize for the image. I had some trouble aligning the toothpicks!
2) Move one toothpick and make the house face east instead of west.
Please share your favorite toothpick problems!
A disclaimer and a plea
I came to the realization that I am not very good at judging the difficulty of certain problems that I am very familiar with. In particular, in my previous post I said that the problem that I discussed can be understood without any prior knowledge of the subject. This is true, but I did not realize that it might not be so easy to follow for someone not familiar with the notation and terminology. This was pointed out to me by several people and in a future post I would like to approach the same subject but taking a step backwards. I will present some specific examples and explain the concepts a bit more.
One of the goals of this blog is to collect fun math problems that could get and keep kids (and potentially some adults :-) interested in the subject. But perhaps an equally important goal is to find good ways to present problems/concepts/solutions and to become aware of what sort of prerequisites are needed to understand them. To that end, it would be great to receive comments from people with different levels of mathematical familiarity, saying what is understandable and what needs more explanation, what are better/different ways of presenting the same material, and finally just which problems they like and which ones they find uninteresting and uninspiring. All comments are welcome as long as they are in some way relevant (and this should be interpreted in a very broad sense). We are also always very happy when people share their fun problems with us, whether they are related to something we post about or not.
One of the goals of this blog is to collect fun math problems that could get and keep kids (and potentially some adults :-) interested in the subject. But perhaps an equally important goal is to find good ways to present problems/concepts/solutions and to become aware of what sort of prerequisites are needed to understand them. To that end, it would be great to receive comments from people with different levels of mathematical familiarity, saying what is understandable and what needs more explanation, what are better/different ways of presenting the same material, and finally just which problems they like and which ones they find uninteresting and uninspiring. All comments are welcome as long as they are in some way relevant (and this should be interpreted in a very broad sense). We are also always very happy when people share their fun problems with us, whether they are related to something we post about or not.
Another favorite problem
One more from the list of my favorites.
Prove that there are 100 consecutive composite (nonprime) natural numbers.
I like it because everyone can understand and solve it, but the idea of the proof is relatively deep.
Prove that there are 100 consecutive composite (nonprime) natural numbers.
I like it because everyone can understand and solve it, but the idea of the proof is relatively deep.
Friday, March 29, 2013
My favorite problem
I should have started with my favorite problem. I gave it to different audiences, ages 10 to whatever. Usual results are always the same: two or three people do it correct. The problem is many times older than I am. Here it is (more modern variation).
The distance between A and B is 100 km. Two bicyclists start moving simultaneously towards each other from A and B respectively with speeds 10 km/h and 15 km/h. A dog starts running from A at the same moment as bicyclists do with the speed 20 km/h. When it reaches the second bicyclist, it turns back, runs until meeting the first one, turns again etc. The dog runs back and forth until bicyclists meet. What distance does it run?
As I mentioned above, the number of fifth graders who solved this problem is approximately the same as the number of high school seniors. BTW the results were the same in USA, Russia, and Ukraine :-)
The distance between A and B is 100 km. Two bicyclists start moving simultaneously towards each other from A and B respectively with speeds 10 km/h and 15 km/h. A dog starts running from A at the same moment as bicyclists do with the speed 20 km/h. When it reaches the second bicyclist, it turns back, runs until meeting the first one, turns again etc. The dog runs back and forth until bicyclists meet. What distance does it run?
As I mentioned above, the number of fifth graders who solved this problem is approximately the same as the number of high school seniors. BTW the results were the same in USA, Russia, and Ukraine :-)
Another good book
The only part of a school math course I have never taught is geometry. My favorite part of a standard school course :-) I come back to it from time to time in our Math club. But most of my students do not share my passion. Maybe one day I will ask to try to teach it. Not now, I am not ready yet.
BTW I should mention a book that I like. It connects geometry and nature (physics in particular) according to the ideas of a late V. Arnold. This book is Measurement by Paul Lockhart. I do enjoy it, there are many good geometry problems on each page. If you like geometry, open this book, and you will have a lot of fun.
BTW I should mention a book that I like. It connects geometry and nature (physics in particular) according to the ideas of a late V. Arnold. This book is Measurement by Paul Lockhart. I do enjoy it, there are many good geometry problems on each page. If you like geometry, open this book, and you will have a lot of fun.
Thursday, March 28, 2013
Construction problems in geometry II
First of all I would like to share with you a book that I got yesterday (it was a real surprise from Amazon, the book was delivered at 8:00 PM, and I expected it only today or tomorrow). The secrets of triangles is a great book. It includes, among others, a big section on constructing triangles using a compass and straight edge given three different elements of a triangle. I started to read it and I am really enjoying this reading.
Now back to problems. A separate group of construction problems consists of ones that should be solved by a compass only. My favorite one was introduced by Napoleon (yes, the emperor).
Given a segment of the length one, construct a segment of the length $\sqrt{2}$ units.
Obviously, you cannot draw a segment without a straight edge, just find the endpoints.
The solution to the problem from yesterday's post is given by two figures below.
Now back to problems. A separate group of construction problems consists of ones that should be solved by a compass only. My favorite one was introduced by Napoleon (yes, the emperor).
Given a segment of the length one, construct a segment of the length $\sqrt{2}$ units.
Obviously, you cannot draw a segment without a straight edge, just find the endpoints.
The solution to the problem from yesterday's post is given by two figures below.
AB is a given diameter and C is a given point. AC intercepts given circle at D, and BC intercepts it at E. Angles ADB and AEB are right angles because AB is a diameter. AE and BD are altitudes of BC and AC respectively. The line from C through the point their intersection is an altitude to AB.
Counting in two ways
One of the many reasons why I like the subject of combinatorics is that many problems in this area can be understood by someone with very little (or sometimes even zero) knowledge of the field. The solutions to these problems can sometimes be likewise simple (but often beautiful and insightful) or extremely difficult (a classic example is the Four Color Theorem which until very recently was a conjecture that remained unsolved for several hundred years). Here I will stick with problems of the first kind.
In this post I will present some formulas (or combinatorial identities) that can be explained by counting the same set of objects or quantities in two different ways. Here is a simple example:
Let \( {n \choose k}\) be the number of ways that k objects can be chosen from a set of n objects (this is the familiar binomial coefficient). We want to show that \[ {n\choose k} = {n-1 \choose k} + {n-1 \choose k-1}.\] Of course one can write out the formula for \({n \choose k}\) using factorials and then algebraically manipulate the right hand side so that it matches the left hand side. However, that will provide you with no intuition about what is actually going on. Here is the combinatorial, and much more insightful, explanation. As already mentioned, the left hand side counts the number of ways we can select k objects from a set of n objects. We want to show that the right hand side counts the same things. For a specific object (out of the n), every subset of k objects either contains it or does not (there is no third possibility!). Now it is easy to see that there are \({n-1 \choose k}\) ways to choose k objects without picking our specific one and there are \({n-1 \choose k-1}\) to choose k objects if we want to include our specific one. This explains the formula!
Here are a few more combinatorial identities that have similarly simple combinatorial interpretations:
\[\sum_{k=0}^n {n\choose k} = 2^n\]
\[ \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} {n \choose 2k} = 2^{n-1} \]
\[ \sum_{k=0}^m {n-k \choose m-k} = {n+1 \choose m} \]
\[ \sum_{k=0}^m {u \choose k}{v \choose m-k} = {u+v \choose m}\]
I will write explanations for these in a future post. All of these identities, as well as many others can be found in the book Combinatorial Problems and Exercises.
In this post I will present some formulas (or combinatorial identities) that can be explained by counting the same set of objects or quantities in two different ways. Here is a simple example:
Let \( {n \choose k}\) be the number of ways that k objects can be chosen from a set of n objects (this is the familiar binomial coefficient). We want to show that \[ {n\choose k} = {n-1 \choose k} + {n-1 \choose k-1}.\] Of course one can write out the formula for \({n \choose k}\) using factorials and then algebraically manipulate the right hand side so that it matches the left hand side. However, that will provide you with no intuition about what is actually going on. Here is the combinatorial, and much more insightful, explanation. As already mentioned, the left hand side counts the number of ways we can select k objects from a set of n objects. We want to show that the right hand side counts the same things. For a specific object (out of the n), every subset of k objects either contains it or does not (there is no third possibility!). Now it is easy to see that there are \({n-1 \choose k}\) ways to choose k objects without picking our specific one and there are \({n-1 \choose k-1}\) to choose k objects if we want to include our specific one. This explains the formula!
Here are a few more combinatorial identities that have similarly simple combinatorial interpretations:
\[\sum_{k=0}^n {n\choose k} = 2^n\]
\[ \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} {n \choose 2k} = 2^{n-1} \]
\[ \sum_{k=0}^m {n-k \choose m-k} = {n+1 \choose m} \]
\[ \sum_{k=0}^m {u \choose k}{v \choose m-k} = {u+v \choose m}\]
I will write explanations for these in a future post. All of these identities, as well as many others can be found in the book Combinatorial Problems and Exercises.
Wednesday, March 27, 2013
I am a rare guest on Google +, but today I went there and found two posts that I really liked - a picture of Paul Erdos and Terence Tao and a trailer of a new movie "Travelling salesman" about a group of four mathematicians who solved P vs. NP problem.
A picture is a great symbol of the continuity of math - the major figure of the 20th century explains something to a kid who is a face of 21st century math.
I am not so sure about movie, but I'll try to see it when it comes to theaters or DVDs.
A picture is a great symbol of the continuity of math - the major figure of the 20th century explains something to a kid who is a face of 21st century math.
I am not so sure about movie, but I'll try to see it when it comes to theaters or DVDs.
Construction problems in geometry I
I always loved construction problems. I will write a lot about them. Today I talked to my high school math teacher and among other things I mentioned constructions with a compass only. He replied that constructions with a straight edge only are the interesting kind as well. I have never seen one before, so he immediately gave me one to solve. It is relatively simple, but I like it.
You are given an arbitrary circle. A diameter is drawn in this circle. You are also given a point outside the circle. Using straight edge only, construct a perpendicular line from a given point to a given diameter.
When solving, do not forget that a perpendicular line can intercept a diameter itself or its continuation.
I will post a solution in the next post in order not to spoil someone a pleasure to find a solution by oneself.
You are given an arbitrary circle. A diameter is drawn in this circle. You are also given a point outside the circle. Using straight edge only, construct a perpendicular line from a given point to a given diameter.
When solving, do not forget that a perpendicular line can intercept a diameter itself or its continuation.
I will post a solution in the next post in order not to spoil someone a pleasure to find a solution by oneself.
Off we go! Why did we decide to start this blog? Because we love math! There are a lot of great problems, models, facts etc. that upon discovery we share with each other, or sometimes friends and family, but then forget or lose forever. Similarly, we lose track of fun/interesting websites, books, magazine articles, so that when we want to refer to them again, we cannot find the link or bookmark. One might ask why not to use Evernote, Diigo, or other such social bookmarking services? Mainly because we want to share and discuss our findings with others, test our ways of presenting stuff, and get new "gems" from our potential readers :-) In short, we would like to have some fun with math.
Not last on our list of priorities is to be able to share our love of math with our kids and grandchildren. By gathering problems of various levels now, we can share them with the kids when they become age appropriate. Of course we are also interested in cool ideas that we can already present to them, so we are always on the lookout for fun facts that can be shared with 3-4 year olds.
Not last on our list of priorities is to be able to share our love of math with our kids and grandchildren. By gathering problems of various levels now, we can share them with the kids when they become age appropriate. Of course we are also interested in cool ideas that we can already present to them, so we are always on the lookout for fun facts that can be shared with 3-4 year olds.
Subscribe to:
Posts (Atom)