The product logarithm

Note: this article makes use of MathML, the standard XML markup for math formulas. Sadly, this is not properly supported on some allegedly ‘modern’ and ‘feature-rich’ browsers. If the formulas don't make sense in your browser, consider reporting the issue to the respective developers and/or switching to a standard-compliant browser.

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

$xex=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:

$x2ekx=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(y)⇔y=xex.$

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

$x=ln(y)⇔y=ex$

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(x)ef(x)=c$

$f(x)=W(c)$

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:

$x2ekx=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):

$xek2x=±c.$

Now we can balance the constants:

$k2xek2x=±k2c$

and apply the definition of $W$ to get

$k2x=W(±k2c)$

and finally

$x=2kW(±k2c).$

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=2kW0(k2c),$

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.)

1. this is actually more or less how it went. ↩

6cm per flag

Note: this article makes use of MathML, the standard XML markup for math formulas. Sadly, this is not properly supported on some allegedly ‘modern’ and ‘feature-rich’ browsers. If the formulas don't make sense in your browser, consider reporting the issue to the respective developers and/or switching to a standard-compliant browser.

## 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×20$ rectangle (with sides of length $1.14$m and $1.2$m respectively), or a $20×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×7$ square with a hole in the center. My son has a $32$-cards game that can be laid out as a $6×6$ square with missing corners.

In fact, the $68$-cards game that spurred these consideration is a bit annoying because $68=8×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×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×19-1=360$, but this would require removing $10$ nations from the “uncontroversial” list;

the next one would be $21×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×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×21-1-4=436$ would require $218$ states: we'd only need to find $12$ more than the ones listed by Wikipedia.

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

As it turns out, $380$ isn't even that bad: since $19×19-1+4×5=361-1+20=380$, a decent tiling can be found with a $19×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×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×2=516$ cards. What would be a good pattern? We have $516=22×22+32=22×22+4×8$ which actually lends itself to a decent layout: a $22×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.

1. anybody familiar with TEX would recognize $1.44$ as “magnification step 2”, per Knuth's recommendation of scaling sizes by a geometric progression of ratio $1.2$. ↩

How far can you see?

Note: this article makes use of MathML, the standard XML markup for math formulas. Sadly, this is not properly supported on some allegedly ‘modern’ and ‘feature-rich’ browsers. If the formulas don't make sense in your browser, consider reporting the issue to the respective developers and/or switching to a standard-compliant browser.

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(1cosα-1)$

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

$hr=1cosα-1$

add $1$ on both sides:

$hr+1=1cosα$

and take the reciprocals, swapping the two sides:

$cosα=1hr+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$

$α=arccos(1hr+1)$

and from this get

$d=rα=rarccos(1hr+1).$

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:

$1hr+1=1-(hr)+(hr)2-(hr)3+...$

assuming $h.)

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

$-11-x2$

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

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

$arccos(1hr+1)=arcsec(hr+1),$

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

$1xx2-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α=1hr+1,$

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

$1-α22=1hr+1$

or

$α22=1-1hr+1=hrhr+1=hh+r$

which gives us a much more approachable

$α2=2hh+r$

and finally, with an ugly square root,

$α=2hh+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):

$α=21+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}}$:

