{"id":2871,"date":"2020-07-03T12:23:59","date_gmt":"2020-07-03T17:23:59","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2871"},"modified":"2020-07-03T16:46:53","modified_gmt":"2020-07-03T21:46:53","slug":"squaring-the-pentagon","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/squaring-the-pentagon\/","title":{"rendered":"Squaring the pentagon"},"content":{"rendered":"

This week’s Riddler Classic<\/a> is a number theory problem, which I will paraphrase:<\/p>\n

\nThe number 50 can be represented using a set of interleaved dots where the number of columns is one greater than the number of rows; the same way the stars in the US flag are arranged. If we add 1 to this number, we obtain 51, which can be represented using concentric pentagons. Here are diagrams showing both arrangements:<\/p>\n

\n
\n\"\"\n<\/div>\n
\n\"\"\n<\/div>\n<\/div>\n

What is the next number with the property that it can be represented as interleaved dots but when you add 1 to it it can be represented using concentric pentagons?\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

The arrangement on the left consists of an $(m+1) \\times m$ grid on the outside, with an $m\\times (m-1)$ grid on the inside, for a total of $m(m+1)+m(m-1)=2m^2$ points. In the case of the US flag, $m=5$ and we have 50 total points. If a number can be written as $2m^2$, I’ll call it a flag number.<\/p>\n

The numbers represented on the right are called centered pentagonal numbers<\/a>. We have 1 point in the center, 5 in the next layer, 10 in the next layer, 15 in the next layer, and so on. This means the centered pentagonal numbers have the form $\\frac{5n^2+5n+2}{2}$. In our case shown above, $n=4$ and the formula produces 51, as anticipated.<\/p>\n

To answer the question, we want to find centered pentagonal numbers that are one greater than a flag number. Mathematically, this amounts to finding pairs of positive integers $(n,m)$ such that:
\n\\[
\n\\frac{5n^2+5n+2}{2}-2m^2 = 1
\n\\]Rearranging this equation a little bit, we can write it as:
\n\\[
\n5(2n+1)^2-(4m)^2=5
\n\\]Let’s rename $x=2n+1$, where $x$ is an integer. Due to the parity of the remaining terms, $x$ must always be odd so there is no loss of generality in solving for $x$ rather than $n$. Also, two of the terms are divisible by 5, so the third one must also be divisible by 5 and we conclude $4m=5y$ for some integer $y$. Eliminating $m$ and $n$, we obtain the following equation:<\/p>\n

$\\displaystyle
\nx^2-5y^2=1,\\quad\\text{where: }n=\\frac{x-1}{2}\\text{ and }m=\\frac{5y}{4}
\n$<\/span><\/p>\n

So if we find a particular solution $(x,y)$, we can convert it to $(n,m) = \\left( \\frac{x-1}{2}, \\frac{5y}{4} \\right)$, and then our pair of centered pentagonal and flag numbers that differ by 1 is given by $\\frac{5n^2+5n+2}{2}$ and $2m^2$, respectively. The solution we originally had $(n,m)=(4,5)$ corresponds to the solution $(x,y)=(9,4)$ of the simplified equation above.<\/p>\n

Brute-force approach<\/h3>\n

If we rewrite the equation $x^2-5y^2=1$ as $x^2 = 5y^2+1$. We can then try different values $y=1,2,3,\\dots$ until $5y^2+1$ becomes a perfect square. Not particularly elegant, but it is guaranteed to find us all solutions (eventually). Here are the first few solutions that we obtain:<\/p>\n\n\n\n\n\n\n\n\n
$x$<\/th>\n$y$<\/th>\n$n$<\/th>\n$m$<\/th>\npentagonal number<\/th>\nflag number<\/th>\n<\/tr>\n<\/thead>\n
9<\/td>\n4<\/td>\n4<\/td>\n5<\/td>\n51<\/td>\n50<\/td>\n<\/tr>\n
161<\/td>\n72<\/td>\n80<\/td>\n90<\/td>\n16,201<\/td>\n16,200<\/td>\n<\/tr>\n
2,889<\/td>\n1,292<\/td>\n1,444<\/td>\n1,615<\/td>\n5,216,451<\/td>\n5,216,450<\/td>\n<\/tr>\n
51,841<\/td>\n23,184<\/td>\n25,920<\/td>\n28,980<\/td>\n1,679,680,801<\/td>\n1,679,680,800<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Pell’s equations<\/h3>\n

This is not the end of the story! The equation $x^2-5y^2=1$ is an example of Diophantine equation<\/a>, that is, a polynomial equation for which we seek integer solutions. More specifically, it is an instance of Pell’s equation<\/a>, which comes up often enough that it was given it’s own name! In general, Pell’s equation refers to any Diophantine equation of the form $x^2-dy^2=1$.<\/p>\n

To understand the structure of solutions to Pell’s equation, consider $\\mathbb{Z}[\\sqrt{5}]$, which is the set of numbers of the form $z = a+b\\sqrt{5}$ where $a$ and $b$ are integers. Just like with complex numbers, we can define the conjugate by flipping the sign of the second term, so $\\bar z=a-b\\sqrt{5}$. Notice that if $z=x+y\\sqrt{5}$, we have:
\n\\[
\nz \\bar z = \\left(x+y\\sqrt{5}\\right)\\left(x-y\\sqrt{5}\\right) = x^2-5y^2
\n\\]So $(x,y)$ is a solution to Pell’s equation precisely when the number $z=x+y\\sqrt{5}$ satisfies $z\\bar z = 1$.<\/p>\n

Fact 1:<\/strong> If $z$ is a solution to Pell’s equation, then $z^{-1} = \\bar{z}$ is also a solution. This is a straightforward consequence of the fact that $z$ must satisfy $z\\bar z = 1$.<\/p>\n

Fact 2:<\/strong> If $z_1$ and $z_2$ are both solutions to Pell’s equation, then so is the product $z_1 z_2$. To see why this is the case, we use the fact that conjugation is distributive and multiplication is commutative:
\n\\[
\n(z_1z_2)(\\overline{z_1z_2}) = (z_1 \\overline{z_1}) (z_2 \\overline{z_2}) = 1
\n\\]Now, let’s define the fundamental unit<\/em> $e \\in \\mathbb{Z}[\\sqrt{5}]$ to be the smallest solution to Pell’s equation with $x,y\\gt 0$. In our case, $e = 9+4\\sqrt{5}$, which is the first row in the table we generated above. Based on our observation that products of solutions are again solutions, it should be the case that $e^2$ is a solution. Let’s check!
\n\\begin{align}
\ne^2 &= (9+4\\sqrt{5})^2 \\\\
\n&= 81 + 2\\cdot 9\\cdot 4\\sqrt{5} + 16\\cdot 5 \\\\
\n&= 161 + 90\\sqrt{5}
\n\\end{align}And indeed, $(x,y)=(161,90)$ is also a solution; it’s the second one in our table above! But things get more interesting…<\/p>\n

Fact 3:<\/strong> If a solution to Pell’s equation satisfies $x+y\\sqrt{5}\\gt 1$, then $x,y\\gt 0$. To see why this is the case, use the fact that $(x+y\\sqrt{5})(x-y\\sqrt{5})=1$, from which we conclude that $0\\lt x-y\\sqrt{5}\\lt 1$. We therefore have the inequalities:
\n\\begin{align}
\n1&\\lt x+y\\sqrt{5} \\\\
\n0&\\lt x-y\\sqrt{5} \\lt 1 \\\\
\n-1&\\lt -x+y\\sqrt{5}\\lt 0
\n\\end{align}Adding pairs of these inequalities together to eliminate $x$ or $y$, we conclude that $1\\lt 2x$ and $0\\lt 2\\sqrt{5}y$. Therefore, $x,y\\gt 0$, as required.<\/p>\n

Fact 4:<\/strong> All positive integer solutions to the Pell equation $x^2-5y^2=1$ are given by $e^k$ for $k=\\{1,2,3,\\dots\\}$. We will prove this surprising fact by contradiction. Suppose we are wrong and there is some other solution $z$ that is not of this form. Since $e\\gt 1$, it must be the case that for some $k$, we have $e^k \\lt z \\lt e^{k+1}$. Rearranging, we obtain $1\\lt z e^{-k} \\lt e$. Since $z$ and $e^{-k}$ are both solutions (Fact 1), then $z e^{-k}$ must also be a solution (Fact 2). Moreover $z e^{-k} \\gt 1$ so by Fact 3, this solution must also have $x,y\\gt 0$. However, we also showed that $z e^{-k} \\lt e$, which contradicts the definition of the fundamental unit; $e$ was defined as the smallest solution with $x,y\\gt 0$. This contradiction means that our initial premise must have been false. So all solutions are of the form $e^k$.<\/p>\n

The arguments we used for the case $d=5$ still hold true for any $d$ that is not a perfect square, so for example we could find solutions to $x^2-17y^2=1$ in the exact same way; by looking for fundamental unit and then raising it to any power. In the case where $d = h^2$ is a perfect square, then the equation becomes $x^2-(hy)^2=1$ and it is clear that the only solution is $(x,y) = (\\pm 1, 0)$.<\/p>\n

All solutions<\/h3>\n

Based on our little Pell’s equation detour, we established that all solutions to the equation $x^2-5y^2=1$ are of the form:
\n\\[
\n(9+4\\sqrt{5})^k\\qquad\\text{for: }k=1,2,\\dots
\n\\]We can find explicit formulas for $x$ and $y$ by using the fact that $x = \\tfrac{1}{2}(z+\\bar z)$ and $y = \\tfrac{1}{2}(z-\\bar z)$, which produces:
\n\\[
\n(x,y)\\,=\\,\\left( \\tfrac{(9+4\\sqrt{5})^k+(9-4\\sqrt{5})^k}{2}, \\tfrac{(9+4\\sqrt{5})^k-(9-4\\sqrt{5})^k}{2}\\right)\\qquad\\text{for: }k=1,2,\\dots
\n\\]This might remind you of the formula for generating Fibonacci numbers<\/a>, which is another example of an integer sequence whose general formula involves irrational numbers.<\/p>\n

Just like with the Fibonacci sequence, we can find a recursive formula. Starting with $k=0$ for simplicity, we have $(x_0,y_0)=(1,0)$. Then subsequent terms can be generated using:
\n\\begin{align}
\nx_{k+1}+y_{k+1}\\sqrt{5} &= \\left( x_k+y_k\\sqrt{5} \\right)\\left( 9+4\\sqrt{5} \\right)\\\\
\n&= (9x_k+20y_k) + (4x_k+9y_k)\\sqrt{5}
\n\\end{align}Or in other words, the recursive relationship:
\n\\[
\n\\begin{bmatrix}
\nx_{k+1} \\\\ y_{k+1}
\n\\end{bmatrix}
\n=
\n\\begin{bmatrix}
\n9 & 20 \\\\ 4 & 9
\n\\end{bmatrix}
\n\\begin{bmatrix}
\nx_{k} \\\\ y_{k}
\n\\end{bmatrix}
\n\\qquad\\text{with: }
\n\\begin{bmatrix}
\nx_{0} \\\\ y_{0}
\n\\end{bmatrix}
\n=
\n\\begin{bmatrix}
\n1 \\\\ 0
\n\\end{bmatrix}
\n\\]If you find this stuff interesting, it’s part of a branch of mathematics called algebraic number theory<\/a>.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This week’s Riddler Classic is a number theory problem, which I will paraphrase: The number 50 can be represented using a set of interleaved dots where the number of columns is one greater than the number of rows; the same way the stars in the US flag are arranged. If we add 1 to this … Continue reading “Squaring the pentagon”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[36,2],"class_list":["post-2871","post","type-post","status-publish","format-standard","hentry","category-riddler","tag-number-theory","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2871","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2871"}],"version-history":[{"count":11,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2871\/revisions"}],"predecessor-version":[{"id":2885,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2871\/revisions\/2885"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2871"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2871"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2871"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}