Category: Just For Fun

  • Driving with Cats

    I’ve surprised myself this week with many skills that I didn’t know that I (still) had. Students have left campus (some are weathering it out there), and I’m social distancing at home with my family. I’ve quickly set up home offices, even taped ethernet cable between floors to strengthen our bandwidth, and offered advice on email like the following.

    Hi ——,
    I saw that you’re leaving campus. Good luck! Georgia is a long haul, but the drive could be enjoyable.
    I’ve driven with cats, and here are my tips:
    Keep the cat in a travel carrier, don’t let it roam around the car while you’re driving!
    Line the carrier with a bath towel, in case it has to pee. If that happens, stop as soon as you can and clean things up, because cats like their space clean, and will start kicking around the towel.
    Stop so that the cat can have a pee break now and then. 
    Use a leash whenever the cat is out of the car! Cats startle, run, and hide. It will be difficult to get them back into the car if that happens.
    Start early, and don’t drive if you feel drowsy. Pull over and take a cat nap! Schedule in walk breaks.
    When I drive long distances, the first 100 miles is usually the hardest, and then I get acclimated to the long hauls. 
    It’s better to stop and stay in a motel overnight than to keep driving when it’s dark and you’re drowsy. You’ll have a short easy distance to complete in the morning when you’re refreshed. 
    Wash your hands and don’t touch your face, of course! But driving is a form of social isolation, so just keep hygienic when you stop.
    Good luck! Please get back in touch when things are less crazy.
    Japheth

  • 1988 IMO Problem 6

    I found about this legendary problem from a Numberphile video and was intrigued. Go watch the video, even if you have seen the problem before. It’s fun!

    Here’s the problem which is can be found on The Official IMO page.


    1988 IMO #6. Let $a$ and $b$ be positive integers such that $ab + 1$ divides $a^2 + b^2$.
    Show that $\dfrac{a^{2} + b^{2}}{ab + 1}$ is the square of an integer.


    I thought about the problem for some time and initially thought it was about Gaussian primes. But I got nowhere, so I wrote a simple Python program to collect some data. Denoting the ratio $\dfrac{a^{2} + b^{2}}{ab + 1}$ by $q$, here’s what I found (notice that I considered non-negative integers, rather than just strictly positive integers).:

    $$\begin{array}{c||cccccccccc}
    a & 1 & 1 & 2 & 3 & 8 & 27 & 30 & 112 & 240 & 418 \\ \hline
    b & 0 & 1 & 0 & 0 & 2 & 3 & 8 & 30 & 27 & 112 \\ \hline
    q & 1 & 1 & 4 & 9 & 4 & 9 & 4 & 4 & 9 & 4 \\
    \end{array}$$

    More thoughts…
    What struck me about this data were the solutions for $q = 4$. They are adjacent terms in the sequence
    $$0, 2, 8, 30, 112, 418, \dots$$
    After some thought, I realized that this sequence satisfies the recurrence $T_n = 4 T_{n-1} – T_{n-2}$.

    And the solutions for $q = 9$ are adjacent terms in the sequence $$0, 3, 27, 240, \dots$$
    This sequence satisfies the recurrence $T_n = 9 T_{n-1} – T_{n-2}$.

    Could it be, that for a fixed value of $q$, the integer solutions are adjacent terms of a 2nd order linear recurrence $T_n = q T_{n-1} – T_{n-2}$?!?

    Given one solution $(a,b)$ with $a > b$, the recurrence yields the next solution, which is $(q a – b, a)$.

    But the recurrence also determines the previous terms of the sequence: $T_{n-2} = q T_{n-1} – T_n$.

    So the solution before $(a, b)$ would be $(b, q b – a)$. And if we keep generating smaller solutions, the process would have to bottom out somewhere, namely at $(T_1, T_0) = (r, 0)$ for some $r$.

    Computing the ratio $q$ for this smallest solution yields that $q = r^2$, a perfect square, just as claimed in the problem!


    With that intuition, here is what I proved:

    Suppose that $a > b > 0$ are integers, and $\dfrac{a^2+b^2}{ab+1} = q$ is an integer. Define $a’ = b$ and $b’ = qb – a$. Then

    1. The ratio $\dfrac{a’^2+b’^2}{a’b’+1}$ is also equal to $q$.

    2. $q \geq 1$.

    3. $a’ > b’$.

    4. $b’ \geq 0$.

    Thus, given a solution $(a,b)$, we can derive a smaller solution $(a’,b’)$. So the motivation described above is valid; any solution can be stepped down to a minimal solution $(r,0)$ whose $q$-value is the same as for $(a,b)$, and is $q = r^2$.


    Proofs:

    1. The ratio $\dfrac{a’^2+b’^2}{a’b’+1}$ is also equal to $q$.

    Proof: Start by substitution and then use that $(a^2 + b^2) = q(ab+1)$.
    $$\dfrac{a’^2+b’^2}{a’b’+1} = \dfrac{b^2+(qb – a)^2}{b(qb – a)+1} = \dfrac{q^2b^2 – 2qab + (a^2 + b^2)}{qb^2 – ab + 1} = \dfrac{q^2b^2 – 2qab + q(ab+1)}{qb^2 – ab + 1} = \dfrac{q^2b^2 – qab + q}{qb^2 – ab + 1} = q$$

    2. $q \geq 1$. Proof: This is because $q$ is a positive integer!

    3. $a’ > b’$. Proof: Start with $q = \dfrac{a^2+b^2}{ab+1}$ and decrease the denominator to get
    $q < \dfrac{a^2+b^2}{ab} = \dfrac{a}{b} + \dfrac{b}{a} < \dfrac{a}{b} + 1$. Then note that $q < \dfrac{a}{b} + 1$ is equivalent to $b > bq – a$ which is just $a’ > b’$.

    4. $b’ \geq 0$.
    Proof: In part 1 we saw that $\dfrac{b^2+(qb – a)^2}{b(qb – a)+1} = q$. We know that the numerator and the right hand side are positive. So the denominator must also be positive, which means that $b’ = qb-a \geq 0$.

  • Uniqueness of Factorization

    A few days ago I came across a proof of the Fundamental Theorem of Arithmetic (aka Unique Factorization) in Courant and Robbin’s What is Mathematics that I hadn’t seen it before. I liked it enough to learn it.

    Then another surprise – I saw it again yesterday in Primes and Programming by Peter Giblin, a book that Larry Zimmerman had recommended to a student from the summer high school program.

    The usual proof that I know is based on Euclid, and basically is a proof by Strong Induction. This new proof is by the Principle of Least Element. So the key is to suppose that unique factorization fails, and to reason about the least positive integer \(N\) that has more than one factorization into primes. Even though we’ll show this number doesn’t exist, we can deduce lots of information about it!

    First, some notation. Let’s say that two distinct prime factorizations of \(N\) are

    \[\text{(1)}\qquad N = p_1 p_2 \dots p_r \text{ and } N = q_1 q_2 \dots q_s\]

    Of course, we’ll arrange the primes in non-decreasing order, so that in particular, \(p_1\) and \(q_1\) are the smallest primes in those factorizations.

    The other primes don’t take a big role in what comes next, so let’s write \(P = p_2 \dots p_r\) and \(Q = q_2 \dots q_s\), so that we have

    \[N = p_1 P = q_1 Q.\]

    The first observation is that \(p_1\) and \(q_1\) are different primes, otherwise if they were equal, we could factor them off and then \(N/p_1 = P\) would be a smaller positive integer with two distinct prime factorizations.

    Now that that’s done, let’s assume without loss of generality that \(p_1 < q_1\), and we’ll form a new number:

    \[\text{(2)}\qquad M = (q_1 – p_1) Q\]

    By equation (2), it’s clear that \(M\) is a positive integer that is less than \(N\), and therefore does factor uniquely into primes. Now we rewrite \(M\) as follows:

    \[M = (q_1 – p_1) Q = q_1 Q – p_1 Q = N – p_1 Q = p_1 P – p_1 Q = p_1 (P – Q)\]

    That is, \[\text{(3)}\qquad M = p_1 (P – Q)\]

    We’re almost there. Note that because of equation (3), the prime \(p_1\) is a prime factor of \(M\). Now consider the factorization of \(M\) given in equation (2). Since we were careful to list the primes in non-decreasing order, \(p_1\) can’t be any of the primes in \(Q = q_2 \dots q_s\), and so it must be a factor of \((q_1 – p_1)\). Suppose that \((q_1 – p_1) = p_1 t\). Then solving for \(q_1\), we find that \(q_1 = p_1 (t+1)\). And this is a contradiction, since then \(q_1\) would not be a prime number!

  • Typesetting synthetic division

    I’m teaching an Algebra course that highlights the Fundamental Theorem of Algebra. So of course we’re looking closely at polynomial division, and in particular at synthetic division. My students are preparing their homework assignments using LaTeX, so this begs the question about how to typeset their computations.

    One of my students found the LaTeX package polynom, which can automatically compute and typeset polynomial long division and synthetic division. The examples in the polynom manual are:

    \polylongdiv{X^3+X^2-1}{X-1}

    which yields

    Screen Shot 2014-09-07 at 2.57.19 PM

     

     

     

     

     

    and for synthetic division, the polynom command

    \polyhornerscheme[x=1]{x^3+x^2-1}

    which yields

    Screen Shot 2014-09-07 at 2.57.28 PM

     

     

     

    But what if you want to show division by x - m using synthetic division, rather than x - 1? These commands no longer work.

    Instead, you can make fancy use of \cline and \multicolumn in the array environment:

    \begin{array}{r|rrrr}
    & 1 & 1 & 0 & -1 \\
    m & & m & (m^2 + m) & (m^3 + m^2) \\ \cline{2-5}
    \multicolumn{2}{r}{1} & (m + 1) & (m^2 + m) & (m^3 + m^2 - 1)
    \end{array}

    which yields

    Screen Shot 2014-09-07 at 3.02.21 PM

     

     

     

    Interesting! If you divide a polynomial by x - m, the remainder is just the value of that polynomial at m!

  • A brief 4,000 year history of Diophantine Equations

    I filled in for a NY Math Circle class over the weekend. Since the topic was Primitive Pythagorean Triples, I had a blast. I also shared the following outline with the students. Each item is full of wonderful mathematics and anecdotes!

    Plimpton 322, a Babylonian cuneiform tablet @ Columbia University. From 1900BCE – 1600BCE, and allegedly includes the Pythagorean triple (12709, 13500, 18541).

    Pythagoras was born ca 580BCE on the island of Samos. Famous quote: “All is Number”. His proof of the theorem that bears his name involved cutting up a square of side a+b and rearranging the pieces.

    Proclus (5th century CE) credits Pythagoras with the formula (2n+1, 2n^2 + 2n, 2n^2 + 2n + 1) of (necessarily) primitive pythagorean triples where the hypotenuse is 1 more than one of the sides. Proclus also credits Plato with the formula (2n, n^2 – 1, n^2 + 1) where the hypotenuse is 2 more than one of the sides. (For what n is this primitive?)

    Euclid of Alexandria (born 365 BCE) is famous for the 13-book Elements. The Theorem of Pythagoras is Book I, Proposition 47. Analysis on Primitive Pythagorean Triples appears as Lemma 1 “To find two square numbers such that their sum is also a square” in Book X, just before Proposition 29.

    By the way, Elisha Scott Loomis, an early 20th century mathematician, published The Pythagorean Proposition, which has 370 proofs of the theorem, and not a single one used trigonometry. This was republished in 1968 by the NCTM.

    Diophantus of Alexandria (200CE – 298CE) is famous for his book Arithmetica. He sought integer (and perhaps rational too?) solutions to algebraic equations. The term Diophantine Equation typically refers to equations where we seek positive integer solutions.

    Fermat (1608CE – 1665CE) wrote in the margin of his copy of Arithmetica that there are no integral values of x, y, z so that x^n + y^n = z^n if n > 2.

    Andrew Wiles of Princeton University announced a proof in 1993 of Fermat’s Last Theorem, after working in secret for 7 years. An error was found in his proof, which was salvaged in 1994. Wiles’ proof was published in 1995.

    Jumping back to 1900, David Hilbert asked mathematicians at the International Congress of Mathematicians to devise a method to determine whether a Diophantine equation has solutions. This is known as Hilbert’s 10th Problem.

    Julia Robinson (1919-1985) was a Californian mathematician who worked on Hilbert’s 10th problem for decades, from the 1940s until final achieving a solution (in joint work with Martin Davis, Hilary Putnam, Yuri Matiyasevich and others) in 1970. In general, there is no such algorithm!

    Mirroring the Hilbert Problems of 1900, the Clay Institute of Mathematics issued the Millennium Problems in 2000.

  • Math Formula Poetry Slam

    Last December, I got to meet Daniel, aka Jarabe Del Sól, a poet from the Readnex Poetry Squad. He showed me in his notebook where he had written all sorts of arcane symbols and characters, perhaps from undiscovered alphabets. I got to fill up a few pages of his notebook with math symbolism off the top of my head, and then he proceeded to respond with a poetic response and free verse. This was a lot of fun, and a few days later, he sent me photos of what I had written. If you click on the photos below, you can see what Jarabe and I wrote, a math formula poetry slam! Play this track while you’re looking, for the full experience.

    11 If gravity could fly one 64

  • Singing and Dancing Mathematics

    Long Division Style

    Recently, a Gangnam Style-inspired video came out of I.S. 285 Meyer Levin in Brooklyn. In this video, students sing and dance the procedure for long division. It’s absolutely delightful.

    The Quadratic Formula Song

    Music versions of math formulas and procedures are not new. One that came up recently in the Algebra class I teach for in-service teachers is the Quadratic Formula, set to the tune Pop Goes the Weasel.

    x equals negative b
    plus or minus the square root
    of b squared minus 4ac
    all over 2a

    Please sing this to your students!

    Solving the Cubic in a Poem

    Did you know that there is something similar for the Cubic Formula? Tartaglia was one of the first mathematicians to solve (a specific form of) the cubic. His solution was secret, but he did communicate his solution to Cardano in a poem, but swore Cardano to secrecy.

    Here’s the poem, in translation (from the MAA Digital Library, a fantastic resource).

    Tartaglia’s Poem

    Tartaglia divulged to Hieronimo Cardano (1501-1576) the solution of the three cubic equations without the quadratic term on March 25, 1539 in Cardano’s house in Milano in the form of a famous poem (translated here by the author):

    01) When the cube with the cose beside it
    02) Equates itself to some other whole number, <=q>
    03) Find two other, of which it is the difference.
    04) Hereafter you will consider this customarily
    05) That their product always will be equal
    06) To the third of the cube of the cose net. 3/3, instead of (p/3)3>
    07) Its general remainder then
    08) Of their cube sides , well subtracted,
    09) Will be the value of your principal unknown. <=x>
    10) In the second of these acts,
    11) When the cube remains solo ,
    12) You will observe these other arrangements:
    13) Of the number you will quickly make two such parts,
    14) That the one times the other will produce straightforward
    15) The third of the cube of the cose in a multitude, 16) Of which then, per common precept,
    17) You will take the cube sides joined together. 
    19) The third then of these our calculations
    20) Solves itself with the second, if you look well after,
    21) That by nature they are quasi conjoined.
    22) I found these, & not with slow steps,
    23) In thousand five hundred, four and thirty
    24) With very firm and strong foundations
    25) In the city girded around by the sea.

  • Math Conference photos

    Going through some old papers, I found the following conference photos from

    • Fall 1996 Fields Institute, Algebraic Model Theory Program
    • July 1-10, 1998, XI Simposio Latinoamericano Lógica Matemática, Mérida, Venezuela
    • 1998 Szeged Conference on Lattices and Universal Algebra

    1996 Fields Institute
    The Fall 1996 Algebraic Model Theory Program at the Fields Institute
    Photo key

    XI Simposio Latinoamericano Lógica Matemática

    1998 Szeged Conference on Lattices and Universal Algebra

  • An Interesting Prime Number Fact, Rubik’s Cube and the Gömböc

    In the summer of 2010 I traveled to Hungary for the 25th anniversary reunion of the Budapest Semesters in Mathematics program, and had the pleasure of seeing the inauguration of another study abroad program for computer science, the Aquincum Institute of Technology.

    The interesting part of the ceremony was a series of mathematics talks to celebrate the genius of Hungarian mathematics and technology. There were also talks by Balázs Bús, the mayor of Óbuda, and by János Kocsány, the CEO of Graphisoft Park.

    The Graphisoft Park Rubik's Cube
    The Graphisoft Park Rubik's Cube

    László Babai talked about Mathematical Generalizations of Rubik’s Cube, and mentioned the following.

    The diameter of the Rubik’s Cube graph is at least 20, but probably no more than 21 (Richard Korf, UCLA, 1997), and definitely no more than 26 (Gene Cooperman, Dan Kunkle, Northeastern, 2007).

    It was very interesting that just a month later, in July, 2010, the diameter was confirmed as 20. A team used 35 years of CPU time, donated by Google, to complete the computation. Even more interesting for me was to learn that the lower bound of 20 had been established in 1995 by Mike Reid, who identified the “superflip” position that required 20 moves to solve. Here’s an interesting website that documents progress on this problem: God’s Number is 20.

    I had met Mike in person about 25 years ago, when I attended the Hampshire College Summer Studies in Mathematics. Now that I am involved with the New York Math Circle, I’ve had the pleasure of meeting Mike’s old math teachers, who have wonderful stories to tell.

    Babai had brought up the diameter of the Rubik’s Cube graph because his talk was really about the connection between the size of a group at the diameter of its Cayley graph. For the Rubik’s cube, the group has about 34 quintillion elements (The exact number is 43,252,003,274,489,856,000. Remember: thousand, million, billion, trillion, quadrillion, quintillion, sextillion, septillion, …), but its diameter is just 20, which is on the order of the logarithm of the size of the group.

    Babai mentioned a recent result of Harald Helfgott and Akos Seres, On the diameter of permutation groups, which gives a “quasipolynomial upper bound” for the diameter.

    One beautiful formula that Babai presented was:

    $latex \prod_{p \leq x} p \approx e^x$.

    This seems related to the prime number theorem, that $latex \pi(x) \approx \frac{x}{\ln{x}}$, where $latex \pi(x)$ denotes how many primes are less than x. I leave it to the readers to find the connection.

    Another great talk was by Gábor Domokos, The Story of Gömböc. The gömböc is a solid object with just one stable point of equilibrium (and also one unstable point). If you place the gömböc on a flat surface, it rocks back and forth, and eventually stabilizes in the same position each time.

    Amazing invention–I want one!

  • Project Euler

    My friend Aaron just pointed me to this site, but I think I’d seen it before, in a less-polished state.

    Project Euler (http://projecteuler.net/)

    This page has a sequence of 360 challenging math and computing problems. If you sign up for an account, you can track your progress in solving the problems. The problems are not trivial at all, so this looks like a great way to challenge yourself and grow both mathematically and in terms of programming.

    I’m curious who set up this site. Even more, I think it would be great to work as a team to solve these problems. Add this to my list of fun things to do, if I only had time…