$α=2(p-(12)p3+(38)p5-(516)p7+⋯).$

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=2{q}^{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α=r21+q$

or can we do something more interesting?

(Aside for local manipulations, such as:

$d=r2hh+r$

of course.)

## Another rollback

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

$1-α22=1hr+1$

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

$1-hr+(hr)2-(hr)3+⋯$

so that our equation for $\alpha$ becomes:

$α22=hr-(hr)2+⋯$

and truncating:

$α22=hr(1-hr),$

but also

$α22=(hr)2(rh-1).$

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

$α22=1q(1-1q)=q-1q2$

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

$d=rα=r2(q-1)q=h2(q-1)=h2r-hh$

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=2hr-h2h$

(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(α)tan(α2).$

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

$h=r2t1-t2t=r2t21-t2$

and let's solve for $t$:

$h(1-t2)=2rt2$

$(2r+h)t2=h$

$t2=h2r+h.$

We can go for a direct solution now, with

$α2=arctan(h2r+h).$

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:

$α2=h2r+h,$

or

$α=2h2r+h,$

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

$α2=4h2r+h,$

or finally

$α=2h2r+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=2rh2r+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(α2)=tanα1+1+tan2α$

which would give us

$h=rtan2α1+1+tan2α$

that we can manipulate to

$1+1+tan2α=rtan2αh$

$1+tan2α=rtan2αh-1$

$1+tan2α=(rtan2αh-1)2$

$h2+h2tan2α=(rtan2α-h)2$

$h2+h2tan2α=r2tan4α-2hrtan2α+h2$

$r2tan4α-(h2+2hr)tan2α=0$

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

$tan2α=h2+2hrr2.$

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:

$α=h2+2hrr$

and for the distance that we're interested in:

$d=rα=h2+2hr=h1+2rh=h1+2q,$

with an amazing similarity to the $h\sqrt{2\left(q-1\right)}$ 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(1hr+1)=rarccos(rh+r)=rarccos(q1+q).$

And several possible approximations:

$d=r2hh+r$

$d=h2(q-1)$

$d=2hr-h2h$

$d=2rh2r+h$

$d=h1+2q$

$d=h1+2rh$

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?

Formula Result for $h=r$ i.e. $q=1$ Quality
$d=r2hh+r$ $d=r$ Not that bad
$d=2rh2r+h$ $d=23r≅1.15⋅r$ Could be better
$d=h1+2q$ $d=3r≅1.73⋅r$ Losing it …
$d=h2(q-1)$ $d=0$ Oh, come on!

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

$d2-d1=rarccos(q1q2(1+q1)(1+q2)+(1-(q11+q1)2)(1-(q21+q2)2))$

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

$d2-d1=rarccos(q1q2(1+q1)(1+q2)+1+2q1(1+q1)21+2q2(1+q2)2)$

or possibly even

$d2-d1=rarccos(q1q2+(1+2q1)(1+2q2)(1+q1)(1+q2)).$

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(hr+1)$

and the arc secant derivative for positive arguments, we get

$∂d∂h=1(hr+1)(hr+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

$∂d∂h=r2(h+r)(h+r)2-r2$

and finally

$∂d∂h=r2(h+r)h2+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

$∂d∂h=r2(h+r)h1+2q$

or even

$∂d∂h=q1+qq1+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):

$∂d∂h=q2(1-54q+4332q2-177128q3+⋯)$

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.)

1. we're picking the distance along the geodetic because we're looking at this issue as the inverse to the previous problem, but we could also look at this in a slightly different manner, i.e. considering the distance «as the crow flies»: this is in fact different, since we'd be talking about the $HS$ distance instead of the $PS$ arc.

Curiously, the formula for the crow's flight interpretation is actually simpler, since we're looking at a leg of the right triangle with hypothenuse $r+h$ and other leg $r$: the crow's flight is then $\sqrt{{\left(r+h\right)}^{2}-{r}^{2}}=\sqrt{{h}^{2}+2hr}=h\sqrt{1+2q}$, which is, in fact, one of the approximations we'll find for $d$. ↩  ↩

How high do you have to go?

Note: this article makes use of MathML, the standard XML markup for math formulas. Sadly, this is not properly supported on some allegedly ‘modern’ and ‘feature-rich’ browsers. If the formulas don't make sense in your browser, consider reporting the issue to the respective developers and/or switching to a standard-compliant browser.

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(1cosα-1)$

or

$h=r1-cosαcosα.$

## 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α221-α22$

or

$h=rα22-α2$

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

$h=rd22r2-d2.$

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=r2(rd)2-1.$

## A different formula

Let's go back to

$h=r(1cosα-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(1+t21-t2-1)$

or

$h=r1+t2-1+t21-t2$

simplifying to

$h=r2t21-t2$

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

$h=2r1t2-1$

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

$h=2r4(rd)2-1=r2(rd)2-12$

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α.$

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

$exsecα=tanαtan(α2).$

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

$α22+5α424+61α6720+⋯$

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=r2(dr)2=d22r$

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(12(dr)2+524(dr)4)=d22r(1+512(dr)2).$

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

$h=r2(1q2+512q4)=r2q2(1+56⋅2q2).$

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(12(dr)2+524(dr)4+61720(dr)6)$

and expressing this in terms of $q$:

$h=r2(1q2+512q4+61360q6)=r2q2(1+16⋅2q2(5+6115⋅2q2)).$

## 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=r2q2.$

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

$h=rs(1+56s),$

and if we want to push it further

$h=rs(1+16s(5+6115s)).$

(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.)

The anarchist curve

Note: this article makes use of MathML, the standard XML markup for math formulas. Sadly, this is not properly supported on some allegedly ‘modern’ and ‘feature-rich’ browsers. If the formulas don't make sense in your browser, consider reporting the issue to the respective developers and/or switching to a standard-compliant browser.

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:

$f(x) = 2+ -(x-2)2 + 1 g(x) = 2- -(x-2)2 + 1 h(x) = 3x-3 i(x) = -3x+9 j(x) = 0,2x+1,7$

Plotting the five functions with $x\in \left[1,3\right]$ (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(x)=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:

$h : y-3x+3 =0 i : y+3x-9 =0 j : 10y-2x -17 =0$

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.)

Pi Day

Note: this article makes use of MathML, the standard XML markup for math formulas. Sadly, this is not properly supported on some allegedly ‘modern’ and ‘feature-rich’ browsers. If the formulas don't make sense in your browser, consider reporting the issue to the respective developers and/or switching to a standard-compliant browser.

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$:

$\left[3,7,15,1,292,...\right]$

Side note: the afore­men­tio­ned $\frac{22}{7}$ is exactly the continued fraction $\left[3,7\right]$.

Taking only the first three terms, corresponding to the date 3/7/15, we get $\left[3,7,15\right]=\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 $\left[3,7,15,1\right]=\left[3,7,16\right]=\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$,

$\left[6,3,1,1,7,2,146,...\right]$

And taking the first three terms we get $\left[6,3,1\right]=\left[6,4\right]=\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 $\left[6,3,1,1\right]=\left[6,3,2\right]=\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.

I biscotti di Wythoff

## Il problema

Note: questo articolo fa uso di MathML, lo standard XML per le formule matematiche. Purtroppo, questo non è supportato correttamente in alcuni browser sedicenti ‘moderni’ o ‘ricchi di funzionalità’. Se le formule non hanno senso nel tuo browser, segnala il problema agli sviluppatori (del browser), o passa ad un browser che supporti questi standard.

Si pone il seguente problema, derivato da questo articolo su G+: determinare la formula esplicita della successione di numeri naturali1 (ovvero della funzione $F:ℕ\to ℕ$) 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 $ℕ$ è 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 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 $ℕ$, possiamo considerare il complementare della sua immagine in $ℕ$, $H=ℕ\F\left(ℕ\right)$, che sarà un insieme non vuoto e quindi (in quanto sottoinsieme di $ℕ$) 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 ℕ$ 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 ℕ$ 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⇒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\left(ℕ\right)$; 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):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
F 1 3 4 6 8 9 11 12 14 16 17 19 21 22 24
h 2 5 7 10 13 15 18 20 23 26 28 31 34 36 39

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 $⌊n\vartheta ⌋$ per un fissato $\vartheta$ numero reale positivo irrazionale (il simbolo $⌊\cdot ⌋$ rappresenta la funzione ‘parte intera’). Se $\vartheta >1$, la successione è strettamente crescente, e la differenza tra due termini consecutivi è sempre compresa tra $⌊\vartheta ⌋$ e $⌊\vartheta ⌋+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 $ℕ$).

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 ℕ$.

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 $⌊n\beta ⌋=⌊⌊n\alpha ⌋\alpha ⌋+1$, ovvero $⌊n\beta ⌋=⌊⌊n\alpha ⌋\alpha +1⌋$, e quindi $-1, da cui ancora $0.

