Tuesday, April 30, 2019

Intersections of Three Circles

This problem occurred to me after seeing the diagram below in Glencoe Geometry (2018) p. 644. It's different from a problem discussed on Numberphile two weeks ago (https://www.youtube.com/watch?v=bRIL9kMJJSc&t=255s) since, in the video's terminology, we allow the circles to kiss.

To get started I borrowed a method that worked well for the "how many ways can 3 sticks touch" problem and considered numbers of intersections. With 0 intersections we have a version of the problem of how many ways 3 bags can be stuffed that @samjshah wrote about (https://samjshah.com/2015/04/03/stuffing-sacks/).
If there is just one intersection it must come from two circles kissing. There are two ways the circles can kiss. Each row below shows the possible placements for the third circle for one of the types of kissing.
2 intersections could come from a crossing or from two kisses. The last entry where all three circles cross through the same two intersections was the hardest for me to think of.

3 intersections could result from a crossing and a kiss, two crossings that share an intersection, or three kisses:
4 intersections could come from two crossings, three crossings that share an intersection, or one crossing and two kisses:

5 intersections can be made by two crosses and a kiss:
Finally, 6 intersections form when all three circles cross and none of the intersections overlap. I don't think I would have found the one in the top right position but saw it in the Numberphile video.
No more than six intersections are possible with three circles. In total that makes 4 + 9 + 10 + 9 + 9 + 3 + 4 = 48 possibilities. I hope I missed some - if I did please let me know! Check out the fascinating discussion started by @autismplusmath at <https://www.cake.co/conversations/lQlZDGj/how-many-ways-can-3-circles-intersect-how-many-ways-can-n-circles-intersect>, especially Factotum's numbering system. I'm sure a few of the above possibilities came from Factotum's enumeration.

Sunday, March 10, 2019

Repeat-Delete Sequences

This week I've been investigating what I call repeat-delete sequences. I have no theory about them, just observations and questions. I thought of them as a variation on the hailstone sequence. To generate a repeat-delete sequence with multiplier m, pick a number and repeatedly apply this rule:

  • If any consecutive digits repeat, delete them.
  • If no consecutive digits repeat, multiply the number by m.
I started with multiplier 2 (m = 2) and checked with a calculator that every (base 10) number up to 50 ended up in one of these cycles:
  • the degenerate 0-cycle (all numbers that consist only of repeats, like 11 or 7744 end up here regardless of the multiplier m)
  • the 1-cycle of length 23
  • the 5-cycle of length 23 (which consists of the terms of the 1-cycle times 10 with one exception)
Whereas every hailstone sequence appears to end up in a 1-cycle of length 3, these sequences appear to end up in one of three cycles. I have now verified this claim with a computer program up to 99999.

Multiplier 3 (m = 3)

The 1-cycle for multiplier 3 has length 25. 2 enters this cycle after 36 iterations.

2, 4, and 6 all enter this cycle after about 35 iterations, but 5 has its own cycle of length 24. For a while all the numbers that are not multiples of 5 enter the 1-cycle while the multiples of 5 either enter the 5-cycle or, if they are also multiples of 10, the 10-cycle (excluding degenerate cases). 29 is the first exception, which has its own cycle of length 24. Other exceptions quickly pile on. 31 enters the 5-cycle, 35 has its own cycle of length 25, and 37 is the first non-degenerate to enter the 0-cycle.

Interesting behavior in the hundreds includes 134 and 142 entering the 6375-cycle of length 25. 175 enters the 425-cycle of length 13, which is the first cycle we've seen whose length isn't about 25. (Are there reasons any of these cycles have the lengths they do?) It appears that if we keep looking we will keep finding more cycles. Here are two lists of cycles. The list on the left contains cycles reached by numbers less than 10,000. The right list is cycles for numbers less than 100,000. Why are the smallest numbers in each cycle all divisible by 5 except for 29?

Using Computer Power

I was having a fun time working out these sequences with a calculator, but I started to run into trouble with m = 5. The number one didn't seem to enter a cycle, so I skipped to three and found that it entered the 9375-cycle of length 28. 7 entered the 875-cycle of length 41. The other multipliers had started with 1-cycles and 5-cycles - these were some (relatively) big numbers!

I switched to m = 7 and found that every number seemed to act differently:

I then took some time to write a computer program. The first thing I wanted to do when I had the program running was try some big starting numbers with big multipliers. It seemed that multipliers could get up into the hundreds and the starting numbers could exceed the trillions and the sequence still would enter a cycle. Here are some random facts I noted:
  • 19394820483094829394 after 1219 iterations with multiplier 93 becomes 990044055 and then enters the 0-cycle
  • 19394820483094829394 with multiplier 219 eventually enters a 4-cycle of length 3810
  • Applying multiplier 613 to 4 yields 7 after 2646 iterations. 7 yields 5 after 1732 iterations. 5 yields 2 after 1166 iterations. 2 yields 50 after 3836 iterations. 50 yields 20 after 1165 iterations. Turns out that the 2-cycle has length 10,004.
Multipliers and their Cycles

Here are the cycles of some multipliers for starting numbers less than 100,000:
Click here for a file that lists all the cycles for multipliers up to 99 for starting numbers up to 99. What do you notice and wonder? I wonder why some multipliers send numbers to a small number of cycles while others seem to explode.

Does every multiplier create cycles? I would imagine that large enough multipliers would overwhelm the deletion of repeats and yield sequences that increase without bound, but I don't know how large the multipliers would have to be. Multipliers as large as 9147 still produce cycles for small inputs:
  • 1 enters the 1-cycle of length 8713
  • 2, 3, and 4, and 5 enter the 5-cycle of length 35,375
Are there any patterns that can be explained in the lengths of the cycles? For example, with multiplier 1591 we find these two cycles:
  • 5 enters the 78-cycle of length 8122
  • 7 enters the 52-cycle of length 8121
Could it be mere coincidence that the length of these cycles differs by one?

Please share any insight you have into these sequences. Have you explored any other variations on the hailstone sequence?

Sunday, February 3, 2019

Partitions of a Triangle into Four Triangles

I started working on this problem a couple days ago and then found Ed Pegg Jr.'s page on the subject: <http://www.mathpuzzle.com/triangle.html>. There I found the great idea to call certain partitions prime. We call a partition prime if it is not a refinement of any partition but the trivial partition. (Luke Janicke brought up the notion of triviality on Twitter.) For example, the partition above on the right is prime. The others are refinements of the two-triangle partition.

To enumerate the partitions of a triangle into four triangles, we could start by looking at refinements of the partitions above. We might guess that there are nine ways to refine a three-triangle partition into a four-triangle partition, because there are three ways to cut a triangle into two triangles (pick a vertex to cut from) and three triangles in the partition. But the number is reduced since we are only considering "distinct" partitions. (Can you say exactly what we mean by "distinct" in this setting?)

For example, of the nine candidate refinements below two are equivalent.

The same situation arises for these refinements:

If we start with a partition with more symmetry there are more duplicates. These refinements duplicate some from the previous batches as well.

The only prime three-triangle partition has just two distinct refinements.

Finally, there are three primes:
In total there are 23 partitions of a triangle into four triangles.

Thursday, January 17, 2019

The Dot Product and Angles Between Vectors

Last year I taught the dot product for the first time but was unhappy with the presentation. I gave the algebraic and geometric definitions of the dot product and we verified their equivalence for one example. Then we started using the dot product to find angles between vectors.

This year I hoped we could arrive at the dot product somehow instead of pulling it from a hat. We started with the problem of finding angles between vectors and ended up deriving the two definitions of the dot product simultaneously.

Implementing Dan Meyer's "headache-aspirin" philosophy, we started with an example that I thought my students might answer by mere inspection: <2, 2> and <-3, 0>. I thought a headache would be created by the next problem where the angle could not be easily seen, and I could offer the Law of Cosines as aspirin. But my intentions backfired in a nice way. Although some students could see the 135 degree angle and explained how they broke it down into 90 and 45 degree angles, other students already had a headache and demanded their aspirin! So we used the Law of Cosines right away on this example.

Students solved a few more problems this way:

Then I told everyone that this method could be simplified into a real nice equation and asked if they wanted to try to get it. Some students would've been happy to continue with the now familiar method, but others asked for the equation, so we worked through it on the board together:

I was nervous that I would lose students right at the beginning writing the vector c as a - b because unfortunately we hadn't done much work visualizing vector subtraction. But students agreed that b + c = a and then we solved for c. On the side (not shown above) we calculated the components of vector c as a - b = <a1,a2> - <b1,b2> = <a1-b1, a2-b2> and then substituted these into our Pythagorean equation for magnitude. Students seemed to enjoy running through the "box method" to expand the left side, but of course the most fun part is all the cancellation that leads to the final equation!

To me this process was quite satisfying, but I'm curious about other pathways. I just checked seven precalculus textbooks from a little over a decade ago and saw that they all introduce the dot product by its algebraic definition and then either simply state an equation for the angle between vectors or derive it using the Law of Cosines. A few of the textbooks first went through properties of the dot product and then used some of these in the derivation (e.g. that the dot product of a vector with itself is the square of its magnitude), which seems too laborious. How do you teach the dot product? Any ideas will be much appreciated.

Sunday, September 23, 2018

Precalculus - Week #1

The day before school started I was driving around to office supply stores buying up their quad ruled composition books. Over the summer I had wondered how to structure Precalculus to better connect its topics with greater coherence and started working on some problems from Phillips Exeter Academy <https://www.exeter.edu/mathproblems>. I realized that I wanted my students to do lots of work on coordinate grids and that maybe having all their work connected in a book instead of scattered on different sheets would help them see the connectedness of the subject itself. After the first week I am very glad we started using the notebooks!

Day 1

After discussing "perseverance" (from Mathematical Practice #1) and distributing the notebooks I told everyone to skip the first page (where we would put our Skills List) and draw a 4x4 set of dots where we would start working on the first problem of Dan Finkel's A Mathematician at Play (AMAP) #1 <https://mathforlove.com/2018/01/mathematician-at-play-puzzle-1/>. It is easy to demonstrate perseverance at this problem - keep drawing more polygons! Every hour a student solved the puzzle and every hour a student argued that 16 is the maximum number of sides due to the number of dots (Mathematical Practice #3). I asked students how we could extend the problem and they said we could try a 5x5 set of dots. I regret rushing on to a new problem in third hour. During the other hours I let the problem take up the whole time and many students were engaged up to the last minute, though no one was able to draw a 25-sided polygon!

Day 2

We began with #14 from Martin Gardner's My Best Mathematical and Logic Puzzles: arrange 12 matches to form a polygon with area 4. It's another good opportunity for students to exercise creativity and one solution provides an opportunity to review area of triangles and the 3-4-5 right triangle.

After having students start setting up the Skills List in the front of their notebook, we started working on the second problem of Finkel's AMAP #2 <https://mathforlove.com/2018/01/a-mathematician-at-play-puzzle-2/>. Really we only worked on the first part of the problem: finding areas of "grid squares." Simply drawing the squares primes the mind to think about perpendicularity! Many students immediately saw the area of the first square. Different classes proposed different methods for finding the areas of the other squares. Some classes added triangles around the outside of the square to make a larger square. Other classes dissected the square into four triangles and a smaller square.

Day 3

We started the hour with one more example of finding the area of a grid square, then used whatever method we had adopted to prove the Pythagorean Theorem.

After we used the Pythagorean Theorem to find some distances traveled and some distances between pairs of points in the xy-plane, students worked on two problems from Exeter Math (2.5, 2.13) and a similar problem I made up based on 2.23.

Here is the list of problems that students pasted in their notebooks:

Day 4

The last day of the week students were introduced to vectors with the following set of problems (based on Exeter 2.22 (#10), 2.73 (#11), and 2.87-88 (#13-14)):

#10 created good class discussion. Students described triangle ABC as being moved 6 to the right and 2 up to produce triangle TUV, which we were able to formalize using a vector in component form. Many students immediately used this notation to describe the directed line segments in #11.

What I like about these selected Exeter problems is that they have both a rote procedural component (plot these points) and a conceptual component (what type of figure is this? / what do these figures have in common?). I believe Dan Meyer wrote somewhere (probably while expounding his headache-aspirin philosophy) that while carrying out a simple mechanical process, resources in the brain are freed up to think about that process.

Tuesday, July 10, 2018

Paths, Combinations, Simplices, and Sums

This summer I've been studying "Pascal's" triangle a lot. Here's what I learned:

1. Paths

I used to think my three-part lesson on binomial expansion was pretty slick. We would start with (a+b)^0 and work up, applying our recently learned (or re-learned) polynomial multiplication skills. (a+b)^4 is a lot of fun because some students work it out as (a+b)(a+b)^3 while others use (a+b)^2(a+b)^2. Then there is a sudden break in the lesson and we start computing the rows of "Pascal's" triangle. After we get pretty far I ask the class why I would have us write out all these numbers. Could they help us with our powers of (a+b)? It takes a while before any light bulbs turn on. As they flicker on, I ask my "enlightened" students to try writing out the next power of (a+b) using the pattern they see.

The part of the lesson that bothers me now is my introduction of "Pascal's" triangle and the superficiality of our connection between the entries in the triangle and the coefficients in the binomial expansion. I would start by writing out the first few rows of the triangle and then either just tell students the rule for generating further rows, or ask students if they could see a pattern. And later, when students saw the connection to binomial expansion, we would just blindly exploit this magic coincidence instead of seeking to understand it.

It is more natural to start with the structure of "Pascal's" triangle and then ask students a question that enables them to fill in all the numbers on their own. The structure we start with is an infinite complete binary tree and the question we ask of a given node is: how many paths descend to it from the root node? But we won't get so wordy with students when we can just show them a picture:
They will be able to fill in the entries of the triangle and then even notice and justify the rule. Every path to a point either passes through its upper left neighbor or its upper right neighbor. So to figure out the number of paths to a point, add up the number of paths to each of its upper neighbors.

To connect these "path numbers" to the binomial expansion coefficients, I was inspired by an old blog post by Sam Shah (https://samjshah.com/2016/09/29/binomial-expansion/) and also a comment by Scott Farrar (@farrarscott). Every path can be thought of as a sequence of choices between left and right.
Similarly, every term in the full expansion of (L + R)^n can be thought of as a sequence of choices between left and right. Notice how the above triangle illustrates the expansion of, say, (L+R)^3:
(LL + LR + RL + RR)(L+R)
(LL)(L+R) + (LR+RL)(L+R) + (RR)(L+R)
Constructing "Pascal's" triangle using paths through a binary tree helps develop the connection with binomial expansion. It is also easy to see that the sum of row n is 2^n, since there are 2^n ways to make n choices between left and right.

By the way, why should we call it "Pascal's" triangle when we knew about it long before Blaise Pascal?

2. Combinations

In dating apps we swipe left to reject and swipe right to express interest. Along these lines, taking a path through our binary tree can be seen as generating a set of objects. Each choice between left and right becomes a choice to exclude or include some particular object. Compare this diagram with the one above:
For another way to see the correspondence, consider that a binary path can be determined by giving the positions of just the right swipes. We could communicate LRRL by indicating that the only right swipes are the second and third. And if our second and third objects are b and c, LRRL gives us the set {b,c}.
Things start to get interesting if we think of our sets as literal boxes and consider how we might stack them. Imagine constructing the triangle by taking the stack of boxes to your left and putting a certain type of object in every box, leaving the stack to your right alone, and then pushing these two stacks together. Here is one way we could stack our boxes:
This drawing shows a few more stacks of boxes without any labels or arrows in the way:
Extending this drawing to the left would be easy. There is a constant sequence of unit cubes, a successively taller sequence of simple stacks, a sequence of triangular staircases, and finally a sequence of tetrahedral stacks. Just as we could not construct the tetrahedral stacks out of squares, extending this drawing to the right any further would exhaust the three dimensions of our cubes. We might have some luck if we switched from cubes to tesseracts, but there are other ways to get a glimpse these higher-dimensional analogues.

3. Simplices

One option is to switch from boxes/cubes/tesseracts to points. And instead of stacking them (which meant unifying certain faces for the cubes) we'll draw line segments between them. If we do this we'll end up with simplexical figures. I hadn't much idea what simplices were until around a month ago, which is probably why I failed the second semester of Honors Analysis.

Basically, the simplices are to the triangle what the hypercubes are to the square. If you have an n-cube you can make an (n+1)-cube. Just copy your n-cube by translating it along a new dimension and then draw a line segment between each point of your n-cube and its image in the copy. So a 0-cube (point) connects to another 0-cube (point) to make a 1-cube (line segment). A 1-cube connects to another 1-cube to make a 2-cube (square). A 2-cube gets another 2-cube to make a 3-cube (cube).
Similarly, if you have an n-simplex you can make an (n+1)-simplex. Just find a point outside your n-dimensional system and draw a line segment between each point of your n-simplex and this new point. Connect a point to all the points in a 0-simplex (point) to make a 1-simplex (line segment). Connect a point to all the points in a 1-simplex to make a 2-simplex (triangle). Join a point to a 2-simplex to make a 3-simplex (tetrahedron). And the tetrahedron becomes a 4-simplex (5-cell).
Here is another version of our drawing with simplices. Extending the drawing to the right more is left as an exercise for the reader!
It's possible to "see" the higher-dimensional simplexical numbers by collapsing everything down a dimension. We can start by collapsing line segments into numbers.
We can continue this process by collapsing stacks of numbers into triangular numbers.
We could continue the process indefinitely, next collapsing stacks of triangular numbers to make tetrahedral numbers.

4. Sums

Once we see the triangular figures as stacks of line segments, the tetrahedral figures as stacks of triangular figures, and in general the (n+1)-simplexical figures as stacks of n-simplexical figures, we are ready to view the n-simplexical numbers as sums. 1 + 2 + 3 + 4 + 5 is T(5) = 15, the fifth triangular number. Similarly, T(1) + T(2) + T(3) + T(4) + T(5) is 35, the fifth tetrahedral number. Continuing this pattern, the sum of the first five tetrahedral numbers is 70, the fifth 4-simplexical number. Try locating these numbers on "Pascal's" triangle. We can make a general statement:

The sum of the first m n-simplexical numbers
is the mth (n+1)-simplexical number.

As a final thought, consider writing the entries of "Pascal's" triangle using sigma notation. We can then write a funny-looking formula.
That concludes my thoughts about "Pascal's" triangle. Please let me know if you can offer more insight, correct any of my mistakes, or are inspired to do any interesting math!