gtMath

Prerequisites: Induction

For those of you who have never heard of it, the Putnam exam is a test for college students (mostly math majors) that universities throughout the country compete in. The test is hard- there are 12 questions (in two sets of 6, for which you get three hours per set), and the median score is 0. I've taken it a few times myself, and I think my record was 2 questions correct, which I was pretty pleased with.

Anyway, a lot of schools have a team that prepares for this test (at Dartmouth, this consisted of a bunch of people gathering for free Raymunto's pizza, which is a surefire way to get folks to show up there), and consequently, you can find a lot of the practice problems on the internet. In fact, you can find archives of past Putnam exams and solutions online, for example, here.

Anyway, the reason I mentioned all this is that I found the following problem in a Putnam practice document from Northwestern:

There are $n$ great circles drawn on the surface of a sphere such that no more than 2 intersect at any point. Into how many regions do the circles divide the surface of the sphere?

Now, I'll get to explaining what a great circle is in a second, but first, I'll explain what made me want to write a post about this problem in the first place. Obviously, the solution must be some function of $n$. Ok, great. But what really #GroundMyGears was that in the solutions in this document, they basically looked at the first few cases, $n=1,2,3,4,...$, guessed the answer, and then proved it was correct by induction. Don't get me wrong- this was all correct and everything, but I just felt like guessing the answer and then proving it works by induction was kind of a cop-out in this case. So I worked out the same answer in what I thought was a more satisfying way, and that's what I'm going to show you here. This method works for other recursions as well, so it may actually be useful to you some day.

Ok, first of all, I just said it, and it's in the title of the post, so what is a recursion? A recursion defines an object in terms of itself.

What???

Ok, maybe best to use an example here, and I promise you'll see what I mean: the factorial of a positive integer $n$, denoted $n!$, is defined as the product of the positive integers 1 through $n$. In symbols, $n! = n(n-1)(n-2)...(3)(2)(1)$, or more succinctly, $n! = \prod_{i=1}^{n}{i}$. Here's where it gets interesting: factorials can be defined in terms of themselves as follows: $$
1! = 1 \\
\forall n > 1, n! = n \cdot (n-1)!
$$ Clearly, this gives the same definition as above, but now we've defined the factorial function in terms of itself, but for smaller values of the input variable. This is crucial in computer science, where we can use this method to specify infinitely many (or more precisely, an arbitrarily large number of) objects in a finite number of steps.

Recursion is also very closely related to induction. Properties of recursively defined functions and sets can often be proved by an induction argument that follows the recursive definition (sentence copy/pasted from Wikipedia, thank you very much). A recursive function definition always needs a base case whose value is specified, and then an inductive definition of the function for greater input values, in terms of the values of the function for smaller inputs.

Hopefully the above got the point across (if not, leave a question in the comments section). Let's shift gears now and talk about great circles.

A great circle of a sphere is a circle drawn on the surface of the sphere, whose center coincides with the sphere's center. All great circles have the same radius and diameter as the sphere itself. Another way to put it is that a great circle is the intersection of a sphere and a plane which passes through its center. These are the largest circles that can be drawn on the surface of a sphere. Smaller circles (called small circles) arise when a plane intersects a sphere and does not pass through its center. In the diagram below, the red circle is a great circle, and the blue one is a small circle:

The equator and meridian are examples of great circles on the surface of the earth. While I'm talking about great circles, it's worth mentioning, though we won't need it in this post, that the shortest path between any two points on the surface of a sphere is the great circle arc (i.e. piece of the great circle) connecting them. It's also worth mentioning (and we will need this fact) that any two great circles intersect at two points (can you see why?).

On that note, let's get back to the question about $n$ great circles on the surface of the sphere. Let's call the number of regions on the surface after we've drawn $n$ great circles $R(n)$. With one circle, the sphere is divided into 2 halves, or hemispheres (hemi- is a prefix that means half, as do demi- and semi- by the way, but for some reason, the word turned out to be hemisphere and not semisphere or demisphere...). So $R(1)=2$.

If we add a second circle, it will intersect the first at 2 points, cutting the existing two regions into 4, so $R(2)=4$. Now, a third great circle will intersect the first two at 2 points each. Remember that the question prohibited an intersection at the existing intersection points (if it hit one, it would hit both), so the third circle again cuts the existing regions each in two, implying $R(3)=8$.

Things get trickier on the fourth circle, which is tougher to picture without a diagram. See the green and red circles in the below diagram, which are the fourth and fifth great circles drawn on the surface after the first 3 black ones:
Note first of all that the fourth circle (and each one thereafter) does not intersect every existing region. The fourth circle intersects 6 of the 8 existing regions, and in fact, since each great circle is the intersection of a plane with the sphere, the fact that the fourth circle hits 6 regions is explained in the post The Plane in ${\Bbb R}^3$- I'll leave it to you to explore the connection there (and it actually does not depend on the angles the first three planes make with each other). So the fourth circle adds 6 new regions (one for each of the 6 it intersected and thus cut into two) so that $R(4)=8+6=14$.

In general, we can see by the same logic that the $n^{\scr th}$ circle intersects each of the existing $n-1$ circles twice. Since none of those intersection points existed before drawing the $n^{\scr th}$ circle (because if one had, then we'd have three circles intersecting at one point, which isn't allowed), there must be $2(n-1)$ intersection points of the $n^{\scr th}$ circle with the original $n-1$ circles.

Also, you can see from the diagram that when we draw the $n^{\scr th}$ circle, each set of two new intersection points breaks the $n^{\scr th}$ circle into an arc which cuts one of the existing $R(n-1)$ regions into two new ones. The number of regions the circle intersects (and thus cuts into two) is $2(n-1)$, because if we walk around the $n^{\scr th}$ circle, there is one region after each of the $2(n-1)$ intersection points with the other circles.

The above two paragraphs give us our recursion: $$
\begin{align}
R(n) &= R(n-1) + 2(n-1), n \geq 2 \tag{1}\\[2mm]
R(1) &= 2 \tag{2}
\end{align}
$$ Note that we need only one initial condition because there is only an $R(n-1)$ term in the recursion equation. If there were also an $R(n-2)$ in there, we'd need both $R(1)$ and $R(2)$ to determine the value of $R$ for all values of $n$. So now that we have our recursion, let's solve the thing. For $n \geq 2$, rearranging $(1)$ gives $$R(n) - R(n-1) = 2(n-1) \tag{3}
$$ Since $(3)$ holds for every $n \geq 2$, we have $$
\begin{align}
R(n-1) - R(n-2) &= 2(n-2) \\[3mm]
R(n-2) - R(n-3) &= 2(n-3) \\[3mm]
\vdots \\[3mm]
R(2) - R(1) &= 2(1)
\end{align}
$$ Therefore: $$
\begin{align}
R(n) &= R(n) + 0 \\[3mm]
&= R(n) + (-R(n-1)+R(n-1)) + (-R(n-2)+R(n-2)) + \cdots + (-R(2)+R(2)) + (-R(1)+R(1)) \\[3mm]
&= (R(n)-R(n-1)) + (R(n-1)-R(n-2)) + \cdots + (R(2)-R(1)) + R(1) \\[3mm]
&\overset{(3)}{=} 2(n-1) + 2(n-2) + \cdots + 2(1) + R(1) \\[3mm]
&\overset{(2)}{=} 2(n-1) + 2(n-2) + \cdots + 2(1) + 2 \\[3mm]
&= \left( 2 \sum_{i=1}^{n-1}{i} \right) + 2 \\[3mm]
&= 2 \left( \dfrac{(n-1)(1+(n-1))}{2} \right) + 2 \tag{$\spadesuit$}\\[3mm]
&= (n-1)n+2 \\[3mm]
&= n^2 - n + 2
\end{align}
$$ where the equality $(\spadesuit)$ is because of the fact that an arithmetic series, i.e. a sum of $N$ terms, the first of which is $a_1$, the last of which is $a_N$, and with the difference between successive terms being a constant, has $\dfrac{N(a_1 + a_N)}{2}$ as its sum. Can you prove why?

So now we've solved for $R(n)$ for every value of $n$ using the recursion equation $(1)$ and the initial condition $(2)$.

I hope you found this interesting and maybe even useful. Thanks for reading, and please post any questions or comments in the comments section.

Prerequisites: Pool Part 1, Similar Triangles

In part 1, we showed how to pocket an object ball with some basic physics. In part 2, we'll derive simple methods for making bank and kick shots using similar triangles.

For all of the below, we'll assume, unless explicitly stated otherwise, that we can ignore the effects of spin on the balls that would alter their trajectories. In practice, English (side-spin) as well as topspin and backspin (sliding) will affect the trajectories and need to be taken into account for more complicated shots. For example, if the target ball is to be banked off a rail very close by, it will still be sliding upon contact, which changes its trajectory coming off the rail. Ball speed also affects the trajectory off the rails, since a faster ball compresses the rail more and changes the angle a bit. We'll ignore these effects in our analysis, which should suffice for most easier bank and kick shots you'll encounter, where you just need to hit the cue ball with medium speed and at center. If any good players are reading this, commentary is welcome on how to use spin on some of these shots.

The one-rail bank

In part 1, we looked at a straight shot into the side pocket. Now, suppose we have the following situation where the purple 4 ball is blocking the line to the side pocket:
We need to find an alternative to the shot from part 1. One solution would be to take the long-distance shot to the top-right corner pocket, but we're going to look at an alternative, the bank shot, where we hit the 2 off the top rail and into the bottom side pocket.

The key to executing this shot is the reflection principle, that the 2 will bounce off the rail at the same angle with which it bounces into the rail- angle in equals angle out. The problem is to find the correct point on the rail to hit the 2 into, where angle in = angle out will get the ball on a trajectory to the side pocket.

Take a look at the following diagram, which is the same layout, but with two triangles drawn on.
The angle $\theta$ is the angle in and out. If the contact point with the rail, $Q$, is chosen correctly, then the angle $\theta$ will be the correct one to send the 2 to the target pocket. Now, because the two $\theta$ angles are equal and the yellow line is drawn at a 90 degree angle to the rail, we know that angles $OQP$ and $SQR$ are also equal. Since angles $OPQ$ and $SRQ$ are both right angles and thus equal, the triangles $OPQ$ and $SRQ$ are similar by angle-angle.

Let's use the notation $L(\overline{AB})$ for the length of a line segment $\overline{AB}$. The similarity of triangles $OPQ$ and $SRQ$ implies that the ratios $\dfrac{L(\overline{PQ})}{L(\overline{QR})}$ and $\dfrac{L(\overline{OP})}{L(\overline{SR})}$ are equal.

Remember that $Q$ is still at an unknown position, but given the equality of those ratios, we can find it. $L(\overline{OP})$ and $L(\overline{SR})$ are known lengths, which can be measured in units of segments. One segment is the distance between two of the white diamonds (or sometimes they are circles) running along the sides of the table. In the diagram above, $L(\overline{OP})$ is just shy of 2 segments, and $L(\overline{SR})$ is just shy of 4 segments. Thus $\dfrac{L(\overline{PQ})}{L(\overline{QR})} \approx \dfrac{1}{2}$. Since $L(\overline{PR})$ is about 2 segments, we see that the correct position for $Q$ puts $L(\overline{PQ}) \approx \dfrac{2}{3}$ and $L(\overline{QR}) \approx \dfrac{4}{3}$.

Alternative method: parallel shifts

The ratio calculation above is relatively simple and works, but can be a bit annoying to work out while playing. There is an alternative method that achieves the same result without having to think about any ratio calculations.

Below is the same diagram as the previous one, but with the blue lines added in:
The slope of line $OQ$ is the same as the slope of line $MR$, i.e. the lines are parallel. You can prove this by assigning coordinates to each of the points and calculating the two slopes (it's probably easiest to assign $O=(0,0)$ and go from there). This being the case, we have an easier method for finding point $Q$:

1. Find the midpoint $M$ between the 2 ball and the target pocket.

2. Make a line (with your cue stick) from $M$ to the opposite pocket.

3. Move your cue, keeping it parallel, over to the 2 ball, and where it intersects the top rail is the target contact point $Q$.

A similar method will work for kick shots as well.

The one-rail kick

The kick shot is similar to the bank, except we hit the cue ball off a rail and into an object ball, as opposed to the bank, where we hit the cue ball straight into the object ball, which then bounces off a rail.

Take a look at the following diagram:
Here, we have the cue ball and 2 ball in the same places as before, but the cue ball's line to the 2 is blocked by the purple 4. In order to make contact with the 2, we need to hit the cue ball off a rail first to avoid hitting the 4 before the 2 (for example, if we're playing 9-ball, where you need to hit the lowest-numbered ball first or else give your opponent ball-in-hand).
The red triangles above show a set-up just like the bank above, with the two red triangles being similar. Now, instead of going to a pocket, the blue line goes to the point where the target ending spot lines up with the rail. I won't go through the whole thing again, since it's basically the same thing. Find $M$, draw a line from $M$ to the spot where the target ending position lines up with the rail, and parallel shift the line over to the cue ball to see where it needs to hit the rail.

The two-rail kick

This is a very difficult shot, but if you can make contact on these, then you'll save yourself from giving a good opponent ball-in-hand and running the table on you. Suppose we now have this set-up where there is no way to execute a one-rail kick and hit the 2 first:
Once again, the translucent cue ball is the desired position of the cue ball at contact, and as you can see, the only way to get it there is by hitting the cue ball off of at least two rails. We'll start by drawing a diagram similar to the ones above:
Note that this diagram is not exactly to scale, so some of the lines that should be parallel look a bit off. The same reason it is difficult to draw the diagram is the reason that this shot is trickier to work out than the one-rail kick: we need to work out the unknown contact point $C$, but the trouble is that a change in $C$ changes the angle off the bottom rail and thus also changes the unknown contact point $E$ on the second rail.

The reflection principle will hold at both $C$ and $E$, and we need to work it out so that the cue ball ends up at $G$. The three red triangles are all similar by angle-angle, and this fact gives us a few equations we can use to solve for the location of point $C$.

Define $x_1$ to be the length $L(\overline{BC})$ (unknown), $L_1 = L(\overline{BD})$ (known), $x_2 = L(\overline{DE})$ (unknown), and $L_2 = L(\overline{DF})$ (known). The known quantities can be measured in units of diamonds on the side of the table. Because of the similarity of the red triangles, we have: $$
\begin{align}
\dfrac{x_1}{L_1-x_1} &= \dfrac{L(\overline{AB})}{x_2} \tag{1} \\[3mm]
\dfrac{x_2}{L_2-x_2} &= \dfrac{L_1-x_1}{L(\overline{FG})} \tag{2}
\end{align}
$$ Solving $(1)$ and $(2)$ for $x_1$ gives the location of point $C$. One can do this by solving $(1)$ for $x_2$ and then plugging in the answer every time $x_2$ occurs in $(2)$. This is not very practical while playing, so once again, there is a midpoint/parallel shift method that you can implement easily.

1. Find the midpoint $M$ between $A$, the cue ball starting position, and $G$, the desired cue ball position at contact.

2. Make a line (with your cue stick) from $M$ to $D$, the corner pocket between the two rails off which you're kicking.

3. Move your cue, keeping it parallel, over to the cue ball, and where it intersects the bottom rail is the target contact point $C$.

So there you have it. The two-rail kick.

Now, there's an important point we completely ignored, and that's the effect of spin and, related to that, the fact that the rails are not rigid, but rather have some give and will compress when a ball contacts them and potentially alter the ball's trajectory coming off.

On the two-rail kick, in practice, we want to hit the ball along the lines we calculated above, but with a bit of running English, which means topspin + a bit of spin in the direction the ball will be moving (right English in the example above). I can't find anywhere on the internet why this is the case, but I suspect that it's because when the rail compresses and then launches the cue ball back out, the "launch" makes the angle off the rail greater. Running English compensates for that angle boost and also gives the ball some speed to "run" around the table.

The amount of spin depends on how close the contact point is to the corner pocket (point $D$ in the diagram) and also the speed with which the cue ball is hit.

For the simpler one-rail shots above, especially when the distances involved are relatively small and the cue ball isn't hit too hard (and thus the rail does not compress much), there is a bit of margin for error, and no fancy spin is necessary, but it is important for the two-rail kick where the ball must travel a long distance and with enough speed to go that distance.

I defer to better players to add to the spin point in the comments section or let me know if anything above is off.

Thanks for reading.

Prerequisites: Vectors

In this two-part post, we'll go through some of the basic geometry of pool/billiards.

In Part 2, we'll derive simple methods to make one-rail bank and kick shots (to be defined below). We'll also go briefly into an example of a two-rail kick, with which it's extremely difficult to actually pocket the target ball, but at least you can work your way out of some sticky situations and avoid giving your opponent ball-in-hand.

This analysis also works for mini-golf on flat surfaces, by the way.

How to pocket a ball

This section involves a bit of physics, which I'll explain for those who don't know it already, but you may need to quickly read up on vectors here before proceeding.

Suppose we have the following set-up:
The white ball is the cue ball, and we want to hit it into the 2 ball (the blue one, also known as the object ball) to pocket the latter in the side pocket on the top of the image.

In order to accomplish this, we need the cue ball, upon contact with the 2, to impart a force upon the latter which makes it move in the direction of the pocket. The way to make the force be in that direction is to hit such that the point of contact of the two balls lies along the line between the center of the pocket (where we want the object ball to go), and the center of the object ball as in the next diagram:
It's a subtle difference, but please note that you are aiming for the point of contact, and not the center of the cue ball, to lie along the yellow line upon contact with the 2. The translucent cue ball in the above diagram shows the desired cue ball position upon contact.

If you get this right, and hit the cue ball at center with a reasonable speed, then the force imparted on the 2 will be along the yellow line, and thus it will roll along the yellow line and into the pocket. This is Newton's second law at work, which states that if the mass (i.e. how many kilograms) of the 2 ball is $m$, and the force the cue ball imparts on the 2 is ${\bf F}$ (note that this is a vector quantity, which is why it has a direction, while the mass is a scalar), then ${\bf F} = m {\bf a}$, i.e. the 2 will gain an acceleration ${\bf a}$ due to the force ${\bf F}$. The units of the acceleration are meters per second squared, and thus the units of the force are killograms*meters per second squared, also called Newtons after the same Isaac Newton we were just talking about.

Acceleration is the change, both of magnitude and direction, in velocity per unit time (thus change over one second, in how many meters per second the ball is traveling at that moment). Velocity is just the vector quantity whose magnitude is the speed (in units of meters per second) and whose direction is the direction of motion of the ball. These quantities can all vary over time, as can the force. The ball's mass $m$ is a scalar quantity that is constant over time and is a measure of how much matter is contained in the ball. The heavier the ball, the more force it takes to accelerate the ball by an equivalent amount. That's what the magnitude part of the vector equation ${\bf F} = m {\bf a}$ tells us. The direction part tells us that the acceleration is in the same direction as the force.

Make sense? Ok good- if there are questions on that, they can go in the comments section or maybe I can do a separate post, but my point was that since the cue ball is round and thus contacts the (also round) 2 at exactly one point, the cue ball must impart a force on the 2 i the direction of the yellow line in the diagram above, and thus the 2 will accelerate along that line after the contact. Since no forces act on the ball that would cause it to deviate off of that line after the contact, it will continue along that line and thus into the side pocket.

Where does the cue ball go after the contact?

That's an important question, and good players need to take this into account when planning a series of shots.

As it turns out, the cue ball bounces off perpendicular to the yellow line as in the next diagram:

To see why this is the case, we need to use conservation of momentum. What does this mean? Well, momentum is the vector quantity $m{\bf v}$ where $m$ and ${\bf v}$ are mass and velocity as above. To say that momentum is conserved means that the momentum vector of a system of objects (for a system of multiple objects, this would be the vector sum of the individual momenta) remains constant in the absence of a net external force. In our system of two balls, the force between the balls would not qualify as external. Gravity would, but it is counteracted by the force of the table pushing back up on the balls, which causes them to not fall to the ground. Thus, ignoring friction, energy loss due to the sound of the balls' hitting, etc., the momentum of the system of the two balls is the same right before and right after the collision.

In the diagram above, we have labeled the velocities, and let's assume the cue and 2 have the same mass $m$. Momentum is conserved before and after the collision, which means: $$m{\bf v}_0 = m{\bf v}_1 + m{\bf v}_2
$$
Note that the 2 ball had no velocity initially, so the left-hand side of the equation has only the cue ball's momentum. The $m$'s cancel out to give the vector equation $${\bf v}_0 = {\bf v}_1 + {\bf v}_2 $$ which actually comprises 2 algebraic equations, one in the $x$-component and one in the $y$-component:
$$
\begin{align}
v_{0x} &= v_{1x} + v_{2x} \tag{1}\\[2mm]
v_{0y} &= v_{1y} + v_{2y} \tag{2}
\end{align}
 $$Now, we can use $(1)$ and $(2)$ to obtain: $$
\begin{align}
\| {\bf v}_0 \|^2 &= v_{0x}^2 + v_{0y}^2 \\[2mm]
&= (v_{1x} + v_{2x})^2 + (v_{1y} + v_{2y})^2 \\[2mm]
&= \| {\bf v}_1 \|^2 + \| {\bf v}_2 \|^2 + 2v_{1x}v_{2x} + 2v_{1y}v_{2y} \\[2mm]
&= \| {\bf v}_1 \|^2 + \| {\bf v}_2 \|^2 + 2({\bf v}_1 \cdot {\bf v}_2) \tag{3}
\end{align}
$$ We also know that the energy of the system is conserved. The energy of an object of mass $m$ and speed $v$ is $\frac{1}{2}mv^2$. Technically, this is only the kinetic energy (energy due to motion of a massive particle), but there is no potential energy in this system (e.g. an object high up about to fall and gain speed, and thus kinetic energy, would have potential energy).

Conservation of energy tells us that $$
\begin{align}
&\frac{1}{2} m \| {\bf v}_0 \|^2 = \frac{1}{2} m \| {\bf v}_1 \|^2 + \frac{1}{2} m \| {\bf v}_2 \|^2 \\[2mm]
\Longrightarrow \ &\| {\bf v}_0 \|^2 = \| {\bf v}_1 \|^2 + \| {\bf v}_2 \|^2 \tag{4}
\end{align}
$$ Subtracting equation $(4)$ from equation $(3)$ shows that ${\bf v}_1 \cdot {\bf v}_2 = 0$, i.e. ${\bf v}_1$ and ${\bf v}_2$ are perpendicular. This means that the cue ball indeed bounces off at a right angle to the direction of the 2 after contact.

In part 2 of this post, we'll explore bank and kick shots...

Remember those fun diagrams from high school geometry? This post is a refresher on similar triangles, which will be needed for a forthcoming post on billiard geometry, so stay tuned for that one...

Congruent Triangles

Two triangles (or any other shape for that matter) are called congruent if they are the same shape and size, except possibly rotated. Congruent triangles thus have three sides of the same length and three angles with the same measure. If you can prove that two triangles are congruent using a few of the sides and angles, then you know the other sides and angles are also equal.

How do you prove two triangles are congruent? It turns out any of the following will work:
- side side side (SSS)
- side angle side (SAS)
- angle side angle (ASA)
- angle angle side (AAS)
- hypotenuse and one leg length (for right triangles only)

So for example, if I have two triangles with side lengths 4 and 7 with a 30 degree angle in between, then they are congruent by SAS, and the other side and two angles are also equal.

Why do these formulas work? Because given, for example, that two sides and the angle in between are all equal, then the other pieces are predetermined. That means that a second triangle with the same SAS will have the same predetermined other pieces as well, i.e. is congruent to the first triangle.

To prove that SAS works, take some triangle $ABC$ in the plane, and assume without loss of generality that point $A$ is at $(0,0)$, $B$ is on the positive $x$-axis, and $C$ is somewhere above the $x$-axis (i.e. in the positive $y$ region). This is indeed without loss of generality, because if it isn't the case, we can move our triangle left/right/up/down and/or rotate it, all without changing its shape and size.

Given the length of segment $AB$ is $L_1$, we know that $B = (L_1,0)$. Given that the measure of angle $BAC$ is $\theta$ and the length of segment $AC$ is $L_2$, we know that $C = (L_2 \cos \theta , L_2 \sin \theta)$ (and that $\theta$ will be between 0 and 180 degrees, or 0 and $\pi$ in radians, because of the assumption that $C$ is above the $x$-axis). So we've determined all 3 vertices, and thus we know all the side lengths and angles.

There are other ways to prove these as well besides coordinate proofs like the one above, but I won't go further into it since it's not that exciting, and we can at least say we proved one of them now.

Note that the following are not sufficient to establish congruence:
- AAA (proves they are the same shape, but not necessarily same size)
- ASS (which doesn't even necessarily prove they are the same shape- can you see why?)

Similar Triangles

Two triangles (or any other shape) are called similar if they are the same shape, just different size, so one is a scaled up/down version of the other. This means that the three angles are the same, and the side lengths of the second triangle are $r$ times the side lengths of the first where $r>0$ is some fixed ratio. Congruence is the special case of similarity where $r=1$.

The same five criteria I mentioned for congruence also work to prove similarity, except that for the side comparisons, you need to show that they have a certain fixed ratio instead of being equal. Since the ratio can be any positive number, AAS and ASA just become AA; if any two angles are the same, the triangles are similar. We know the third angle is the same too because the three of them need to add up to 180, so AA is equivalent to AAA and is sufficient to prove similarity. For SAS and SSS, which have more than one side involved, you need to actually check the ratio of the sides.

One last comment here: to prove that the angles add up to 180, draw a straight line $L$ through one of the vertices which is parallel to the side of the triangle which is opposite that vertex. Then the angles between the triangle and $L$ are equal to the angles at the other two vertices. But the three angles at our first vertex obviously add up to 180 because they are on a straight line.

Brief off-topic foray:

Interestingly, the angles of a triangle do not necessarily add up to 180 if the triangle is drawn on a non-flat surface (in particular, if a neighborhood of a vertex isn't flat). For example, if you draw a triangle on the sphere of the earth which has a vertex at the north pole and two vertices on the equator, you can have all 3 angles be 90 degrees, in which case the angles add up to 270.

The analog of "straight lines" on a non-flat surface, which form the sides of a triangle, are the paths of shortest distance and are called geodesics. On a sphere, the geodesics are the great circle arcs, which are pieces of circles on on the surface whose radius is the entire radius of the sphere. The equator is a great circle on the surface of the earth, as is the line dividing the eastern and western hemispheres.

Thanks for reading. Please post any questions in the comments section.

There is a hallway with 100 lockers, numbered 1 through 100. They are all closed to begin with. 

 

There are also 100 kids, numbered 1 through 100. Each kid $n$ runs down the hall once, visiting each locker with a multiple of $n$ on it, opening it if it's closed or closing it if it's open.

 

Which lockers remain open at the end?

 

I've heard that this one is actually an interview question, though no one has ever asked it to me...

So kid 1 runs down the hallway and opens all multiples of 1 (i.e. all the lockers), leaving them all open. Kid number 2 then goes and closes 2, 4, 6, etc., i.e. all the evens.

Now, kid 3 visits 3, 6, 9, etc. and changes the state of each. So he'll close 3 (which kid #1 opened), open 6 (opened by 1 then closed by 2), close 9 (opened by 1), etc.

It's not going to be fast to go through each kid and write it out, though that would get you the answer. But what if there are 1,000 lockers/kids, or 1,000,000? The answer's the same in each case, and it's pretty cool.

To get there, start by considering a given locker- let's look at #48 as an example. Kids #1, 2, 3, 4, 6, 8, 12, 16, 24, and 48, or all the factors of 48, are going to visit this locker. Since there are 10 factors, the door will end up closed (and it will be opened then closed again 5 times in the process).

Now, this is where it gets good.

You can see from the example, or any other example you work through, that a locker will end up closed if it has an even number of visitors, or an even number of factors. Almost all the lockers have an even number of factors, because almost every factor has a "buddy." For 48, the "buddies" are 1 and 48, 2 and 24, 3 and 16, 4 and 12, and 6 and 8.

Which factors don't have a buddy?

It's the ones where the buddy is itself. Take locker 64 as an example. The factors are 1, 2, 4, 8, 16, 32, and 64. Notice that 8 has no buddy, because $64 = 8^2$. So this locker will end up open. It will get opened and closed again 3 times, but will be opened one additional time and remain open at the end.

The only numbers with an odd number of factors like this are the perfect squares, i.e. the set of integers that equal the square of another integer, 1, 4, 9, 16, 25, 36, etc.

So we got the answer; it's the perfect squares. Good job.

If you want to read the real nerdy stuff, go on; otherwise, thanks for reading.

Unique Prime Factorization

The solution to the problem above relied on the fact that any positive integer can be written as the product of two factors, sometimes in multiple ways.

A prime number is a positive integer that has no factors other than 1 and itself. Any other positive integer is a composite number and can be written as a product of factors other than 1 and itself. The first few primes are 1, 2, 3, 5, 7, 11, 13, 17, etc.

There are infinitely many primes. If you want to prove this, assume that there are only $n$ primes, and label them so that $p_1 < p_2 < ... < p_n$. Consider the number $x = p_1 p_2 p_3 ... p_n + 1$. If you try to figure out which primes are factors of this number (by the assumption, there must be at least one, since $x$ is greater than all the primes and thus must be composite), you will run into a contradiction quickly, which proves that there actually must be infinitely many primes.

This isn't news- the proof outlined above is allegedly a modification of a proof by Euclid.

Ok, back to business. We were talking about the locker problem and factoring. Now, as I mentioned above, there are many ways to factor an integer (unless it's prime, in which case there's only one way)- for example, $12 = 1 \times 12 = 2 \times 6 = 3 \times 4 = 1 \times 2 \times 2 \times 3$, etc. However, once we break it down to powers of primes, there is only one way to do it, called a prime factorization. $12 = 2^2 \times 3$. If you look at the factorizations above, they are actually all just re-arrangements of $2^2 \times 3$, the prime factorization of 12.

Ahh...it's all coming back now, isn't it? Remember these?


This discussion is bringing us to the Fundamental Theorem of Arithmetic. I'm going to show the proof below and then leave you a little food for thought about how this relates to the number of visitors at our lockers above.

Before going to that, there is a notation that will be useful, and that's the product sign $\Pi$, which looks like the entrance to a temple but is actually an upper-case Greek letter Pi. This works in the same way as the sum symbol $\Sigma$, where we write below and/or above the index over which we'll be multiplying, and then we write the factors to the right. For example, $\prod_{i=1}^{7}{2i^2}$ has an index $i$ running from 1 to7, and for each one, we throw $2i^2$ into the product. So $\prod_{i=1}^{7}{2i^2} = (2 \times 1^2) \times (2 \times 2^2) \times ... \times (2 \times 7^2)$, whatever that ends up being.

Like sums, we can also write infinite products such as: $$\prod_{i=1}^{\infty}{{p_i} ^ {x_i}}$$ If we say each of the $p_i$'s above is a prime (remember, there are infinitely many), and each of the exponents $x_i$ is a positive integer or zero, with only finitely many being non-zero, then the product above is a representation of some number in the form of a prime factorization. For the ones with an exponent of zero, that prime simply doesn't show up in the prime factorization since ${p_i} ^ 0 = 1$.

Theorem (Fundamental Theorem of Arithmetic): Every positive integer greater than 1 can be factored into a product of powers of primes. Furthermore, this prime factorization is unique (i.e. there is only one way to do it).

Proof: We have to prove that such a prime factorization exists, and then that it is unique. Luckily, it's already been done on Wikipedia, so I'll regurgitate their proof below.

Existence: This part can be proved by induction. The base case is $n=2$, which is obvious because $2 = 2^1$. This is a product (consisting of one factor, $2^1$) of powers of primes. Assume that for some $n$, each integer $j$ with $1<j<n$ has a prime factorization. Either $n$ is prime, or it is composite. If $n$ is prime, we know it can only be written as $n \times 1$, so that is the prime factorization. Otherwise, $n$ is composite, which means that there exist two integers $a$ and $b$ such that $1<a,b<n$ and $ab = n$.

Then $a$ and $b$ are examples of $j$'s from the induction hypothesis, so they can each be written as products of powers of primes, $a = \prod_{i=1}^{m}{{p_i}}$, and $b = \prod_{i=1}^{k}{{q_i}}$, where the $p_i$'s and $q_i$'s are primes. But then $n = ab = (\prod_{i=1}^{m}{{p_i}})(\prod_{i=1}^{k}{{q_i}}) = p_1 ... p_m q_1 ... q_k$, which shows that $n$ can be written as a product of powers of primes.

Uniqueness: There is a more intuitive way to do this that uses Euclid's Lemma, but I'll show the way that doesn't assume this lemma.

We know now that every positive integer greater than 1 has at least one prime factorization. Let $s$ be the smallest positive integer greater than 1 which does not have a unique prime factorization. We're going to show that $s$'s very existence leads to a contradiction and thus that prime factorizations are unique.

$s$ cannot be prime, because primes only have the unique factorization into the product of 1 with themselves, so $s$ is composite and the prime factorizations $s = \prod_{i=1}^{m}{{p_i}}$ and $s = \prod_{i=1}^{k}{{q_i}}$ must each have at least 2 prime factors. Note that here, the $p_i$'s and $q_i$'s are any primes, and some of the $p_i$'s could equal each other, as could the $q_i$'s.

However, none of the $p_i$'s can equal any of the $q_j$'s. If they did, then we'd have a number $\dfrac{s}{p_i} = \dfrac{s}{q_j}$ which is smaller than $s$ but has two different prime factorizations, $p_1...p_{i-1}p_{i+1}...p_m$ and $q_1 ... q_{j-1}q_{j+1}...q_k$. This contradicts the assumption that $s$ was the smallest such integer. So none of the $p_i$'s equal any of the $q_j$'s.

Assume without loss of generality that $p_1 < q_1$. It is indeed without loss of generality, because if it's not the case, then we can switch the $p$ and $q$ labels. Consider the number $t = (q_1 - p_1)q_2...q_k$. This number must be greater than $q_2$ since it's the product of $q_2$ and bunch of other numbers greater than 1, and it must also be less than $s$ since it has the same factors (from the product with the $q$'s) except with the first one reduced from $q_1$ to $q_1 - p_1$.

We can do some algebra to get $$
\begin{align}
t &= (q_1 - p_1) (q_2 ... q_k) \\[2mm]
&= q_1(q_2...q_k) - p_1(q_2...q_k) \\[2mm]
&= s -  p_1(q_2...q_k) \\[2mm]
&= p_1(p_2...p_m) - p_1(q_2...q_k) \\[2mm]
&= p_1((p_2...p_m) - (q_2...q_k)) \\[2mm]
&= p_1u
\end{align}$$ where $u=(p_2...p_m) - (q_2...q_k)$. Since $p_1>0$ and $t>0$, it must also be the case that $u>0$. Since $t<s$, $t$ has a unique prime factorization, and we just showed that $p_1$ must appear in said factorization.

$q_1-p_1>0$, but $q_1-p_1 \neq 1$, because if it did, then we'd have $t = (q_1-p_1)q_2...q_k = q_2...q_k$. But $p_1$ appears in $t$'s unique prime factorization, and none of the $q$'s equal any of the $p$'s, so $q_1-p_1 \geq 2$, which means $q_1-p_1$ has a prime factorization, $q_1 - p_1 = r_1...r_d$, and thus $t = r_1...r_d q_2...q_k$.

Since $p_1$ appears in $t$'s prime factorization and isn't any of the $q$'s, it must be one of the $r$'s, and so $p_1$ is a factor of $q_1-p_1$. In other words, $\exists \ \alpha \in \{1, 2, 3, 4, ... \}$ such that $\alpha p_1 = q_1 - p_1$, which can be rearranged to $p_1 (\alpha + 1) = q_1$. This shows that $q_1$ has a factorization other than just $1 \times q_1$ and thus is not prime.

That's a contradiction, so this whole thing is nonsense: $s$ could not have had 2 different prime factorizations in the first place. This completes the proof.

$\square$

To tie this back to visitors at our numbered lockers, see if you can use the theorem above to prove the following fact about the perfect squares:

In the unique prime factorization of a perfect square, the exponent of each prime is even.

Can you see how that relates to whether the number has an even or odd number of factors (and thus number of visitors at locker $n$)?

Thanks for reading. Post any questions in the comments section.