Essendo $\alpha$ irrazionale e positivo possiamo scrivere $\left(n-1\right)\alpha <⌊n\alpha ⌋, e quindi spezzare l'ultima catena di diseguaglianze in $n\beta -\left(n-1\right){\alpha }^{2}>n\beta -⌊n\alpha ⌋\alpha >0$ e $n\beta -n{\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 $⌊n{\phi }^{2}⌋=⌊⌊n\phi ⌋\phi ⌋+1$.

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

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

La diseguaglianza di destra è immediata essendo $\phi$ irrazionale, rimane quindi da provare che $\left(n-1\right)\phi \le ⌊n\phi ⌋$. Supponiamo per assurdo che sia vero il contrario, ovvero $\left(n-1\right)\phi >⌊n\phi ⌋$, da cui seguirebbe $⌊\left(n-1\right)\phi ⌋\ge ⌊n\phi ⌋$; ma $\left(n-1\right)\phi , quindi $⌊\left(n-1\right)\phi ⌋\le ⌊n\phi ⌋$, e pertanto $⌊\left(n-1\right)\phi ⌋=⌊n\phi ⌋$, che implica $n\phi -\left(n-1\right)\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 $\left(a,b\right)$ 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) che garantiscono la vittoria al giocatore che le raggiunge sono

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a 1 3 4 6 8 9 11 12 14 16 17 19 21 22 24
b 2 5 7 10 13 15 18 20 23 26 28 31 34 36 39

