Saturday, June 30, 2018

Sets of Numbers

I used to introduce sets of numbers by asking students to name some numbers that I then write on the board. At first students name small positive integers, but with encouragement to be more adventurous they name negatives and fractions and maybe even pi or infinity! Then I would draw circles around the numbers and (because all the numbers were placed carefully) we'd get something like the usual image of sets of numbers:

I now find this sort of image problematic, because it makes ours sets of numbers look like biological taxonomy. Look at how the numbers sit in their places isolated, as if they were individual organisms out there waiting to be sorted into groups. In Science and the Modern World, Alfred North Whitehead contrasts biological classification with mathematical measurement:
The practical counsel to be derived from Pythagoras, is to measure, and thus to express quality in terms of numerically determined quantity. But the biological sciences, then and till our own time, have been overwhelmingly classificatory. Accordingly, Aristotle by his Logic throws the emphasis on classification. The popularity of Aristotelian Logic retarded the advance of physical science throughout the Middle Ages. ... Classification is a halfway house between the immediate concreteness of the individual thing and the complete abstraction of mathematical notions. ... Classification is necessary. But unless you can progress from classification to mathematics, your reasoning will not take you very far. (p. 28)
We need an image that shows that we are doing more than classifying in the biological sense. Our sets of numbers are profanely presented above as blobs, mere collections of elements. But numbers are not individuals. They are positions in structures. Whereas we can first familiarize ourselves with the properties of an individual organism and later determine its relationship to other organisms, the only properties a number has are its relationships to other numbers. As Willard Van Orman Quine writes in Ontological Relativity, "numbers ... are known only by their laws." That's why I propose a sort of image like this one, that shows some of the structure of our sets of numbers, both some structure within each set of numbers and also some structural relationships between the sets of numbers:

Note that in the first image the number zero occurs exactly once, whereas in the second image there is a separate zero in each set of numbers. This aspect might please Bertrand Russell, who wrote in his Introduction to Mathematical Philosophy that
One of the mistakes that have delayed the discovery of correct definitions in this region is the common idea that each extension of number included the previous sorts as special cases. It was thought that, in dealing with positive and negative integers, the positive integers might be identified with the original signless integers. Again it was thought that a fraction whose denominator is 1 may be identified with the natural number which is its numerator. ... All these suppositions were erroneous, and must be discarded, as we shall find, if correct definitions are to be given. (p. 63-64)
We could insist that the natural numbers are not a subset of the integers, but instead that the natural numbers are only isomorphic to a subset of the integers. In any case, I hope we will start using images that display some of the structure of our sets of numbers and maybe even suggest the possibility of further sets of numbers. Where are the quaternions and further extensions of the complex numbers?

What about the surreal numbers, which deepen the sort of "completeness" the real numbers bring?

If you have a good image of our number sets or can improve upon my attempt, please share!

Tuesday, June 12, 2018

Shape-Counting Problem #3

How many triangles are there in these figures? I found this problem more challenging than Shape-Counting Problem #1 and Problem #2. In this case I used a recursive problem-solving approach that led to a formula that I then proved using mathematical induction. Let's begin by introducing some terminology. How about we say that all the figures in the second column have two segments coming from the left or two left segments. Every figure in the third row has three right segments. And let's say that is the number of left segments and m is the number of right segments.

Look at the figures with n = 1 in the first column.
It's the triangular numbers again! I haven't found a shape-counting problem that doesn't involve the triangular numbers. Check out my explanations for the first two problems if you'd like more insight.
If n = 1, there are T(m) triangles.

Now look at the figures with n = 2 in the second column. The figure with n = 2 and m = 1 has already been dealt with through its mirror image in the first column, so let's jump to m = 2.
If we think of the figure as being split into an upper piece and a lower piece by the interior left segment, then we can count the triangles in the lower piece (blue), the triangles in the upper piece (red), and the triangles that overlap (green).
Notice that for the blue regions and green regions we get triangular numbers, but in the red region the number of triangles is just the number of right segments. Now that the general pattern has been illustrated, I will sometimes just color the regions and omit a thorough inventory of every triangle.
It looks like we're ready to write a formula for figures in the second column.
If = 2, there are 2T(m) + m triangles.

