Category: Math Posts

NP Fun

Olly / / Math Posts

Today I read about P and NP. I started with the informal discussion of the topic in Math Games with Bad Drawings by Ben Orlin, which I got for my birthday last week. Then I read the somewhat more technical overview in Introduction to Algorithms by Thomas H. Cormen et al., a beautiful, big book that I’ve been lugging around since college. Then I looked at some of the discussion of the topic in The Princeton Companion to Mathematics (an even bigger, more beautiful book). It was good to refresh my memory on this fundamental of computer science, which was my college minor.

For those unaware, P and NP are classes of problems, divided based on how difficult they appear to be to solve. Problems in P can be thought of as those that will take a computer a reasonable length of time to solve. Problems in NP are those that, using any known algorithm, will take a computer an unreasonable length of time to solve. The relationship between P and NP is an unsolved problem in mathematics. (Are they actually different?) Something I thought was interesting, though, was Ben Orlin’s comment that humans seem to be very attracted to problems in NP. Many of our games and puzzles fall into that class.

Oops

Olly / / Math Posts

Well, it turns out that 253 is not prime. Rather, 253=11(23). It also turns out that the proposition I wanted to use to show that 253 is prime is not true. Oops.

(I worked out the latter myself and then looked up the former.)

Today I’ve been reading more about primality tests, which is a complex topic. I found this page, which seems to give a fairly clear account of two of them. I’m going to have to review quite a few ideas in number theory to understand it, though.

The Renewal Equation Renewed

Olly / / Math Posts

Hello, faithful readers (and anyone else out there). I took a much longer break than I intended, but I am finally ready to start blogging again. There has been a problem with my medication for the past three weeks, but it is now corrected and I am feeling better.

Today I worked on some AMC exam problems. The one I found most interesting was:

What is the least value of $n$ such that $n!$ is a multiple of $2024$?

I am pretty sure I know the answer to this, as well as how to answer the analogous question for any natural number. I ended up pursuing a tangent, however, to do with how I would show that 253, one of the prime factors of 2024, is indeed prime. I expect to post more about that in the coming week. Stay tuned.

(Note on 22 November: It turns out 253 is not prime. Oops.)

Collections of Things

Olly / / Math Posts

Today I listened to more of A Brief History of Mathematics. Most of what I heard was about Cantor. For non-enthusiasts, Cantor is famous for discovering that there are multiple sizes of infinity. The set of natural numbers (i.e. 1, 2, 3, 4, and so on) is infinite, and so is the set of real numbers (i.e. 1, $-\frac{1}{3}$, 2.5837, $\pi$, and all the other numbers on a number line). Cantor discovered, however, that the cardinality of the set of natural numbers—how many things are in it, essentially—is less than the cardinality of the set of real numbers. The infinity of natural numbers is a smaller infinity than the infinity of real numbers.

Not only that, but Cantor discovered that there are infinitely many sizes of infinity, called infinite cardinals. Listening to that idea being discussed, I was struck by a question I’d never thought of before, which was “what size of infinity describes the infinitude of sizes of infinity?” or, more intelligibly, “what is the cardinality of the set of all infinite cardinals?”

I don’t have an exciting answer to share with you, unfortunately. Basically, the answer is that the question is not intelligible. I was able to find a thread on Mathematics Stack Exchange about the topic, and the answers given there explained that there is no set of all infinite cardinals, because the collection of infinite cardinals is in fact a class. Unlike sets, classes do not have cardinality, so there is no answer even to an adjusted form of the question. I was and still am a bit confused about what a class is, but another thread on Mathematics Stack Exchange suggests that it’s any collection of things that can be described but can’t be a set for logical reasons founded in the set theory axioms.

(I also spent a bit of time today reading about categories, which are another mathematical collection of things. They were something I’d heard of but never actually encountered, and my other researches brought them to mind.)

Baby Steps

Olly / / Math Posts

Today I relistened to more of A Brief History of Mathematics. That might seem like it hardly qualifies as study, but I think it is helping revive my desire to continue this project. It comprises mathematical bedtime stories, told by an enthusiast, with a very light sprinkling of actual mathematical ideas—just enough to be tantalizing without being overwhelming.

I also thought a bit about one of those ideas, a theorem in number theory discovered by Gauss: that every natural number is the sum of three triangular numbers. I didn’t put my full focus into it, though, and I didn’t come up with any insights.

[Later note: The theorem only holds as stated if we let 0 be a triangular number. Definitions appear to differ on that point.]

Happy Day

Olly / / Math Posts

Today I had fun working on a geometric proposition about trapezoids and reading some mathematical correspondence. I may do more math activities later, as well.

The proposition I worked on, which comes from Elementary College Geometry, is that the base angles of an isosceles trapezoid are equal. (That book defines a trapezoid as a quadrilateral with exactly two parallel sides. An isosceles trapezoid is a trapezoid that has legs of equal length. The legs are the non-parallel opposite sides.)

I drew a number of pictures trying to find a good way to prove this proposition.

Trapezoid One Small

The first one shows the approach I came up with when I first looked at the problem some time ago: construct isosceles triangles on either end of the trapezoid, show those are congruent (likely requiring some lemmas), use alternate interior angles. I think this will probably work, but it will need some details ironed out. For instance, what if $\angle ABC$ is acute? (It can’t actually be with Elementary College Geometry’s definition of a trapezoid and $AD$ equal to $BC$, but I may need to prove that.)