e se la tabella vi ricorda qualcosa è perché i valori sono esattamente gli stessi visti nella precedente tabella: le coppie $\left(F\left(n\right),h\left(n\right)\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 $\left(F\left(n\right),h\left(n\right)\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 $ℕ$ 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.

1. si intende qui l'insieme dei numeri interi strettamente positivi. ↩  ↩

2. l'affermazione è ovvia nel caso $k=1$, poiché non vi sono numeri naturali1 minori di 1; se invece $k>1$, posto $l=b\left(k\right)$ e supponiamo per assurdo $l: essendo $b\left(n\right)=n\forall n per la scelta di $k$, avremmo, $b\left(k\right)=l=b\left(l\right)$, e quindi $b\left(l\right)=b\left(k\right)$ con $l, che viola la stretta crescenza di $b$. ↩

3. si dimostra ad esempio per induzione. Come base induttiva abbiamo che $a\left(1\right)\in ℕ⇒a\left(1\right)\ge 1$. Supponiamo ora che $a\left(n\right)\ge n$ e dimostriamo che da questo segue $a\left(n+1\right)\ge n+1$: per la stretta crescenza della successione abbiamo $a\left(n+1\right)>a\left(n\right)\ge n$, ovvero $a\left(n+1\right)>n$, e non essendovi numeri naturali tra $n$ ed $n+1$ questo equivale ad $a\left(n+1\right)\ge n+1$. ↩

4. se fosse $F\left(3\right)>4$, per la crescenza di $F$ si avrebbe $F\left(n\right)>4\forall n>3$, da cui, sapendo che $F\left(1\right)<4$ ed $F\left(2\right)<4$, seguirebbe che $4\notin F\left(ℕ\right)$. ↩

5. tale verifica è necessaria perché l'ipotesi da noi fatta (ovvero che $F$ ed $h$ siano successioni di Beatty complementari) potrebbe condurre ad un assurdo, da cui seguirebbe che in realtà esse non sono successioni di Beatty. ↩

6. si ha $⌊x⌋=m$ se e solo se $m\le ⌊x⌋, da applicare nel nostro caso con $x=\frac{⌊n\phi ⌋}{\phi },m=n-1$ ↩

7. osserviamo che per un arbitrario numero reale positivo $\alpha$ la diseguaglianza $\left(n-1\right)\alpha \le ⌊n\alpha ⌋$ non è in genere verificata, come si vede prendendo ad esempio $\alpha =\frac{1}{K}$ per un fissato $K$ naturale ed osservando che per ogni $1 si ha $⌊n\alpha ⌋=⌊\frac{n}{K}⌋=0<\frac{n-1}{K}=\left(n-1\right)\alpha$; la diseguaglianza è però verificata per tutti i numeri reali $\alpha \ge 1$. ↩

8. essendo nota la forma esplicita delle due successioni, ci basta provare che $⌊n{\phi }^{2}⌋=⌊n\phi ⌋+n$; partiamo quindi dall'equazione che definisce la sezione aurea: da ${\phi }^{2}=\phi +1$ segue, per ogni $n$, $n{\phi }^{2}=n\left(\phi +1\right)$ e quindi anche $⌊n{\phi }^{2}⌋=⌊n\phi +n⌋$, o equivalentemente $⌊n{\phi }^{2}⌋=⌊n\phi ⌋+n$, ciò che volevamo dimostrare. ↩

Matematica aliena/1: numerali

Se è vero che la matematica è concettualmente un linguaggio ‘universale’, lo stesso non può dirsi dei sistemi di numerazione. Ad esempio, siamo ormai abituati a considerare ‘universale’ il sistema posizionale basato sulle cosiddette cifre arabe, ma abbiamo dimestichezza anche con il ben diverso sistema simbolico in uso nell'antica Roma. E questi sono solo due dei sistemi che sul nostro pianeta sono (o sono stati) usati.

Supponiamo di entrare in contatto con una civiltà aliena, magari ormai estinta, ma che ci abbia lasciato documenti ed iscrizioni su cui poterla studiare. Anche ammesso che, per la sua universalità, la loro matematica sia ‘isomorfa’ alla nostra, possiamo essere sicuri di riuscire a non dico leggere, ma almeno identificare la loro rappresentazione della stessa?

Propongo un esercizio di riscaldamento. Supponiamo di sapere che gli alieni scrivano, come noi, da sinistra verso destra e poi dall'alto verso il basso. Supponiamo anche di aver identificato gli otto simboli con cui vengono scritti i numeri, e che trascriveremo con le prime otto lettere dell'alfabeto latino: A B C D E F G H.

Supponiamo inoltre che nei documenti che ci sono pervenuti compaia un solo simbolo di operazione, che trascriveremo con ˆ. Supponiamo che nei frammenti arrivati fino a noi, gli esempi più semplici che si riescano a trovare siano questi:

• AA ˆ AA = BB
• AA ˆ BB = CC
• HA ˆ HA = HAB

Ovviamente, si trovano esempi più complicati, come CCFDAC ˆ FEEGHC = AADDBAF.

Siamo in grado di cominciare a interpretare i numeri (e capire di quale operazione si tratta) semplicemente da questo?

Il sistema numerico presentato è biiettivo in base 8, con alcune modifiche. Come nei sistemi di numerazione biiettiva, le otto cifre rappresentano i numeri da 1 a 8, e non si fa quindi uso dello zero. In aggiunta, gli alieni scrivono i numeri nella direzione di scrittura, partendo dalle cifre meno significative, e chiudendo con la cifra data dal numero modulo 7.

Vediamo alcune ragioni perché un siffatto sistema ha senso.

L'uso della base 8 invece che della base 10 è facilmente giustificabile, ad esempio, supponendo che gli alieni abbiano solo 8 dita invece delle nostre 10.

Scrivere le cifre meno significative prima di quelle più significative semplifica la scrittura in riga dei risultati delle operazioni (non è necessario sapere in anticipo quanto saranno lunghi e lasciare spazio a sufficienza).

L'uso della cifra supplementare facilita la determinazione di eventuali errori. Nel nostro usuale sistema numerale, questo punto si applicherebbe aggiungendo alla normale sequenza di cifre il valore modulo 9 dello stesso numero.

Il valore della cifra di controllo non è nemmeno difficile da calcolare, ricordando la buona vecchia ‘prova del nove’ che un tempo si insegnava alle elementari: basta sommare le cifre del numero, ripetutamente, fino ad ottenere una sola cifra. Volendo separare con una barra verticale il numero dalla cifra di controllo, scriveremmo 12|3 o 15|6, o 125678|2 (adottando, a parte la base, il sistema alieno, avremmo invece 213, 516, 8765212 rispettivamente).

L'unico inconveniente (come ai tempi della prova del 9) è che bisogna ricordarsi che 0 e 9, come cifre di controllo, sono equivalenti. È qui che interviene infine l'utilità del sistema biiettivo, che rende univoca la rappresentazione, mancando di una cifra per indicare lo 0.

Risolvere un quizzino della domenica (1)

Il .mau. propone per oggi un quizzino della domenica dal seguente testo:

In un articolo apparso il secolo scorso sul bollettino parrocchiale di Villar Perosa, si racconta che il senatore Giovanni Agnelli in persona premiò un contadino che aveva nove figli per una curiosa proprietà aritmetica. Tutti i figli erano infatti nati allo stesso numero di anni di distanza l'uno dal successivo; ma soprattutto la somma dei quadrati delle loro età in quell'anno era pari al quadrato dell'età del contadino. Quali erano queste età?

Vediamo di risolverlo.

## Ratio e definizioni

Note: questo articolo fa uso di MathML, lo standard XML per le formule matematiche. Purtroppo, questo non è supportato correttamente in alcuni browser sedicenti ‘moderni’ o ‘ricchi di funzionalità’. Se le formule non hanno senso nel tuo browser, segnala il problema agli sviluppatori (del browser), o passa ad un browser che supporti questi standard.

Sia $A$ l'età del figlio minore e sia $D$ la cadenza con cui sono nati i figli: avremo allora che il penultimo ha $A+D$ anni, e così via fino al maggiorenne, di età $B=A+8D$ anni. La somma dei quadrati di queste età, dopo un po' di semplice aritmetica, si può scrivere così:

$S=9{A}^{2}+72AD+204{D}^{2}$

ed il problema si riduce quindi a trovare $A,D,C$ interi tali che

${C}^{2}=9{A}^{2}+72AD+204{D}^{2}$

con alcune condizioni al contorno, del tipo $D>0$, $A>0$, $C>A+8D$ etc.

## Procedimento

In generale, trovare interi tali che loro combinazioni algebriche diano quadrati perfetti non è banale, ma nel nostro caso possiamo aiutarci osservando che l'espressione che vorremmo ridurre ad un quadrato perfetto è molto simile all'espansione del quadrato di una somma, il cui primo quadrato è $9{A}^{2}$, il doppio prodotto è ‘vicino’ a $72AD$ ed il secondo quadrato è ‘vicino’ a $204{D}^{2}$.

L'idea è quindi quella di trasformare questa espressione nel quadrato di una somma di interi, ‘trasformando’ opportunamente il secondo e il terzo addendo senza ovviamente alterare il valore numerico dell'espressione stessa.

A tal fine, osserviamo che 204 (il coefficiente numerico del secondo quadrato) non è un quadrato perfetto, ma è compreso tra $196={14}^{2}$ e $225={15}^{2}$: è quindi legittimo sperare che l'espressione si possa trasformare in un quadrato con uno di questi due coefficienti. A tal fine, calcoliamo:

${\left(3A+14D\right)}^{2}-S$

e

${\left(3A+15D\right)}^{2}-S,$

ottenendo rispettivamente

$4\left(3A-2D\right)D$

e

$3\left(6A+7D\right)D,$

termini che noi vogliamo siano nulli, nell'ambito sempre delle condizioni enunciate alla fine del precedente paragrafo. Questo comporta in particolare che il secondo caso non ammette soluzione, poiché annullarlo ci dà come condizioni o $D=0$ (impossibile) o $6A+7D=0$, che ammette soluzioni solo se $A$ e $D$ hanno segno opposto (o sono entrambi nulli), mentre noi vogliamo che sia $A$ che $D$ siano strettamente positivi.

Ne consegue che l'espressione da noi cercata è la prima, che si annulla per $3A=2D$. Sostituendo quindi ad esempio $A=\frac{2D}{3}$ nell'espressione per $S$ otteniamo

$S=256{D}^{2}$

e quindi $C=16D$.

Sappiamo anche che $D$ deve essere multiplo di 3, poiché altrimenti $A$ non sarebbe intero, ed abbiamo quindi almeno due soluzioni possibili:

• per $D=3$ si ha $A=2,B=26$ e $C=48$;
• per $D=6$ si ha $A=4,B=52$ e $C=72$;

e ci fermiamo qui perché per il successivo valore $D=9$ avremmo $C=144$ e non siamo più ai tempi dei matusalemmi. È probabile che come soluzione si debba in realtà prendere la prima, perché un contadino 72enne con un figlio di 4 anni è poco credibile, benché non impossibile.

## Postilla

Il testo del problema è stato emendato per rendere univoca la soluzione aggiungendo questa nota:

mentre la somma degli anni dei figli era uguale al triplo degli anni della moglie

e intendendo che la moglie del contadino sia anche la madre di tutti i suoi figli, questo porta la moglie ad avere un'età $M$ che soddisfi

$3M=9\left(A+4D\right)$

da cui, semplificando e introducendo le nostre condizioni su $A$ e $D$,

$M=3\left(A+4D\right)=14D$

che per $D=3,6$ ci restituisce $M=42,84$ rispettivamente; questo permette di scartare la soluzione $D=6$ essendo praticamente impossibile che una donna abbia un figlio ad 80 anni. È però interessante notare che con questa condizione la donna aveva 16 anni quando ha partorito il primo figlio.

Il problema dei portatori di pizza

Tre coppie decidono di prendere per cena pizza da asporto. Arrivati alla pizzeria, ordinano rispettivamente due margherite senza olio, una caprese e una bresaola, una caprese e una vulcano. Quando le pizze sono pronte, la commessa le fornisce impilate in ordine ignoto. Ciascuno dei tre cavalieri prende due delle pizze per distribuire equamente il carico durante il trasporto verso casa.

Supponendo che l'ordine in cui le pizze sono state distribuite sia perfettamente casuale, qual è la probabilità che ciascun cavaliere trasporti le due pizze ordinate dalla rispettiva coppia?

## Soluzione

Nel seguito, indicheremo con B la pizza Bresaola, con C la Caprese, con M la Margherita (senza olio) e con V la Vulcano. Il pizzaiolo fornisce le pizze in un ordine casuale (ad esempio MCCBMV), che per comodità i tre cavalieri prenderanno in ordine (nell'esempio, il primo prenderà MC, il secondo CB, il terzo MV).

La probabilità che i cavalieri portino il paio giusto di pizze è quindi il numero delle permutazioni che assegnano a ciascun cavaliere le pizze giuste diviso il numero totale di permutazioni (distinte) possibili.

Le permutazioni valide sono quattro, per le seguenti condizioni: il primo cavaliere deve prendere le margherite (una sola possibilità: MM), il secondo cavaliere deve prende la bresaola e una caprese (due possibilità: BC, CB), il terzo cavaliere prende la vulcano e una caprese (ancora due possibilità: VC, CV). Le permutazioni in questione possono anche essere enumerate per esteso:

• MM BC VC
• MM CB VC
• MM BC CV
• MM CB CV

Quante sono invece le permutazioni distinte possibili1? Se le pizze fossero tutte diverse, si avrebbero 6! = 720 permutazioni, ma poiché vi sono due margherite, e tutte le permutazioni in cui le due margherite si scambiano di posto sono equivalenti, il numero di permutazioni va dimezzato; analogamente per le capresi, ottenendo infine 720/4 = 180 permutazioni distinte.

La probabilità che ciascun cavaliere porti le pizze della propria coppia è quindi di 4/180, ovvero 2/90 o 1/45, il 2.(2)%.

{ Costruire un albero delle 180 combinazioni distinte. }

1. si ringrazia il proponente del gioco per aver anche determinato il modo più rapido per calcolare le permutazioni distinte. ↩

Lavorare per, lavorare con

Versione tl;dr (e conclusioni di tutto il discorso): lavorare per qualcuno e lavorare con qualcuno sono due tipi di relazioni indipendenti: si può quindi lavorare per qualcuno, ma non con loro; si può lavorare per qualcuno e con loro; si può lavorare con qualcuno, ma non per loro. Sono quindi due insiemi con intersezione non vuota.

Motivazione: una delle tipiche discussioni inutili che si fanno per passare tempo in palestra.

Note: questo articolo fa uso di MathML, lo standard XML per le formule matematiche. Purtroppo, questo non è supportato correttamente in alcuni browser sedicenti ‘moderni’ o ‘ricchi di funzionalità’. Se le formule non hanno senso nel tuo browser, segnala il problema agli sviluppatori (del browser), o passa ad un browser che supporti questi standard.

Per una comprensione più dettagliata del discorso, cominciamo con un breve ripasso di teoria degli insiemi (solo quello che serve).

Sia $X$ un insieme. Una relazione (binaria) tra gli elementi di $X$ è un sottoinsieme del prodotto cartesiano di $X$ con sé stesso. Se $R\subseteq X×X$ è una relazione ed $x,y\in X$, diremo che $x$ è in relazione con $y$ (secondo $R$) se $\left(x,y\right)\in R$, ed in tal caso scriveremo per semplicità $xRy$.

Su uno stesso insieme $X$ si possono definire più relazioni. Alcuni tipi di relazione sono particolarmente diffusi e/o importanti. Tra questi ricordiamo:

relazioni d'ordine

una relazione $R\subseteq X×X$ si dice d'ordine se essa gode delle proprietà riflessiva ($xRx$ per ogni $x\in X$), antisimmetrica (se $xRy$ e $yRx$ allora $x=y$) e transitiva (se $xRy$ e $yRz$ allora $xRz$); un esempio classico di relazione d'ordine è la relazione di minore o uguale definita sui numeri (naturali, razionali, reali);

relazioni d'ordine stretto

una relazione $R\subseteq X×X$ si dice d'ordine stretto se essa gode delle proprietà irriflessiva ($xRx$ per nessun $x\in X$), asimmetrica (se $xRy$ allora non può aversi $yRx$) e transitiva (se $xRy$ e $yRz$ allora $xRz$); un esempio classico di relazione d'ordine stretto è la relazione di minore definita sui numeri (naturali, razionali, reali);

relazioni di equivalenza

una relazione $R\subseteq X×X$ si dice di equivalenza se essa gode delle proprietà riflessiva ($xRx$ per ogni $x\in X$), simmetrica (se $xRy$ allora $yRx$) e transitiva (se $xRy$ e $yRz$ allora $xRz$); un esempio classico di relazione d'ordine è la relazione di similitudine definita sull'insieme dei triangoli del piano.

Veniamo ora alla nostra questione: prendiamo l'insieme $X$ delle persone che lavorano, e definiamo su questo insieme due relazioni.

La prima relazione, che indicheremo con $C$, è la relazione del ‘lavorare con’. Se $x,y$ sono persone ed $x$ lavora con $y$, scriveremo $xCy$. Questa relazione gode sicuramente della proprietà riflessiva (nel senso che ciascuno lavora con sé stesso) e di quella simmetrica (se uno lavoro con un altro, è anche vero che l'altro lavora con l'uno); se quando uno lavora con un altro e questo lavori con una terza persona è sempre vero che il primo lavori con il terzo, allora sarà anche vera la proprietà transitiva e quindi la relazione $C$ potrà essere considerata una relazione d'equivalenza.

La seconda relazione, che indicheremo con $P$, è la relazione del ‘lavorare per’. Se $x$ lavora per $y$, scriveremo $xPy$. A seconda se si ammette che si lavori per sé stessi o meno, la relazione $P$ è abbastanza ovviamente una relazione di ordine semplice o in senso stretto.

Siccome si ha $C,P\subseteq X×X$, possiamo calcolare l'intersezione delle due relazioni (ovvero lavorare per e con qualcuno) e questa sarà ancora una relazione tra gli elementi di $X$ ($C\cap P\subseteq X×X$). Se essa è vuota, non vuota, uguale alla diagonale (ovvero se ogni elemento è in relazione ‘per e con’ solo con sé stesso) o altro dipende ovviamente dalle relazioni $C$ e $P$.

Facciamo un esempio. Sia dato un insieme $X$ i cui elementi sono $a,b,c,d$ e supponiamo che le relazioni $C$ e $P$ siano così definite:

• $b$ lavora con $a$ e con $d$; considerando la simmetria e riflessività di $C$, avremo le relazioni $aCa,bCb,cCc,dCd,aCb,bCa,bCd,dCb$ (in questo caso stiamo supponendo che non valga la proprietà transitiva, ed in particolare che anche se $b$ lavora con $a$ e con $d$, $a$ non lavora con $d$)
• $a$ e $b$ lavorano per $c$, e $b$ lavora anche per $d$; senza considerare la riflessività per $P$, avremo $aPc$, $bPc$, $bPd$ (questa relazione $P$ è una relazione d'ordine in senso stretto)

In tal caso, la relazione lavorare per e con lega soltanto $b$ e $d$ essendo $\left(b,d\right)$ l'unico elemento dell'intersezione $C\cap P$ (relazioni $bCd$ e $bPd$)

Se nella relazione $P$ si avesse pure $bPa$, gli elementi di $C\cap P$ sarebbero $\left(b,d\right)$ e $\left(b,a\right)$.

Se invece in $P$ considerassimo anche la riflessività (cioè che ciascuno lavora per sé stesso), allora a lavorare per e con qualcuno saranno: ciascuno con sé stesso, $b$ per e con $d$: $\left(a,a\right),\left(b,b\right),\left(c,c\right),\left(d,d\right),\left(b,d\right)$.