Let's advance to the third column (n = 3) and skip m = 1 and m = 2 since we've already covered their mirror images. Recursive thinking will really start to come in handy now. In everything that follows the blue region will be a figure for which we have already developed a formula, the red region will represent all the triangles outside the blue region, and the green regions will represent the triangles that overlap. Here's how it looks for n = m = 3.
The structure is similar for n = 3 and m = 4.
And I think we're ready for another formula.
If n = 3, there are 3T(m) + 3m triangles.

Once we're ready we can look at all the formulas we've written for the columns and see if we can figure out how n fits into the formula. For me personally, I had to work out the formula for one more column before really seeing the pattern. Here's how things turned out for n = 4.
I'd like to solve!
If n = 1, there are T(m) triangles.
If n = 2, there are 2T(m) + m triangles.
If n = 3, there are 3T(m) + 3m triangles.
If n = 4, there are 4T(m) + 6m triangles.
For any n, there are nT(m) + mT(n-1) triangles.

I was so delighted to yet again see my friends, the triangular numbers, this time as coefficients in a sequence of formulas. But I also thought the formula must be wrong, because it lacked symmetry between n and m. It turns out that there is symmetry after all, because
nT(m) + mT(n-1) = nT(m-1) + mT(n).

Proof by Induction
If n = 1, the number of triangles is T(m). In this case the formula gives
nT(m) + mT(n-1) = 1T(m) + mT(0) = T(m) + m(0) = T(m),
so the base case holds.
Suppose that if n = k, the number of triangles is kT(m) + mT(k-1). We want to show that if n = k+1, the number of triangles is (k+1)T(m) + mT(k).
By the induction hypothesis, there are kT(m) + mT(k-1) triangles in the blue region. There are T(m) triangles that can be formed by selecting two elements from among the m right segments and the base of the figure. Finally, for each of the k interior left segments there are m triangles that can be formed by using that interior segment and the left segment on the perimeter of the figure. Taking the sum of all these triangles we get
kT(m) + mT(k-1) + T(m) + km
= (k+1)T(m) + m(T(k-1)+k)
= (k+1)T(m) + mT(k).

Summary of Shape-Counting Problems #1-3
Here is a rough summary of the formulas for the first three shape-counting problems I've written about:
It's quite beautiful how the triangular numbers appear in all these formulas, and it's possible to gain a deeper understanding of all these formulas by thinking about the combinatorial meaning of the triangular numbers. My route to the last formula in particular was rather tortured. Can you see how to justify the formula just by taking combinations of line segments? Anyway, stay tuned... the most exciting shape-counting problems are yet to come!

Monday, June 4, 2018

Shape-Counting Problem #2

How many rectangles are there in a 3 x 4 grid? The obvious generalization is to ask how many rectangles there are in an x m grid. As with the first shape-counting problem, we get a two-dimensional array of problems:
Again, the easiest problems to solve are the ones in the top row and the ones in the leftmost column. As this picture illustrates, the number of rectangles in a 1 x m grid is T(m), the mth triangular number.
Similarly, the number of rectangles in an n x 1 grid is T(n). It turns out that we can use the solutions to these problems to solve every other problem. There is a one-to-one correspondence between rectangles in an n x m grid and pairs of rectangles from the n x 1 and 1 x m grids.
So the number of rectangles in an n x m grid is T(n)*T(m). For the 3 x 4 grid that's T(3)*T(4) = 6*10 = 60. Notice the similarity with the first shape-counting problem. To get the solution to a given problem in our array, just multiply the solution to the leftmost problem in the row by the solution to the top problem in the column.

Common Factors
The way I just explained the solution is not the way I originally figured it out. To arrive at the solution I looked at a particular example, found a product that gave the number of each type of rectangle, and then factored.
So working on this problem might provide students a good opportunity to apply their factoring skills.

Summation Notation
Another way to solve the problem is to manipulate some nasty sigma notation. We might realize that the number of rectangles in an n x m grid is the sum of all the answers to these questions: how many i x j rectangles are there in an n x m grid? For example, how many 5 x 8 rectangles are there in a 12 x 17 grid? The answer is (12 - 4)(17 - 7). The number of i x j rectangles in a n x m grid is (n - i + 1)(m - j + 1). So the total number of rectangles in an n x m grid is this double summation:
If you evaluate this sum for some particular values like n = 3 and m = 4 you can figure out the form of the solution like we did above. Alternatively, you can simplify the summation by realizing that
and then manipulating the sum like this:
Thanks for reading! If you solved the problem a different way or have any ideas about how this task could be implemented with students, I would be excited to hear from you!