Introduction

You can find an introduction to the legendary “Question Six” in this Numberphile video. This article is my attempt at providing a “simple” answer to the problem, sketched from the hints provided in this more detailed insights video.

To be clear this isn't my personal “best effort” at trying to solve the problem (I did give it a quick try, starting from an intuition that induction would be the key, but I didn't get very far in). I also have no idea if this is how it was solved by any of the candidates that did provide the correct answer to the problem.

No, this is just a formalization into an actual proof of the hints provided by Simon Pampena in the second video. The proof should still be easy to follow even with only a basic knowledge of algebra.

The problem

Let $a$ and $b$ be positive integers such that $ab+1$ divides $a^2+b^2$. Show that

$$\frac{a^2+b^2}{ab+1}$$

is the square of an integer.

The solution

Let

$$f(x,y)=\frac{x^2+y^2}{xy+1}.$$

We want to show that if $a,b$ are positive integers and $f(a,b)$ is an integer, then $f(a,b)$ is a square.

Observe first that if $a,b$ are non-negative integers, and one of them is 0, then the statement is trivially true, since $f(a,0)=a^2$ and $f(0,b)=b^2$.

Assume now that $a_0,b$ integers with $0<a_0<b$ are such that $f(a_0,b)$ is an integer. We want to show that there exist a non-negative integer $a_1<a_0$ such that $f(a_1,a_0)=f(a_0,b)$. Note that with this proven, we can apply the result iteratively, constructing a sequence $\left\{a_i\right\}$ with $0\le a_{i+1}<a_i$ and such that $f(a_{i+i},a_i)=f(a_0,b)$. Given the strictly decreasing nature of the sequence and the non-negativity of the values, the sequence will terminate in $k<a_0$ steps, with $a_k=0$, leading to $f(a_0,b)=f(0,a_{k-1})=a_{k-1}^2$, proving that $f(a_0,b)$ is the square of an integer.

Let us then prove the existence of $a_1$. Let $N=f(a_0,b)$. By hypothesis, $N$ is an integer and we have

$$\frac{a_0^2+b^2}{a_{0}b+1}=N$$

that with simple algebra can be rearranged into

$$b^2-N{a}_{0}b+a_0^2-N=0. (\star )$$

This implies that the quadratic equation

$$x^2-N{a}_{0}x+a_0^2-N=0$$

has the solution $x=b$. Dividing the polynomial

$$x^2-N{a}_{0}x+a_0^2-N$$

by $x-b$ gives us1 the second root, $a_1=N{a}_0-b$, which again is an integer.

We need to show that $a_1<a_0$, i.e.

$$N{a}_0-b<a_0$$

or equivalently

$$N{a}_{0}b-b^2<a_{0}b.$$

Note that by bringing the leftmost two terms in the right-hand side of equation $(\star )$ to the left-hand side and flipping the equation, we have

$$N{a}_{0}b-b^2=a_0^2-N$$

but since $a_0<b$, this implies:

$$N{a}_{0}b-b^2=a_0^2-N<a_{0}b-N<a_{0}b$$

and thus

$$N{a}_{0}b-b^2<a_{0}b,$$

quod erat demonstrandum.

xmau propone per oggi un quizzino della domenica che consiste nel “risolvere” una semplice somma espressa utilizzando i numerali romani (I, V, X) in maniera impropria: invece di rappresentare addendi e risultato semplicemente esprimendo i numeri con il meccanismo romano, i numeri sono espressi nel sistema decimale posizionale che ci è familiare, ma ciascuna delle cifre è espressa con i numerali romani1: I per 1, II per 2, III per 3, IV per 4, V per 5, VI per 6, VII per 6, VIII per 8, IX per 9, con l'aggiunta difficoltà dell'assenza di spazi tra le cifre.

L'esposto del problema è il seguente:

IVIIIIIVIII +
IIVIIIII    =
-------------
VIIXIVI

L'assenza di spazi è proprio ciò che rende questa una “crittosomma”: è infatti impossibile, con un semplice colpo d'occhio, capire ad esempio se una sequenza come III rappresenta la cifra 3 o una delle coppie di cifre 21 e 12.

L'unica “sequenza” di cui possiamo essere sicuri è IX, giacché X rappresenta il valore 10 secondo il sistema di numerazione romano, e nel sistema posizionale da noi adottato non esiste una cifra con questo valore, per cui IX è sicuramente 9. Possiamo quindi “semplificare” la nostra crittosomma in:

IVIIIIIVIII +
IIVIIIII    =
-------------
VI9IVI

Rimangono da interpretare le due sequenze di numerali romani nella somma finale: VI, che può essere 6 o 51, e IVI che può essere interpretata in tre modi diversi: 151, 41, e 16.

Un dubbio

Un problema aperto (che speriamo non sia determinante per la soluzione) è la lettura delle cifre: le piú significative saranno scitte a destra, come vuole la convenzione che abbiamo ereditato dagli arabi, o saranno scritte a sinistra, come sembra suggerire l'allineamento?

Alla prova del 9

Per cercare di limitare le possibili interpretazioni possiamo osservare che non tutte le interpretazioni hanno la stessa congruità modulo 9. Specificamente, mentre le sequenze “additive” (simbolo di valore maggiore seguito da simboli di valori non inferiori) hanno tutte lo stesso valore modulo 9, quelle potenzialmente sottrattive (simbolo di valore inferiore seguito da simbolo di valore maggiore) possono avere due possibili interpretazioni, con valori modulo 9 che differiscono di un valore pari alla differenza tra il valore additivo e quello sottrattivo del simbolo di valore inferiore.

Nel nostro caso, le uniche coppie ambigue sono IV per cui la differenza di valore sarà 2. Come esempio, vediamo che VI alla “prova” del 9 darà sempre 6 (sia che venga letto come 6, sia che venga letto come 51), per IV abbiamo due valori diversi a seconda che IV abbia valore “additivo” (15 = 6) o “sottrattivo” (4).

Per la somma finale, alla prova del 9 abbiamo quindi due possibili valori: 4 (interpretazione additiva di IV) oppure 2 (intepretazione “sottrattiva” di IV).

Il secondo addendo ha pure un'unica sequenza IV, e quindi due interpretazioni: 3 (additiva) e 1 (sottrattiva).

Il primo degli addendi ha invece due sequenze IV , e quindi ha tre possibili valori (a seconda che le due sequenze siano entrambe additive, entrambe sottrattive, o una additiva ed una sottrattiva, indipendentemente da quale sia quale): i valori associati sono 1 (additive), 6 (sottrattive) e 8 (mista).

Alla prova del nove, le possibili combinazioni dei due addendi sono: $1+1=2$, $1+3=4$, $6+1=7$, $6+3=8+1=0$, $8+3=2$. Poiché la somma è congrua 4 o 2 modulo, possiamo scartare per il primo addendo l'interpretazione sottrattiva: quindi o entrambe le sequenze del primo addendo vanno lette additivamente, oppure la lettura del primo addendo è mista, e quella del secondo è additiva (caso $8+3=2$).

La cifra piú a sinistra

La cifra piú a sinistra della somma è 5 o 6, e quindi le cifre piú a sinistra dei due addendi devono arrivare almeno a 4 o 5, piú un opzionale riporto dalle due cifre successive (supponendo che la notazione metta a sinistra le cifre piú significative).

Osserviamo subito che questo non è possibile se per il primo addendo si utilizza la lettura puramente additiva: in tal caso infatti la cifra piú a sinistra del primo addendo è 1, mentre quella del secondo è al piú 2, arrivando a 3, che è insufficiente.

Ne segue che per il primo addendo si deve usare la lettura mista, con la prima sequenza IV interpretata sottrattivamente (ed a fortiori la seconda interpretata additivamente). Questo ci porta quindi nel caso $8+3=2$ della prova del9, che implica un'interpretazione additiva del secondo addendo, e sottrattiva della somma: la sequenza IVI con cui termina quest'ultima può pertanto essere letta solo come 41.

Possiamo quindi ulteriorimente semplificare la nostra crittosomma in

4IIIIIVIII +
IIVIIIII   =
------------
VI941

Dei rimanenti simboli V sappiamo che vanno interpretati additivamente, e quindi o avranno valore 5 (a sé stanti) o saranno parte di sequenze per 6, 7 oppure 8.

Il lungo problema dell'1

Un terzo aiuto nel vincolare le interpretazioni ci viene dal possibile numero di cifre. Per la somma abbiamo solo due possibili interpretazioni: 6941 e 51941, di lunghezza rispettivamente 4 e 5. Nessuno dei due addendi può avere una lunghezza superiore (potrebbero avere una lunghezza inferiore se le cifre meno significative fossero a sinistra ed avessimo un riporto tra quelle piú significative, a destra).

Questo vincolo risulta particolarmente potente in congiunzione con il problema dell'1: un interessante corollario dell'uso del sistema numerico romano per la rappresentazione delle cifre è l'assenza di un modo per rappresentare lo 0: questo ci aiuta perché, non potendovi essere 0 negli addendi, l'unica cosa che può fare spuntare la cifra 1 nella somma è una coppia di cifre con riporto.