This method is not very elegant, even ignoring the niggly details, so before working those out, I decided to see if I could find something better. In the process, I came up with the figures below. None of these approaches has born fruit so far, though.

Trapezoid Two Small

Trapezoid Three Small

Trapezoid Four Small

In the first drawing, I tried the most basic quadrilateral proof move, but just went around in circles. The second drawing didn’t really go anywhere at all. Something resembling the third drawing will be useful for proving the converse of the proposition, I think, but didn’t yield a proof in this direction.

I’m feeling much encouraged and less inclined to simply drop this project, which I had been resisting the urge to do.

Squares Yet Again

Olly / / Math Posts

Today I watched this fun video from Numberphile. I watched it earlier in the month—it’s the one I stopped so I could investigate its topic a bit myself—but I had since forgotten the details. I’d recommend it to all of my readers. It is very accessible but has connections to more advanced topics. When I am feeling better, I would like to work on proving the theorem presented at the end of the video.

Back to School

Olly / / Math Posts, Updates

Well, I’m back. I ended up taking a somewhat longer break than planned. I was just too discouraged to study last Thursday, and yesterday I was still getting settled again after being at camp. Today I watched YouTube videos in an attempt to ease into my project again. One was about the recent discovery of a new formula for approximating $\pi$. (It is not superior to existing formulae, just new.) The other was a fun video about some properties of prime numbers. It should be accessible to most people, and I have embedded it below.

Circles and a Line Again

Olly / / Math Posts

Today I read the section of my calculus textbook about continuity, looked up a couple of related proofs in Analysis with an Introduction to Proof, and experimented with a variation on the problem I shared yesterday.

2circles1line Small
Source: Single Variable Calculus by James Stewart

In a comment on yesterday’s post, reader Tim McL asked what would happen if circle $C_2$ in the diagram above were fixed and the radius of $C_1$ were allowed to increase toward infinity. (See this interactive model on Desmos.) How would this affect $R$? And if it caused the $x$-coordinate of $R$ to grow without bound, as seemed likely, why would our intuition be correct in this scenario but not in the one described in the original problem?

I’m not sure I’ve answered the second of those questions, but I did establish that in the scenario Tim McL described, $R=(\sqrt{4t^2-r^2}+2t,0)$, where $t$ is the radius of $C_1$ and $r$ is the (fixed) radius of $C_2$. Notice that the $x$-coordinate does become arbitrarily large as $t$ increases. Notice also, though, that it becomes closer and closer to $4t$. In the original problem, $R$ approached $(4,0)$ and $t$ was equal to $1$. Thus, I think we are seeing the same behavior in both scenarios, with the $x$-coordinate of $R$ dependent on the radii of both circles, and approaching $4t$ as they diverge. It only grows without bound when one of them increases toward infinity, however.

Two Circles and a Line

Olly / / Math Posts

Today I finished the textbook exercises from the section on limit laws. There were a few interesting ones among the higher numbers. I may discuss more of them in coming days, but today I want to give a sketch of the last problem in the section:

“The figure shows a fixed circle $C_1$ with equation $(x-1)^2+y^2=1$ and a shrinking circle $C_2$ with radius $r$ and center the origin. $P$ is the point $(0,r)$, $Q$ is the upper point of intersection of the two circles, and $R$ is the point of intersection of the line $PQ$ with the $x$-axis. What happens to $R$ as $C_2$ shrinks, that is, as $r\rightarrow 0^+$?”

2circles1line Small
Source: Single Variable Calculus by James Stewart

What do you think? Make a guess.

It turns out the answer is that it approaches the point $(4,0)$. This is not at all in line with my intuition that, since at the limit point $P$ and $Q$ have the same $y$-coordinate, the $x$-coordinate of $R$ would grow without bound as $\overline{PQ}$ approached horizontal.

You can see the actual path of $R$ in this manipulable model of the problem that I made in Desmos after I found the solution. I did that by crunching the algebra arising from the equations of the circles and line in the diagram. I’m not going to give a full account of that here, but the basic procedure was a follows:

  1. Find the coordinates of the intersections of the two circles.
    $(\frac{r^2}{2}, \pm\frac{r}{2}\sqrt{4-r^2})$
  2. The one with a positive $y$-coordinate is $Q$.
  3. Use the coordinates of $P$ and $Q$ to find the slope of $\overline{PQ}$.
    $\frac{\sqrt{4-r^2}-2}{r}$
  4. Plug this and $y$-coordinate of $P$ into the slope-intercept form of a line.
    $y=\frac{\sqrt{4-r^2}-2}{r}x+r$
  5. Find the $x$-intercept of this line.
    $(\sqrt{4-r^2}+2,0)$
  6. This is $R$. Find it’s value as $r\rightarrow 0^+$.

It turns out that there is also a trigonometric solution, which you can read about in this thread on Math Stack Exchange. I stumbled on this when I did a Google search for the problem, hoping to check my (to me) surprising answer.

I also did a lot of thinking today about my review project and its ultimate goal of allowing me to do some online tutoring. I may say more about that in the coming days, as well.