Guardando alla somma, abbiamo due possibili interpretazioni rimaste: 6941, e 51941. La seconda, in particolare, ha un 1 in seconda posizione (non sappiamo ancora se per le decine o per le migliaia), e questo non è ottenibile in alcun modo.

Supponiamo infatti che la lettura corretta della somma sia 51941. La cifra piú a sinistra del secondo addendo dovrà quindi essere 1, poiché se dovessimo leggere la sequenza iniziale II come 2, avremmo $4+2=6$. (L'alternativa per arrivare a 5 come cifra piú a sinistra piú significativa richiederebbe un riporto dalle cifre precedenti, che però possono essere lette al massimo come $5+2=7$, e non potremo mai avere un riporto di $4$ dalle cifre ancora precedenti per arrivare ad un riporto dalle seconde.)

Saremmo quindi a

4IIIIIVIII +
11VIIIII   =
------------
51941

ma diventa a questo punto impossibile ottenere un 1 in seconda posizione, non potendo esserci uno zero nel primo addendo, o un riporto tale da lasciare un 1.

L'unica lettura possibile per la somma è quindi 6941, e questo richiede (sempre per una questione di riporti) che la cifra piú a sinistra del secondo addendo sia un 2: la nostra crittosomma è ora parzialmente risolta come

4IIIIIVIII +
2VIIIII    =
------------
6941

e possiamo affermare che tutti e tre i termini sono composti da 4 cifre: potrebbero essere 3 con un opportuno riporto dalla somma delle cifre piú significative, ma il primo addendo non può avere solo 3 cifre.

Il vincolo sulle lunghezze è particolarmente importante per l'interpretazione del secondo addendo, per il quale rimangono 6 simboli per 3 cifre, con poche letture possibili: 811; 721 o 712; 631, 622 o 613, ed infine 532 o 523.

Anche qui ci viene in aiuto la questione dell'1 (terminale, stavolta), che risolve, insieme al vincolo delle lunghezze, anche la questione dell'ordine delle cifre: l'unico modo per ottenere un 1 come cifra piú significativa sarebbe un riporto da due addenti con tre cifre, e come già detto il primo addendo non può avere solo 3 cifre.

Da questo si deducono due fatti importanti: le cifre meno significative sono a destra (quindi alla fine otterremo numeri con le cifre ordinate secondo la convenzione cui siamo abituati), e per gli addendi queste sono rispettivamente 8 e 3, le uniche letture possibili per ottenere un riporto che ci lasci indietro l'1 della somma:

4IIIII8 +
2VII3   =
---------
6941

che lascia come possibili letture per il secondo addendo solo 2613 o 2523. E poiché dobbiamo arrivare a 9 come seconda cifra da sinistra, ed abbiamo al piú 3 dal primo addendo, e nessun riporto, la cifra dopo il 2 deve essere un 6, con un 3 in sua corrispondenza sul primo addendo, che ci permette una completa risoluzione del problema:

4328 +
2613 =
------
6941

xmau propone per oggi un quizzino della domenica che consiste nel trovare la singola cifra (di quelle da 1 a 9) che rimane fuori inserendo nelle caselle del seguente schema le altre otto:

Il quiz chiede di trovare la cifra “in piú”, e per farlo è sufficiente (ma, come vedremo, non necessario) risolvere lo schema.

Cominciamo dalla riga superiore: abbiamo una divisione $a:b=c$ in cui i tre numeri $a,b,c$ devono essere tutti distinti tra loro e compresi tra 1 e 9. Questo ci aiuta ad escludere, come valori possibili di $a$, sia l'1, sia i numeri primi (2, 3, 5, 7) sia i quadrati (4, 9), ciascuna con motivazioni diverse:

• se $a=1$, allora deve essere $b=c=1$, e quindi abbiamo ripetizioni;
• se $a$ è primo, dovendo essere $b\ne a$ dovrebbe essere $b=1$ (poiché $a$ non ha altri divisori, essendo primo), e quindi $c=a$ (ripetizione);
• se $a$ è un quadrato, come divisori ha solo $1,a$ (esclusi), o un terzo valore $b\ne a$ per cui $a:b=b$, nuovamente una ripetizione.

Gli unici valori possibili per $a$, ovvero per la casella in alto a sinistra dello schema, sono quindi 6 oppure 8, per cui gli unici valori possibili per le altre due caselle della prima riga sono 2, 3 oppure 4.

Osserviamo ora che la colonna di destra di fatto è analoga alla riga superiore, poiché $a:b=c$ è equivalente a $c\times b=a$: la casella in basso a destra vale quindi 6 oppure 8, e la casella centrale della colonna vale pure 2, 3 oppure 4.

Quindi o la casella in alto a sinistra vale 6, e quella in basso a destra vale 8, oppure è al contrario. In entrambi i casi, possiamo osservare che la casella in alto a destra deve essere il divisore comune a 6 ed 8, e quindi deve essere 2.

Usando una notazione simil-sudoku possiamo scrivere:

e la presenza delle coppie 3/4 e 6/8 ci permette di escludere questi 4 valori dalle tre caselle mancanti, che possono quindi solo contenere i valori 1, 5, 7 e 9.

Soluzione del quiz

Osserviamo che già ora, senza completare lo schema, possiamo dire quale valore sarà escluso: nessuna delle tre caselle rimanenti, infatti, può avere valore 9, giacché questo renderebbe impossibili le operazioni necessarie per arrivare rispettivamente a 6 o 8.

La risposta al quiz è quindi: il 9 è la cifra mancante.

Completamento dello schema

Come per il lato superiore e quello destro, possiamo osservare che il lato sinistro e quello inferiore presentano la medesima simmetria: la sottrazione sul lato sinistro è equivalente alla somma sul lato inferiore. Ragionando analogamente a quanto visto per la divisione e la moltiplicazione, possiamo quindi dire che la casella inferiore sinistra prenderà l'addendo comune (in questo caso, 1) e le altre due caselle avranno rispettivamente 5 e 7, a seconda di dove saranno 6 ed 8.

Per completezza, possiamo quindi osservare che lo schema ha due possibili soluzioni, rivelate passando il cursore del mouse sull'immagine seguente (a sinistra e a destra per risultati diversi):

There is something I learned today that, as a mathematician, I should have probably learned some time ago: the name of the function that solves the equation

$$x{e}^x=y$$

where $e$ is Napier's constant. I did know that the equation didn't have an elementary solution, but that didn't really help me solving the problem I wanted to solve, which was to find a solution to the equation:

$$x^2{e}^{kx}=c$$

for positive $k,c$ (and $x$ too, for what it's worth).

Apparently the non-elementary function we're interested in is called Lambert's $W$ or $\omega$ function, or the product logarithm. It is the (multi-valued, in fact) function such that

$$x=W\left(y\right)\iff y=x{e}^x.$$

The name product logarithm comes from the analogy with the (natural) logarithm

$$x=ln\left(y\right)\iff y=e^x$$

and the fact that there's an extra $x$ multiplying the exponential on the right hand side of the equation we want to invert (solve for $x$).

I'm not going to discuss the properties of the function (I mean, what would the Wikipedia link above be here for, otherwise), but I will show how it can be used to solve the equation we're interested in, something that is not shown on Wikipedia and actually had me thinking for a while —mostly about the fact that I was obvioulsy missing something trivial, as it often happens in mathematics.

The general idea, to use the product logarithm in solving an equation, is to bring it in the form

$$f\left(x\right)e^{f\left(x\right)}=c$$

which then leads to

$$f\left(x\right)=W\left(c\right)$$

and finally, assuming $f$ is invertible, to $x=f^{-1}\left(W\left(c\right)\right)$. Of course, how to get to the form we want is not always obvious.

Let us take for example the equation I wanted to solve:

$$x^2{e}^{kx}=c.$$

Making sure $k$ appears both as power of $e$ and outside of it is trivial: simply multiply by $k$ both sides. However, how to make sure we have the same power of $x$ muliplying the exponential and as a power is not: the most obvious ideas (divide by $x$ both sides, or multiply and divide by $x$ the power and then try to juggle things around) don't really take you anywhere.

We'd have to be able to take the square root … wait, that might actually work!1 If we take the square root on both sides, then we get two equations (with the only difference being the sign, so we'll write it as one):

$$x{e}^{\frac{k}{2}x}=\pm \sqrt{c}.$$

Now we can balance the constants:

$$\frac{k}{2}x{e}^{\frac{k}{2}x}=\pm \frac{k}{2}\sqrt{c}$$

and apply the definition of $W$ to get

$$\frac{k}{2}x=W(\pm \frac{k}{2}\sqrt{c})$$

and finally

$$x=\frac{2}{k}W(\pm \frac{k}{2}\sqrt{c}).$$

As mentioned, $W$ is a multi-valued function. However, for the specific application we derived the equation for we needed the largest positive value, meaning we need specifically the $W_0$ branch (which is the only one that gives positive value), and since $W_0$ is monotone increasing, we want the solution with the largest argument, that is, ultimately:

$$x=\frac{2}{k}{W}_0\left(\frac{k}{2}\sqrt{c}\right),$$

a surprisingly elegant formula —for which there is no built-in function in the C++ standard library.

(Surprisingly, making the latter discovery wasn't enough to reduce my enthusiasm and satisfaction in finding the answer and discovering the function, although it will be a problem I'll have to solve in the next few days —I'm not really looking forward to having to include the GSL or Boost libraries just for this.)

Nation, flags and memory card games

One of the “portable” games offered by Flying Tiger is a memory card game with national flags as a theme. The game has $68$ cards ($34$ national flags) and I like it not only because it's one of the largest memory games I've seen, if not the largest (about $50$ cards or fewer being the norm, for what I can see), but also because of its educational side-effect, as each card features not only the flag, but also (in the “native” language as well as in English) the name of the nation and the name of the capital city.

After the first play, my first consideration was that Mexico was missing from the flags/nations (why Mexico? personal reasons). The next thing I noticed was that the selection of nations is essentially centered around Europe, with only a handful of extra-European nations included. This is when I realized how small the selection is: $34$ nations is less than a fifth of the nations of the world, even if you consider the smallest possible set (the $190$ states whose sovereignity is undisputed).

So obviously, my next thought was: how large would such a memory card game be? $190$ states (at least) means $190$ pairs, or $380$ cards. The Flying Tiger cards are squares (with rounded corners) with a side length of $55$mm, and I don't think it's reasonable to go much smaller. In fact, considering the padding between cards that is needed for practical reasons when laying them down for playing, we can assume square tiles with a $6$cm side. That's $36$cm², or $0.0036$m² per tile. $380$ such tiles would cover an area of $1.368$m².

Curiously, $380$ is very close ${19.56}^2$, which means that if the $190$ pairs were laid out in a square, they would take up a square area with a side of almost exactly $117$cm, or $1.17$m. Even I would have troubles reaching the cards on the opposite side of the table. Of course, you can't actually do that, because $380$ is not a perfect square, so you cannot tile the cards on a square: you would have to either have to do a $19\times 20$ rectangle (with sides of length $1.14$m and $1.2$m respectively), or a $20\times 20$ square with an empty diagonal.

The issue of placing the memory cards in a pleasing pattern has always fascinated me. My daughter has a $48$-cards game, which I like because the card can be laid out in a $7\times 7$ square with a hole in the center. My son has a $32$-cards game that can be laid out as a $6\times 6$ square with missing corners.

In fact, the $68$-cards game that spurred these consideration is a bit annoying because $68=8\times 8+4$, but the 4 extra cards cannot be placed in a nice symmetric way with good alignment because the sides of the square are even, not odd. Possible placemets are the “wheel” pattern (extending each of the sides with one card), the “shifted” pattern (place each extra card on the middle of each side, spanning the gap between the two central cards of the side), or the “versus” pattern, good when playing 1v1 games, with two extra cards on each of two opposing sides.

Obviously, the next question is: how many nations would you have to include to be able to tile out the cards in a “good” pattern?

Perfect squares

this solution can be achieved with $20\times 20=400$ cards, or $200$ states (note that without holes or extra cards, the square must be even); problem is, Wikipedia lists $206$ states when including the ones with disputed sovereignity; we'd have to cherry-pick some, leaving out six of them;

The hole

an odd square can be made even by taking out a central hole;

a possible solution would be $19\times 19-1=360$, but this would require removing $10$ nations from the “uncontroversial” list;

the next one would be $21\times 21-1=440$, which would require $220$ states: can we find $14$ other territories to add to the $206$ states currently listed by Wikipedia?

Give or take more

good patterns can be obtained by removing the 4 corners, or by having 4 extra cards —particularly with an odd square;

$20\times 20-4=396$ would require $198$ states, which could be assembled from the $193$ UN member states, the $2$ observer states, plus more (decisions, decisions);

$21\times 21-1-4=436$ would require $218$ states: we'd only need to find $12$ more than the ones listed by Wikipedia.

$19\times 19-1+4=364$ would require $182$ states: still too little;

As it turns out, $380$ isn't even that bad: since $19\times 19-1+4\times 5=361-1+20=380$, a decent tiling can be found with a $19\times 19$ square, without the center, plus $5$ cards centered on each side.

And a long stick to pick the cards on the other side of the table.

But I want more

Revision 6.0 of the Unicode standard introduced Regional Indicator Symbols and their ligatures mapping to «emoji flag sequences». Of the $26\times 26=676$ possible combinations, only $270$ are considered valid, and if we ignore the $12$ «deprecated region sequences», this leaves us with $256+2=258$ “current” region sequences. We could use this as the basis for our memory card game!

With $258$ regions we have $258\times 2=516$ cards. What would be a good pattern? We have $516=22\times 22+32=22\times 22+4\times 8$ which actually lends itself to a decent layout: a $22\times 22$ square, plus $8$ cards centered on each side.

How large would such a memory game be? At $6$cm per tile, the main square wold be $1.32$m wide. The extra cards on each side would make it $1.44$m wide, which is actually a pretty nice number1 —if unwieldy in practice. Still, if we're basing our choice on what Unicode supports, why not build such a game around computers? You'd need lots of players to make sense of it anyway.

Something that everybody (but the staunchiest believer in a Flat Earth) can agree on is that you can see farther by climbing higher. Indeed, getting to a higher place not only helps you see beyond any obstacles that might be in your line of sight, but it actually helps you see farther along the surface of the Earth even if there are no other obstacles than Earth's own curvature: it's the reason why ships have a Crow's nest.

So the obvious question is: how much farther can you see by climbing higher? And people that follow me will surely have already caught on: yes, we're trying to solve the inverse problem to how high do you have to go. In fact, we'll recycle the figure:

Again, we assume we're dealing with a spherical Earth of known radius $r$. This time, however, we assume $h$ known (how far high we are), and we want to know $d$, the distance along the geodetic to the farthest point we can see1. Equivalently, we want to know the angle $\alpha$ subtending the geodetic, since by definition of radian its amplitude in radians is just $\frac{d}{r}$, hence $d=r\alpha$. And again, of course, we know that it will be for sure $0\le \alpha <\frac{\pi }{2}$, i.e. $2d<\pi r$.

In fact, from our study on the direct problem we know that the relationship between $h$ and $\alpha$ can be expressed as

$$h=r(\frac{1}{cos\alpha }-1)$$

which we can invert rather easily; divide by $r$:

$$\frac{h}{r}=\frac{1}{cos\alpha }-1$$

add $1$ on both sides:

$$\frac{h}{r}+1=\frac{1}{cos\alpha }$$

and take the reciprocals, swapping the two sides:

$$cos\alpha =\frac{1}{\frac{h}{r}+1}.$$

Given our range of existence for $\alpha$, we can use the inverse function of the cosine, $arccos$, to get the final formula for $\alpha$

$$\alpha =arccos\left(\frac{1}{\frac{h}{r}+1}\right)$$

and from this get

$$d=r\alpha =rarccos\left(\frac{1}{\frac{h}{r}+1}\right).$$

As a quick check, for $h=0$ we have $\alpha =arccos1=0$, while for $h$ growing to infinity we get $\alpha =arccos0=\frac{\pi }{2}$, as we would expect.

Approximation?

As with the previous problem we would like to devise a formula that can be applied easily under the assumption that the angle is small. The most obvious approach would be to use the first term(s) of the Taylor expansion of the arc cosine, as it's usually done for small-angle approximations. However, Taylor series for these functions are usually developed around 0, whereas we would like to develop them around 1, since a small angle, in our case, leads to an argument of 1 for the arc cosine.

(In fact, we can see that better if we focus on the argument to the arc cosine:

$$\frac{1}{\frac{h}{r}+1}=1-\left(\frac{h}{r}\right)+{\left(\frac{h}{r}\right)}^2-{\left(\frac{h}{r}\right)}^3+...$$

assuming $h<r$.)

From a mathematical perspective, writing a Taylor expansion of $arccos$ around 1 is not recommended, since some assumptions needed to ensure good convergence behavior for the series cannot be guaranteed (in particular, the fact that 1 is at the boundary of the domain of the arc cosine rather than inside it is a no-no).

Worse, if we opt to disrergard the warning, we find out that we can't even do what we want, since the derivative of the arc cosine is

$$-\frac{1}{\sqrt{1-x^2}}$$

which isn't even defined for $x=1$.

We could try leveraging the nice relationship between the arc cosine and the arc secant:

$$arccos\left(\frac{1}{\frac{h}{r}+1}\right)=arcsec(\frac{h}{r}+1),$$

but that barely helps us, since the arc secant's first derivative is

$$\frac{1}{x\sqrt{x^2-1}}$$

for $x>1$ so that again, for $h=0$, we would have a degenerate case.

Look ma, no inverse functions!

To work around this conundrum, let's take a step back, to:

$$cos\alpha =\frac{1}{\frac{h}{r}+1},$$

and let's use the small-angle approximation for the cosine; we get

$$1-\frac{{\alpha }^2}{2}=\frac{1}{\frac{h}{r}+1}$$

or

$$\frac{{\alpha }^2}{2}=1-\frac{1}{\frac{h}{r}+1}=\frac{\frac{h}{r}}{\frac{h}{r}+1}=\frac{h}{h+r}$$

which gives us a much more approachable

$${\alpha }^2=2\frac{h}{h+r}$$

and finally, with an ugly square root,

$$\alpha =\sqrt{2\frac{h}{h+r}}.$$

In fact, there's two horrible things in this formula: the division of a (potentially) very small number by a very large number, and a square root.

For the ratio, we can rewrite things with our friend $q=\frac{r}{h}$ under the assumption that $h\ne 0$ (sensible, since otherwise $\alpha =0$, which isn't very interesting):

$$\alpha =\sqrt{\frac{2}{1+q}}$$

with $q$ large (in fact, potentially tending to $+\infty$).

As it turns out, ignoring for a moment the $\sqrt{2}$ factor, the rest has a power series expansion, in the form of a Puiseux series that can be written in an acceptable form in terms of $p=\sqrt{\frac{1}{q}}=\sqrt{\frac{h}{r}}$:

$$\alpha =\sqrt{2}(p-\left(\frac{1}{2}\right)p^3+\left(\frac{3}{8}\right)p^5-\left(\frac{5}{16}\right)p^7+\cdots ).$$

Curiously (but unsurprisingly) the first order term is what we get if we just ignore the 1 in the non-expanded formula.

More in general, we shouldn't be surprised by the need to compute $p$ with a square root, given that in the other direction we used $s=2q^2$. But then again, if we have to compute a square root, why even bother doing it for $p$ when we can do it directly for $\alpha$?

So, shall we just stop at

$$d=r\alpha =r\sqrt{\frac{2}{1+q}}$$

or can we do something more interesting?

(Aside for local manipulations, such as:

$$d=r\sqrt{2\frac{h}{h+r}}$$

of course.)

Another rollback

To find a better formula, let's roll back to

$$1-\frac{{\alpha }^2}{2}=\frac{1}{\frac{h}{r}+1}$$

and work on the right-hand side, which we can write as ${(1+\frac{h}{r})}^{-1}$. For small $h$ (compared to $r$) this has a curiously nice expansion:

$$1-\frac{h}{r}+{\left(\frac{h}{r}\right)}^2-{\left(\frac{h}{r}\right)}^3+\cdots$$

so that our equation for $\alpha$ becomes:

$$\frac{{\alpha }^2}{2}=\frac{h}{r}-{\left(\frac{h}{r}\right)}^2+\cdots$$

and truncating:

$$\frac{{\alpha }^2}{2}=\frac{h}{r}(1-\frac{h}{r}),$$

but also

$$\frac{{\alpha }^2}{2}={\left(\frac{h}{r}\right)}^2(\frac{r}{h}-1).$$

The nice thing about these formulas is that we can rewrite the right-hand side in terms of $q$, giving us

$$\frac{{\alpha }^2}{2}=\frac{1}{q}(1-\frac{1}{q})=\frac{q-1}{q^2}$$

which comes in very handy if we don't stop at $\alpha$, but actually go and compute $d$:

$$d=r\alpha =r\frac{\sqrt{2(q-1)}}{q}=h\sqrt{2(q-1)}=h\sqrt{2\frac{r-h}{h}}$$

that is interesting since it expresses the distance in terms of “the height, multiplied by something” rather than “the radius of the planet, multiplied by something”.

In fact, in this case we can even try pulling out the 2 from under the square root:

$$d=2h\sqrt{\frac{r-h}{2h}}$$

(well, sort of; but at least it has some symmetry to it).

A different approach

Remember that we could also express $h$ as the exterior secant, that could be expressed in terms of the tangent function, giving us

$$h=rtan\left(\alpha \right)tan\left(\frac{\alpha }{2}\right).$$

Can we try inverting this instead? Let us proceed by expressing the tangent in terms of $t=tan\left(\frac{\alpha }{2}\right)$:

$$h=r\frac{2t}{1-t^2}t=r\frac{2t^2}{1-t^2}$$

and let's solve for $t$:

$$h(1-t^2)=2r{t}^2$$

$$(2r+h)t^2=h$$

$$t^2=\frac{h}{2r+h}.$$

We can go for a direct solution now, with

$$\frac{\alpha }{2}=arctan\left(\sqrt{\frac{h}{2r+h}}\right).$$

The good news is that, in contrast to the situation with the arc cosine, we would need to go now for the expansion of the arc tangent for small values of the tangent, which is just its argument, giving us the following approximation:

$$\frac{\alpha }{2}=\sqrt{\frac{h}{2r+h}},$$

or

$$\alpha =2\sqrt{\frac{h}{2r+h}},$$

If instead we wanted to use small-angle approximation for $t$, giving us $t^2=\frac{{\alpha }^2}{4}$, we'd get

$${\alpha }^2=4\frac{h}{2r+h},$$

or finally

$$\alpha =2\sqrt{\frac{h}{2r+h}}.$$

Would you look at that, it's the same formula! That's good news, like the fact that the 2 is already out of the square root (well, at least one of them!) and when we go for $d$:

$$d=2r\sqrt{\frac{h}{2r+h}}$$

we have the same nice symmetry that we had with the previous approach —but no $h$ outside of the square root.

Going crazy

As an alternative, we could leverage that fact that $0\le \alpha <\frac{\pi }{2}$, so that we are in the range where

$$tan\left(\frac{\alpha }{2}\right)=\frac{tan\alpha }{1+\sqrt{1+{tan}^2\alpha }}$$

which would give us

$$h=r\frac{{tan}^2\alpha }{1+\sqrt{1+{tan}^2\alpha }}$$

that we can manipulate to

$$1+\sqrt{1+{tan}^2\alpha }=r\frac{{tan}^2\alpha }{h}$$

$$\sqrt{1+{tan}^2\alpha }=r\frac{{tan}^2\alpha }{h}-1$$

$$1+{tan}^2\alpha ={(r\frac{{tan}^2\alpha }{h}-1)}^2$$

$$h^2+h^2{tan}^2\alpha ={(r{tan}^2\alpha -h)}^2$$

$$h^2+h^2{tan}^2\alpha =r^2{tan}^4\alpha -2hr{tan}^2\alpha +h^2$$

$$r^2{tan}^4\alpha -(h^2+2hr){tan}^2\alpha =0$$

And assuming $\alpha \ne 0$ (which for us would only be the case if $h=0$) we can actually simplify this to

$${tan}^2\alpha =\frac{h^2+2hr}{r^2}.$$

Going for the small-angle approximation (that, as we've seen, gives us the same result regardless if we go first for the arc tangent), we finally get:

$$\alpha =\frac{\sqrt{h^2+2hr}}{r}$$

and for the distance that we're interested in:

$$d=r\alpha =\sqrt{h^2+2hr}=h\sqrt{1+2\frac{r}{h}}=h\sqrt{1+2q},$$

with an amazing similarity to the $h\sqrt{2(q-1)}$ we had found before. (Of course, for small enough $h$ i.e. large enough $q$, the extra term, be it $+1$ or $-2$, doesn't really matter, $2q$ prevails.)

(As someone might have noticed, this approximation is nothing more than the length of the $HS$ segment, i.e. the distance from the observation point «as the crow flies» rather than along the geodetic1.)

TL;DR

Pick your poison (as usual, $q=\frac{r}{h}$). The exact formula is:

$$d=rarccos\left(\frac{1}{\frac{h}{r}+1}\right)=rarccos\left(\frac{r}{h+r}\right)=rarccos\left(\frac{q}{1+q}\right).$$

And several possible approximations:

$$d=r\sqrt{2\frac{h}{h+r}}$$

$$d=h\sqrt{2(q-1)}$$

$$d=2h\sqrt{\frac{r-h}{2h}}$$

$$d=2r\sqrt{\frac{h}{2r+h}}$$

$$d=h\sqrt{1+2q}$$

$$d=h\sqrt{1+2\frac{r}{h}}$$

Oh, and do you know how you can tell that this is the inverse problem? Because the formulas are uglier.

Example

How far can a human being with their eyes 2 meters from the ground (yes, it's a tall human being) see? Let's pretend that $r$ is 6,400 km (yes, it's a larger-than-ours planet). We have $2q=6,400,000$ (how convenient, the 2 simplifies with $h$!), so its square root is marginally (less than 0.2) smaller than 2530 (damn, one would hope that with that nice 64 … but no, we went and had an odd number of zeroes!). We multiply that by the 2 meters of height, and it turns out that the tall man can see over 5 km in the distance, marginally less than 5,060 m. The exact solution would be 5,059.64… m —not bad, not bad at all!

Let's say you managed to climb up to the top of Mt Everest: then $2q$ would be something less than 1,500, and its square root around 38. If not for the weather and the mountains and everything else, you could se things nearly 340 km away —336 km and counting, which is still just as good as the exact solution, within less than a meter.

It's interesting to see what happens if we push the boundaries of these approximations: assume $h$ equal to $r$, i.e. $q=1$. Then the exact formula gives us $d=r\frac{\pi }{3}$, i.e. around $1.05\cdot r$. What about the rest?

Overall, the situation isn't even that bad: only one formula completely misses the target, and for two out of three of the others the error is relatively small (5% to 10%). Sadly, but unsurprisingly, the worst behaving approximations are the ones expressed for $h$ rather than $r$: the extra benefit in their simplification comes more strongly from the “small $h$” assumptions, and that's why they fail the hardest.

The extra mile

A slightly different question that we might be interested in is: how much more can you see by going to higher ground? In other words, if we have two different heights $h_1$ and $h_2$ (say, $h_1<h_2$), and the corresponding distances $d_1$ and $d_2$ (for which it will still be $d_1<d_2$, since the arc cosine is nondecreasing), what would be, for example, the ratio $\frac{d_2}{d_1}$ compared to the ratio $\frac{h_2}{h_1}$, or the difference compared to the difference?

For the ratio, I'm not aware of a formula, but for the difference there's actually a way to express the difference of the arc cosines, giving us

$$d_2-d_1=rarccos(\frac{q_1{q}_2}{(1+q_1)(1+q_2)}+\sqrt{(1-{\left(\frac{q_1}{1+q_1}\right)}^2)(1-{\left(\frac{q_2}{1+q_2}\right)}^2)})$$

which is quite the mouthful that offers only a little bit of possibility for simplification, if it can be called that way:

$$d_2-d_1=rarccos(\frac{q_1{q}_2}{(1+q_1)(1+q_2)}+\sqrt{\frac{1+2q_1}{{(1+q_1)}^2}\frac{1+2q_2}{{(1+q_2)}^2}})$$

or possibly even

$$d_2-d_1=rarccos\left(\frac{q_1{q}_2+\sqrt{(1+2q_1)(1+2q_2)}}{(1+q_1)(1+q_2)}\right).$$

Of course, if we couldn't easily reason (or simplify) the analytical formula for the geodetic distance visible from a certain height, much less so we can hope to do derive any interesting information from the present formula.

A bit of insight on the other hand can be derived by looking at the derivative of $d$ as a function of $h$, in particular using the expression for the arc secant.

From

$$d=rarcsec(\frac{h}{r}+1)$$

and the arc secant derivative for positive arguments, we get

$$\frac{\partial d}{\partial h}=\frac{1}{(\frac{h}{r}+1)\sqrt{{(\frac{h}{r}+1)}^2-1}}$$

(interestingly enough, the $r$ on the numerator cancels with the $r$ coming from the derivative of $\frac{h}{r}+1$). We can work on simplifying this

$$\frac{\partial d}{\partial h}=\frac{r^2}{(h+r)\sqrt{{(h+r)}^2-r^2}}$$

and finally

$$\frac{\partial d}{\partial h}=\frac{r^2}{(h+r)\sqrt{h^2+2hr}}$$

(and we can rejoyce in the knowledge that even well-known software tools with strong analytical capbilities have issues trying to integrate that, while we know the result from the previously computed $d_2-d_1$) that tells us pretty clearly how quickly the rate of growth decreases as $h$ increases.

We can still massage the expression to give

$$\frac{\partial d}{\partial h}=\frac{r^2}{(h+r)h\sqrt{1+2q}}$$

or even

$$\frac{\partial d}{\partial h}=\frac{q}{1+q}\frac{q}{\sqrt{1+2q}},$$

which is a bit improper (we're expressing a derivative with respect to $h$ using $q$), but it makes life easier for us if we want to know how small variations in height affect how far you can see.

Let's pretend for example that humans, on average have their eyes about 1.6 m from the ground; then $q=4\cdot {10}^6$ assuming our usual $r$, and the rate of change of $d$ with respect to $h$ is about 1,414: a centimeter of difference alters your perspective by about 14 m.

Let's linearize this too!

Of course, the expression we have for the derivative isn't that nice either. It would be better if we could approximate that one with something more manageable. And there is, in fact an expansion for the formula assuming $h$ small (or $q$ large):

$$\frac{\partial d}{\partial h}=\sqrt{\frac{q}{2}}(1-\frac{5}{4q}+\frac{43}{32q^2}-\frac{177}{128q^3}+\cdots )$$

and our previous example works perfectly if we stop at the first order, since $\sqrt{\frac{q}{2}}=\sqrt{2\cdot {10}^6}\cong 1414$.

And now that we have it easy, we can see what happens around 2 m of baseline (yes, we can still use the first-order approximation for the derivative): $\sqrt{\frac{q}{2}}=\sqrt{1.6\cdot {10}^6}\cong 1264$: a centimeter of difference alters your perspective by less than 13 m.

(Notice how moving our baseline up by 40 cm has reduced the effect of fluctuations by over 1 m per cm.)

You are standing on the beach of a great lake, and realize that the other side is far enough to not be visible. You'd have to get to a higher place. But how much higher?

To simplify things a little bit, let us assume that the Earth is spherical, so that the geodetic (shortest path on the surface) connecting any two points on the surface is the arc of a great circle, and let as denote the radius of this sphere by $r$ (which is something less of 6,400 km).

Let us denote by $d$ the distance (along the geodetic) between the place $P$ where we are and the place $S$ we want to see. Let $h$ be the distance above the Earth surface our eyes have to be to be able to see $S$ due to the curvature of the Earth.

Observe that the center of the earth $C$, the place $S$ we want to see and the place $H$ we have to be at to see it represent a right triangle with hypothenuse $CH$ and legs $CS$ and $SH$. We also have $CH=CP+PH=r+h$, $CS=r$ and the arc $PS=d$.

By definition of radian, the angle $PCS$ has amplitude $\alpha =\frac{d}{r}$ (radians). As a side note, we remark that this whole construction only makes sense if $\alpha <\frac{\pi }{2}$, or $2d<\pi r$ (we will discuss this more later).

We also have that $cos\alpha =\frac{CS}{CH}$, and thus $CH=\frac{CS}{cos\alpha }$, that is $r+h=\frac{r}{cos\alpha }$ and finally:

$$h=r(\frac{1}{cos\alpha }-1)$$

or

$$h=r\frac{1-cos\alpha }{cos\alpha }.$$

Approximation

To proceed further, let us assume that $d$ is very small compared to $r$, so that the cosine of the angle is very close to 1. We can then make use of the small-angle approximation $cosx=1-\frac{x^2}{2}$, which brings us to

$$h=r\frac{\frac{{\alpha }^2}{2}}{1-\frac{{\alpha }^2}{2}}$$

or

$$h=r\frac{{\alpha }^2}{2-{\alpha }^2}$$

and rememering that $\alpha =\frac{d}{r}$,

$$h=r\frac{d^2}{2r^2-d^2}.$$

Taking advantage of the fact that $\frac{r}{d}$ is probably easier to compute than $\frac{d}{r}$ for us, we can rewrite the previous expression as

$$h=\frac{r}{2{\left(\frac{r}{d}\right)}^2-1}.$$

A different formula

Let's go back to

$$h=r(\frac{1}{cos\alpha }-1)$$

and remember that, with $t=tan\left(\frac{\alpha }{2}\right)$, we can write $cos\alpha =\frac{1-t^2}{1+t^2}$, so:

$$h=r(\frac{1+t^2}{1-t^2}-1)$$

or

$$h=r\frac{1+t^2-1+t^2}{1-t^2}$$

simplifying to

$$h=r\frac{2t^2}{1-t^2}$$

or still again, dividing numerator and denomitator by $t^2$,

$$h=\frac{2r}{\frac{1}{t^2}-1}$$

For small $\alpha$ we can approximate $t=\frac{d}{2r}$ and $\frac{1}{t}=2\frac{r}{d}$. This gives us

$$h=\frac{2r}{4{\left(\frac{r}{d}\right)}^2-1}=\frac{r}{2{\left(\frac{r}{d}\right)}^2-\frac{1}{2}}$$

The only difference is that we're subtracting $\frac{1}{2}$ instead of 1 at the denominator. In fact, in most cases (small $d$) we can completely disregard the subtracting costant.

A historical note

When computers were not as common as they are today, and time-consuming accurate computations were optimized by the use of look-up tables, several derived trigonometric functions were in common usage. The one we care about is the exterior secant (exsec for short), that represents exactly the ratio of the length we are interested in to the radius of the circle:

$$h=rexsec\alpha .$$

The interesting thing about $exsec$ is that you can express it in terms of the tangent simply as

$$exsec\alpha =tan\alpha tan\left(\frac{\alpha }{2}\right).$$

The first terms of the Taylor expansion around 0 for this function are:

$$\frac{{\alpha }^2}{2}+5\frac{{\alpha }^4}{24}+61\frac{{\alpha }^6}{720}+\cdots$$

as usual with $\alpha =\frac{d}{r}$.

If we stop at the first term (the same we would get from our knowledge of the first-order approximation of the tangent), we get an approximation of $h$ as

$$h=\frac{r}{2}{\left(\frac{d}{r}\right)}^2=\frac{d^2}{2r}$$

which, while written differently, is in fact the same expression that we've seen already, but with a null constant —as anticipated.

Knowing additional terms allows us to write higher order approximation (if we would ever need it):

$$h=r(\frac{1}{2}{\left(\frac{d}{r}\right)}^2+\frac{5}{24}{\left(\frac{d}{r}\right)}^4)=\frac{d^2}{2r}(1+\frac{5}{12}{\left(\frac{d}{r}\right)}^2).$$

If we wanted to express this in terms of the easier-to-compute-and-square $q=\frac{r}{d}$, we would get:

$$h=\frac{r}{2}(\frac{1}{q^2}+\frac{5}{12q^4})=\frac{r}{2q^2}(1+\frac{5}{6\cdot 2q^2}).$$

Finally, since we know the next term in the series, let's do that (and stop there, since coefficients start becoming very large afterwards): expanding $\alpha$ we get

$$h=r(\frac{1}{2}{\left(\frac{d}{r}\right)}^2+\frac{5}{24}{\left(\frac{d}{r}\right)}^4+\frac{61}{720}{\left(\frac{d}{r}\right)}^6)$$

and expressing this in terms of $q$:

$$h=\frac{r}{2}(\frac{1}{q^2}+\frac{5}{12q^4}+\frac{61}{360q^6})=\frac{r}{2q^2}(1+\frac{1}{6\cdot 2q^2}(5+\frac{61}{15\cdot 2q^2})).$$

TL;DR summary

If you want to know how high you have to go over the surface of a sphere of radius $r$ to see a point which is at distance $d$ along the surface of the sphere, compute $q=\frac{r}{d}$ and then your height can be computed as

$$h=\frac{r}{2q^2}.$$

For higher-order terms, set $s=2q^2$. The second term then gives us

$$h=\frac{r}{s}(1+\frac{5}{6s}),$$

and if we want to push it further

$$h=\frac{r}{s}(1+\frac{1}{6s}(5+\frac{61}{15s})).$$

(The formulas are in Horner's form, which makes for quicker computation and express elegantly the “extra contribution” from each new term.)

An example

As an example, let's say that $d$ is about 160 km, which puts $\frac{r}{d}$ at around 40, squared to 1,600, doubled to 3,200. Disregarding the subtracting constant (i.e. using the exsecant expansion), the final result is $h=\frac{6400}{3200}=2$ km. The correct value would be $2.00052...$, so our approximation is good within half a meter out of 2km, a relative error of about 2.6%.

Limitations

You can't see further than a quarter circle in each direction, and that's only at infinite distance from the sphere surface; so we must have $\frac{d}{r}=\alpha <\frac{\pi }{2}$ or $2d<\pi r$. (Using the approximation $\pi \approx \frac{22}{7}$, which is a slight overestimation, we get the easier condition $7d<11r$).

On the Earth, this would mean distances up to about 10,000km, which means you wouldn't be able to see Cape Town from Reykjavik (over 11,400km), but you could see Hong Kong from Rome (9,280km).

However, the formulas we presented aren't accurate in the whole domain: the error term for the higher order approximation is of order 6, and in the highest order we presented is of order 8, which is very good as long as your angles are less than 1 radian, but actually gets really bad really fast after that.

(Intuitively, you can tell that the formula doesn't work when the distance approaches its maximum because the exact formula diverges, while the ones we have proposed don't.)

To see this in action, consider the Rome to Hong Kong case. We have $q=1.45$, squared to $2.1025$, doubled to $s=4.205$.

Our lower-order estimate for $h$ is 1,522km. Our higher-order estimate for $h$ is 1,824km. Our highest-order estimate is 2,160km. The correct answer is 46,711km, over 20 times higher!

So, how far can you push the formula? How large can the angle be before the error you commit is too large? What would be a possible workaround? (Aside from the obvious: use the exact formula.)

As visually discussed here, a set of equations has recently been popping up as graffiti in Belgium. The equations define five functions of one variable, namely:

$$\begin{array}{rcl}f\left(x\right)& =& 2+\sqrt{-{(x-2)}^2+1}\\ g\left(x\right)& =& 2-\sqrt{-{(x-2)}^2+1}\\ h\left(x\right)& =& 3x-3\\ i\left(x\right)& =& -3x+9\\ j\left(x\right)& =& \mathrm{0,2}x+\mathrm{1,7}\end{array}$$

Plotting the five functions with $x\in [1,3]$ (the domain of existence of $f$ and $g$) gives the well-known anarchist logo

Anarchy

As mathematicians, we can take this a step further and define an Anarchist curve, by finding the implicit form of the plot of each of the function, and then bringing them together.

In this case, $f,g$ together define the circle, with equation

$${(x-2)}^2+{(y-2)}^2=1$$

or rather (fully implicit):

$${(x-2)}^2+{(y-2)}^2-1=0.$$

The three functions $h,i,j$ describe the ‘A’ shape. We first rewrite $j$ in a nice form as

$$j\left(x\right)=x/5+17/10,$$

and then write the implicit equation for each of them, multiplying the one for $j$ by $10$ to get rid of the fractions:

$$\begin{array}{rcc}h& :& y-3x+3=0\\ i& :& y+3x-9=0\\ j& :& 10y-2x-17=0\end{array}$$

We can now multiply all the left hands together, obtaining:

$$(y-3x+3)(y+3x-9)(10y-2x-17)=0$$

which is the equation for the ‘A’.

If we then multiply this for the left-hand side of the implicit equation for the circle, we have the Anarchist curve

$$({(x-2)}^2+{(y-2)}^2-1)(y-3x+3)(y+3x-9)(10y-2x-17)=0$$

(which, for the record, is currently missing from the list of known curves in the Wolfram Alpha database.)

(There's a few more we could draw similarly, but that's for another time.)

Today's date, March 14th, is considered Pi Day, since written in the North American (and a few other places') convention of putting the month before the day, 3/14 can be read as the three most significant digit of

$$\pi =3.1415926535897932384626433832795...$$

I personally disagree with this choice, mainly for two reasons:

1. it depends on the decimal representation of $\pi$; in hexadecimal, we have $\pi =3.243F...$ so that the correct day would be March 2nd (hexadecimal 24 is decimal 36, and no month is that long);

2. it depends on the (IMO barbaric) convention of putting the month before the day in numerical date representations, which is far from being international (day/month/year being much more common) or standard (the ISO standard goes for year-month-day).

While the second point is debatable (I'm not aware of ISO standard recommendations for dates without years, which might be used as a resolution), the first point is easily fixed by going for a fractional representation of $\pi$ instead; and a well-known fractional approximation of $\pi$ is given by $\frac{22}{7}$, that dates as far back as Archimedes at least. Of course, 22/7 is not really possible in the month/day representation, but it makes perfect sense as July 22nd.

Mathematically speaking, July 22nd is preferable to March 14th as Pi Day also because the relative error introduced by approximating $\pi$ as $\frac{22}{7}$ is 0.04%, while the $3.14$ truncation has a relative error of 0.05%, so July 22nd is a better approximation to $\pi$ than March 14th.

The best Pi Day

Arguably, in the year 2015, the “American way” has another benefit: writing the year in the short (two-digit) form, we get an even better approximation of $\pi$ as $3.1415$, and by further appending the time we have an actual instant in which $\pi$ is presented exactly.

The argument fails miserably when taking into account that the time to be considered (9:26:53) would need to be padded by a 0 before “appending” it to the date, and there's always the decimal representation issue, and the fact that the time is sexagesimal …

If the year is to be considered, better dates can be chosen, with the following argument. Consider the continued fraction expansion of $\pi$:

$$[3,7,15,1,292,...]$$

Taking only the first three terms, corresponding to the date 3/7/15, we get $[3,7,15]=\frac{333}{106}$, which is accurate to 0.0026% (better than the 0.0029% of $3.1415$, even). So, March 7th 2015 (resp. July 3th 2015, depending on date notation) are both better approximations than March 14th (resp. June 22nd) for $\pi$ this year.

But as it happens, we can do better: if we take the first four terms of the continued fraction, we get $[3,7,15,1]=[3,7,16]=\frac{355}{113}$ which is an excellent approximation to $\pi$, with an error of less than one in ten million (a hint to this is the following huge 292 number).

The best date-fractional approximation of $\pi$ will happen next year, on March 7th in North America, Belize and whichever other country prefers month before day, and on July 3rd in the rest of the world.

Going beyond $\pi$

As a mathematician, one gets to think: we stop at $\pi$ day, aside from the obvious pi/pie pun? There are so many other interesting numbers to look into!

Tau Day and the $\tau$ manifesto

For example, there are people that believe that $\pi$ is wrong, and $\tau =2\pi$ should be considered the fundamental constant of the circle, and

$$\tau =6.283185307179586476925286766559...$$

The proposed Tau Day (in the manifesto linked above) is thus on June 28th, following the North American tradition. We obviously disagree, and would rather look for a fractional date choice. We thus go and look at the continued fraction representation of $\tau$,

$$[6,3,1,1,7,2,146,...]$$

And taking the first three terms we get $[6,3,1]=[6,4]=\frac{25}{4}$ which approximates $\tau$ to 0.5% (May 25th). Sadly, in this case the fractional approximation is worse than the truncation (0.05%), due to the fact that the next continued fraction term $[6,3,1,1]=[6,3,2]=\frac{44}{7}$, which approximates $\tau$ to 0.04%, is not a good date (although it was on 6/3/2). Is this a hint that $\pi$ is, in fact, better than $\tau$?

$e$, $\varphi$, what else?

Similarly, we can go looking for the best date for Napier's number $e$, for which we can choose $\frac{19}{7}$, accurate to 0.15% and dating to July 19th. For the golden ratio $\Phi$ the best candidate is $\frac{11}{9}$, with an error of 0.21% and dating to either September 11th (oops), or November 9th, depending on convention.

(It should be mentioned that the continued fraction representation of $e$ and $\varphi$ is not interesting enough to give us something useful for the year.)

For anybody interested in exploring rational approximating dates, I've also cooked up a quick'n'dirty Ruby script that does the finding for you.

Have fun.

Il problema

Si pone il seguente problema, derivato da questo articolo su G+: determinare la formula esplicita della successione di numeri naturali1 (ovvero della funzione $F:\mathbb{N}\to \mathbb{N}$) che soddisfa le due seguenti condizioni:

1. è strettamente crescente;
2. l'$i$-esimo elemento non appartenente all'immagine di $F$ è $F\left(F\left(i\right)\right)+1$.

Vediamo innanzi tutto di capire bene il secondo punto, cominciando con l'osservare che l'unica successione strettamente crescente che ha come immagine l'intero $\mathbb{N}$ è la successione $a\left(n\right)=n$. Per dimostrarlo, prendiamo una qualunque (altra) successione strettamente crescente $b$ e sia $k$ il primo indice per cui $b\left(k\right)\ne k$; risulterà anzi necessariamente2 $b\left(k\right)>k$, ed avremo quini $b\left(n\right)=n<k\forall n<k$ e $b\left(n\right)\ge b\left(k\right)>k\forall n\ge k$, da cui risulta che $k$ non è immagine di alcun numero naturale secondo $b$.

Ora, se ogni successione strettamente crescente non banale ha come immagine un sottoinsieme stretto di $\mathbb{N}$, possiamo considerare il complementare della sua immagine in $\mathbb{N}$, $H=\mathbb{N}\backslash F(\mathbb{N})$, che sarà un insieme non vuoto e quindi (in quanto sottoinsieme di $\mathbb{N}$) totalmente ordinato e numerabile; in soldoni, in tale complementare possiamo considerare il primo elemento (inteso come il minimo), il secondo elemento (il più piccolo elemento di $H$ maggiore del primo elemento), etc.

La seconda condizione su $F$ ci dice quindi che il primo elemento di $H$ è esattamente $F\left(F\left(1\right)\right)+1$, che il secondo elemento di $H$ è $F\left(F\left(2\right)\right)+1$, etc. Volendo, la cosa si può riformulare dicendo che $H$ è l'immagine della successione $h\left(n\right)=F\left(F\left(n\right)\right)+1$.

La domanda a questo punto è se effettivamente esiste (almeno) una successione $F$ che soddisfi i requisiti prescritti, e (in caso affermativo) se tale successione sia unica. Vi sono vari approcci per trovare risposta alla domanda, ed uno dei più immediati è sicuramente quello costruttivo: dimostriamo che $F$ esiste ed è unica determinando i valori di $F$ per ogni $n\in \mathbb{N}$ e mostrando come essi siano univocamente determinati.

Nel procedimento, ci serviremo di due ulteriori osservazioni. La prima è che in una successione strettamente crescente di numeri naturali $a$ si ha sempre3 $a\left(n\right)\ge n$; la seconda è che nel complementare $H$ del codominio di $F$ non possono esservi mai due interi consecutivi (infatti, se $k\in H$, avremo $k-1=F\left(F\left(n\right)\right)$ per un opportuno $n$, e quindi $k-1$, essendo nell'immagine di $F$, non starà in $H$).

Costruiamo dunque la nostra $F$, e vedremo come nel farlo costruiremo di necessità anche $H$ (ovvero, come visto, equivalentemente, la successione $h$ dei valori non assunti da $F$).

Abbiamo innanzi tutto che $F\left(1\right)=1$. Se così non fosse, infatti, sarebbe $1\in H$; di più, 1 sarebbe il primo elemento di $H$ (non possono infatti esservi in $H\subset \mathbb{N}$ numeri più piccoli), e quindi dovrebbe essere (per la seconda proprietà di $F$) $1=F\left(F\left(1\right)\right)+1$, da cui risulterebbe $0=F\left(F\left(1\right)\right)\ge F\left(1\right)\ge 1$ (dove le due disuguaglianze sono ottenute dalla precedente osservazione su valori e indici delle successioni crescenti).

Da $F\left(1\right)=1$ segue che $F\left(F\left(1\right)\right)=F\left(1\right)=1$ e quindi $h\left(1\right)=2$: il primo elemento di $H$ è 2, e quindi $F\left(2\right)\ge 3$ (per la crescenza di $F$ abbiamo $F\left(2\right)\ge 2$, ma $2\in H\Rightarrow F\left(2\right)\ne 2$).

Possiamo anzi dire che $F\left(2\right)=3$: se infatti fosse $F\left(2\right)>3$, dalla crescenza di $F$ seguirebbe che $F\left(n\right)>3\forall n>1$, che in congiunzione con il fatto che $F\left(1\right)=1<3$ ci direbbe che 3 non è immagine di alcun elemento, e quindi $3\in H$, ma ciò è impossibile, essendo $2\in H$ e non potendosi avere, come osservato, numeri consecutivi in $H$.

Quindi $F\left(2\right)=3$, da cui segue che $F\left(3\right)\ge 4$ (stretta crescenza di $F$), e quindi il secondo elemento di $H$ sarà $h\left(2\right)=F\left(F\left(2\right)\right)+1=F\left(3\right)+1\ge 5$ e quindi $h\left(n\right)\ge 5\forall n>1$, per cui $4\notin H$ e, per complementareità $4\in F(\mathbb{N})$; sarà quindi4 $F\left(3\right)=4$, da cui infine $h\left(2\right)=5$.

Così procedendo possiamo calcolare manualmente ciascun valore di $F$ e di $h$, ottenendo qualcosa come la seguente (l'idea, in soldoni, è di ‘riempire’ i valori di $F$ finché possibile, e quindi quelli di $h$ secondo la formula della seconda condizione):

Se questa tecnica costruttiva ci può servire come prova dell'esistenza (ed unicità) della $F$ (e della relativa $h$), non sembra dirci molto sulla sua forma chiusa.

Possiamo però studiare i primi termini delle due successioni $F$ ed $h$ e notare ad esempio che —almeno nella sequenza iniziale— esibiscono questo tipo di comportamento:

• per $F$, valori successivi differiscono tra loro di 1 o 2 (più spesso 2 che 1) unità;
• per $h$, invece, i ‘passi’ tra un valore e il successivo sono di 2 o 3 (più spesso 3 che 2) unità.

Le successioni di Beatty

Il comportamento in questione è tipico delle successioni di Beatty, una classe di successioni il cui termine generico ha la forma $\lfloor n\vartheta \rfloor$ per un fissato $\vartheta$ numero reale positivo irrazionale (il simbolo $\lfloor \cdot \rfloor$ rappresenta la funzione ‘parte intera’). Se $\vartheta >1$, la successione è strettamente crescente, e la differenza tra due termini consecutivi è sempre compresa tra $\lfloor \vartheta \rfloor$ e $\lfloor \vartheta \rfloor +1$.

Una interessante proprietà delle successioni di Beatty è che se $\alpha$ e $\beta$ sono irrazionali positivi tali che $\frac{1}{\alpha }+\frac{1}{\beta }=1$, allora le rispettive successioni di Beatty partizionano i numeri naturali (ovvero, sono complementari e la loro unione è data dall'intero insieme $\mathbb{N}$).

Vi sono forti indizi che le nostre successioni $F$ e $h$ siano successioni di Beatty complementari. Per risolvere il nostro problema basterebbe quindi trovare una coppia di numeri irrazionali $\alpha ,\beta$ che soddisfino $\frac{1}{\alpha }+\frac{1}{\beta }=1$ e che generino rispettivamente $F,h$ soddisfacenti la famosa seconda proprietà, scrivibile come $h\left(n\right)=F\left(F\left(n\right)\right)+1\forall n\in \mathbb{N}$.

Per trovare i generatori in questione cominciamo con l'osservare che, secondo quanto osservato finora, il generatore $\alpha$ di $F$ dovrebbe essere compreso tra 1 e 2, mentre il generatore $\beta$ di $h$ sarebbe compreso tra 2 e 3. Da $2<\beta <3$ e $\frac{1}{\alpha }+\frac{1}{\beta }=1$ seguirebbe anzi che $\frac{3}{2}<\alpha <2$ (da cui si potrebbe già intuire chi possa essere $\alpha$, essendovi un famosissimo numero irrazionale proprio in quell'intervallo —ma noi cercheremo di essere più formali).

Partiamo quindi dalla famosa seconda proprietà, che scritta in forma esplicita nel caso di $F,h$ successioni di Beatty ci dice che per ogni positivo $n$ risulta $\lfloor n\beta \rfloor =\lfloor \lfloor n\alpha \rfloor \alpha \rfloor +1$, ovvero $\lfloor n\beta \rfloor =\lfloor \lfloor n\alpha \rfloor \alpha +1\rfloor$, e quindi $-1<n\beta -(\lfloor n\alpha \rfloor \alpha +1)<1$, da cui ancora $0<n\beta -\lfloor n\alpha \rfloor \alpha <2$.

Essendo $\alpha$ irrazionale e positivo possiamo scrivere $(n-1)\alpha <\lfloor n\alpha \rfloor <n\alpha$, e quindi spezzare l'ultima catena di diseguaglianze in $n\beta -(n-1){\alpha }^2>n\beta -\lfloor n\alpha \rfloor \alpha >0$ e $n\beta -n{\alpha }^2<n\beta -\lfloor n\alpha \rfloor \alpha <2$. Dividendo per $n$ ovunque e portando un $\frac{{\alpha }^2}{n}$ a minorare nella prima diseguaglianza otteniamo infine la relazione $\frac{{\alpha }^2}{n}<\beta -{\alpha }^2<\frac{2}{n}$ vera per ogni $n$, da cui in definitiva $\beta -{\alpha }^2=0$ e quindi $\beta ={\alpha }^2$.

Abbiamo quindi che $\alpha ,\beta$ devono soddisfare $\frac{1}{\alpha }+\frac{1}{\beta }=1$ e $\beta ={\alpha }^2$. Sostituendo nella prima abbiamo $\frac{1}{\alpha }+\frac{1}{{\alpha }^2}=1$ o $\alpha +1={\alpha }^2$, la cui unica soluzione positiva è la famosa sezione aurea $\phi =\frac{1+\sqrt{5}}{2}$.

In definitiva, abbiamo dimostrato che se una coppia di successioni di Beatty complementari soddisfa le condizioni richieste, allora dovrebbe avere come generatori $\phi$ e ${\phi }^2$. Per concludere che le successioni di Beatty con questi generatori sono effettivamente quelle che cercavamo rimane ora da verificare che esse soddisfano i due criteri5.

La crescenza di $F$ è immediata conseguenza del fatto che il generatore è maggiore di 1, quindi rimane da provare la famosa seconda condizione, che vista la complementareità delle successioni possiamo esprimere così: dimostrare che per ogni $n$ risulta $\lfloor n{\phi }^2\rfloor =\lfloor \lfloor n\phi \rfloor \phi \rfloor +1$.

Osserviamo innanzi tutto che, posto $k\left(n\right)=\lfloor n\phi \rfloor -\lfloor (n-1)\phi \rfloor$, risulta $\lfloor n{\phi }^2\rfloor -\lfloor (n-1){\phi }^2\rfloor =k\left(n\right)+1$. Infatti, essendo ${\phi }^2=\phi +1$, possiamo scrivere $\lfloor n{\phi }^2\rfloor =\lfloor n\phi \rfloor +n$ e $\lfloor (n-1){\phi }^2\rfloor =\lfloor (n-1)\phi \rfloor +n-1$; sottraendo membro a membro otteniamo $\lfloor n{\phi }^2\rfloor -\lfloor (n-1){\phi }^2\rfloor =\lfloor n\phi \rfloor -\lfloor (n-1)\phi \rfloor +1=k\left(n\right)+1$.

Abbiamo quindi che $\lfloor n{\phi }^2\rfloor =\lfloor (n-1){\phi }^2\rfloor +k\left(n\right)+1$, e per provare la nostra tesi basta dimostrare che $\lfloor \lfloor n\phi \rfloor \phi \rfloor =\lfloor (n-1){\phi }^2\rfloor +k\left(n\right)$, eguaglianza che possiamo riscrivere $\lfloor \lfloor n\phi \rfloor (1+\frac{1}{\phi })\rfloor =\lfloor (n-1)(\phi +1)\rfloor +k\left(n\right)$, ovvero $\lfloor n\phi \rfloor +\lfloor \frac{\lfloor n\phi \rfloor }{\phi }\rfloor =\lfloor (n-1)\phi \rfloor +n-1+k\left(n\right)$. Essendo $\lfloor n\phi \rfloor =\lfloor (n-1)\phi \rfloor +k\left(n\right)$ la nostra tesi si semplifica nel dover dimostrare che $\lfloor \frac{\lfloor n\phi \rfloor }{\phi }\rfloor =n-1$ o equivalentemente6 $n-1\le \frac{\lfloor n\phi \rfloor }{\phi }<n$ che possiamo riscrivere $(n-1)\phi \le \lfloor n\phi \rfloor <n\phi$.

La diseguaglianza di destra è immediata essendo $\phi$ irrazionale, rimane quindi da provare che $(n-1)\phi \le \lfloor n\phi \rfloor$. Supponiamo per assurdo che sia vero il contrario, ovvero $(n-1)\phi >\lfloor n\phi \rfloor$, da cui seguirebbe $\lfloor (n-1)\phi \rfloor \ge \lfloor n\phi \rfloor$; ma $(n-1)\phi <n\phi$, quindi $\lfloor (n-1)\phi \rfloor \le \lfloor n\phi \rfloor$, e pertanto $\lfloor (n-1)\phi \rfloor =\lfloor n\phi \rfloor$, che implica $n\phi -(n-1)\phi <1$, ovvero $\phi <1$, assurdo7.

Abbiamo così completato la nostra dimostrazione e verificato che le successioni di Beatty con generatori $\phi$ e ${\phi }^2$ sono effettivamente quelle cercate.

Le successioni di Wythoff

Queste due successioni sono meglio note come la successione inferiore ($F$) e superiore ($h$) di Wythoff. Queste due successioni sono state scoperte appunto dall'eponimo matematico nello studiare un famoso problema di teoria dei giochi che prende vari nomi (problema di Wythoff, il gioco delle scatole dei biscotti, etc).

Il gioco ha la seguente forma: ci sono due scatole di biscotti, e due giocatori si alternano scegliendo quanti biscotti vogliono da una sola delle due scatole, oppure lo stesso numero di biscotti da entrambe le scatole. Vince il giocatore che prende l'ultimo biscotto.

È evidente che se una delle due scatole è vuota, o se ambo le scatole hanno lo stesso numero di biscotti, il primo giocatore vince. Il gioco si fa più interessante se entrambe le scatole sono piene ed il numero di biscotti non è equamente distribuito.

Ad esempio, se le scatole hanno rispettivamente 1 biscotto e 2 biscotti, è evidente che il secondo giocatore vincerà, qualunque sia la scelta fatta dal primo giocatore. Ovviamente, partendo da un'altra configurazione, un giocatore dovrebbe quindi cercare di arrivare alla distribuzione 1/2 per aver garantita la vittoria. La domanda è: quali altre configurazioni hanno tale proprietà? Ovvero, quali coppie di numeri $(a,b)$ sono tali che, qualunque sia la mossa del primo giocatore, il secondo si può garantire la vittoria?

Con un poco di calcoli si scopre che le coppie (ordinate, con $a<b$) che garantiscono la vittoria al giocatore che le raggiunge sono

e se la tabella vi ricorda qualcosa è perché i valori sono esattamente gli stessi visti nella precedente tabella: le coppie $(F\left(n\right),h\left(n\right))$ sono le configurazioni vincenti nel problema di Wythoff.

Una nota finale

Concludiamo questa nostra rapida escursione sulla questione osservando che $h\left(n\right)$ ha una forma ben più semplice della già vista $F\left(F\left(n\right)\right)+1$, e questa è $h\left(n\right)=F\left(n\right)+n$. La cosa, chiaramente visibile dai valori in tabella e facilmente dimostrabile8, ci permette di leggere le successioni di Wythoff in questo modo: ogni coppia $(F\left(n\right),h\left(n\right))$ è la coppia vincente in cui la differenza di contenuto tra le due scatole di biscotti è pari ad $n$.

Questo, combinato con la proprietà di partizionamento di $\mathbb{N}$ di cui godono le due successioni (ogni intero sta in una ed una sola delle successioni, e quindi anche in una ed una sola coppia) e con il fatto che il gioco è puramente ‘sottrattivo’ (da una configurazione all'altra si passa solo diminuendo uno o entrambi dei contenuti) è sufficiente a definire la strategia vincente, che viene lasciata come esercizio per il lettore.