Sancho Garcés III the Elder (born between 992 and 996) was king of Pamplona from 1004 until his death in 1035. His reign is considered to be the period of greatest hegemony of the kingdom of Pamplona (and, by extension, of Navarre) over the Hispano-Christian sphere in its entire history.
Among other possessions, some by inheritance, others by marriage, and some more by conquest, Sancho III reigned over the present-day lands of La Rioja (in fact, Nájera was during this period the habitual residence of the kings of Navarre, alternating with Pamplona for various historical circumstances). In particular, he held sway over the monastic writing offices of San Millán de la Cogolla and San Martín de Albelda where, in the 10th century, impressive manuscripts of great beauty and of unquestionable historical value were produced.
From San Millán it is worth mentioning Codex Emilianense 60, page 72 of which contains the so-called Emilian glosses, which are explanations, in a Romance language and grammatical structure, made by or for a monk who was no longer fluent in Latin; this codex is currently preserved in the Library of the Royal Academy of History in Madrid. From San Martín de Albelda we would highlight the Codex Vigilanus (or Codex Albeldense), written in 976 by a monk called Vigila, which contains beautiful miniatures in vivid colours; today, this codex is in the Library of the Royal Monastery of San Lorenzo del Escorial. We Riojanos are deeply grateful to the people of Madrid for keeping our thousand-year-old codices (those two and a few others), to prevent them from getting damaged.
The fact is that, from 26 January to 30 April 2006, the great exhibition “The Age of a Kingdom” was held in Pamplona, commemorating (a couple of years late) the thousandth anniversary of the coronation of Sancho Garcés III el Mayor, with an impressive display of historical pieces and manuscripts of great value. Among them, the Codex Vigilanus, which is very rarely loaned for exhibitions.
To say that this codex is precious for its illustrations is an understatement. But for mathematicians it has an even greater appeal, as it shows the nine digits (there is no zero) of our current numbering system and alludes to their positional value:
And also with regard to the figures of arithmetic, it is necessary to know that the Indians possess a very subtle intelligence and that the other concepts yield to them as far as arithmetic, geometry and other liberal disciplines are concerned. This is best brought out in the nine figures through which they express each degree of no matter what level. This is the form:
Not only is it the first time that Indo-Arabic numerals appear in the Christian West – a system that would not become widespread until the 13th century and would continue to struggle with the use of other methods until the 15th century – but it is possibly the oldest document in the world in which all nine digits are represented; more details can be found in [7] and [1].
That same year, a few months later, the International Congress of Mathematicians (ICM 2006) was to be held in Madrid, which, like the Olympics, is organised once every four years (it was inaugurated by King Juan Carlos and attended by some four thousand mathematicians from over 100 countries). One of the cultural activities accompanying the scientific activities was the exhibition “Life of Numbers” at the National Library (see [1]), and the Codex Vigilanus was to be one of the works on display.
Taking advantage of a meeting of the Executive Committee of the ICM 2006 in Castro Urdiales, I, Guillermo Curbera and Antonio Durán – who were involved in the organisation of the ICM – went to Pamplona to see the Codex Vigilanus on display there, and then spent the night in San Sebastián. After the spiritual enjoyment of the Pamplona exhibition, we proceeded to San Sebastian for a more mundane enjoyment: dinner at a temple of gastronomy, Juan Mari Arzak’s restaurant.
A tasting menu with many small dishes, each one tastier than the next and, except for one option between two courses, with no choice. A couple of times, someone from the kitchen – Arzak himself – came to greet us and ask how the food was. On one of these occasions, the following conversation arose: “We liked everything very much, but a doubt has arisen. We imagined that, at the beginning of the meal, you would have told us that we could repeat a course, just one, but that we had to say which one right after eating it, we couldn’t order a previous one. And our problem is, when do we say we want to repeat a dish if we don’t know whether we will like the subsequent ones more or less?”
I guess our host didn’t realise the depth of the problem – it’s not easy for someone who is not used to the subtleties that are indeed used in mathematics – and it was difficult to go on from there, debating strategies. But, as an alternative solution, he offered us that, since when we had to choose between two dishes we had only eaten one, they would bring us the other one as well. Magnificent!
That was that. In the following years, from time to time we would comment on the anecdote, but the truth is that we never thought of giving the problem a precise mathematical approach and studying it in depth.
Some time later, at another mathematics congress, a colleague – José María Grau – told me that he was working on variants and generalisations of the secretary’s problem (see, for example, [3]). What is that? I said to him. And he explained it to me: a company manager wants to hire a secretary, and to do so he interviews candidates one after the other; but he can only hire each one just after interviewing her, he cannot interview them all beforehand and decide afterwards (after the interview, each candidate leaves and does not come back).
“Oh, come on, it’s the same story as the problem of repeating a course at Arzak! The fact is that the problem we had set ourselves is a well-studied problem of decision-making and optimal stopping, on which, moreover, mathematical research is still being carried out. It is usually explained with the example of the secretary, but it also has more technical names.
It is clear that, nowadays, presenting the problem in terms of a manager who wants to hire a secretary is not politically attractive, and the adjectives that can be used to describe the problem in this way may not be pleasant (let alone with other names it sometimes receives, such as the problem of the sultan’s daughters or the demanding suitor). Fortunately, I don’t think anyone will be offended by the problem of repeating a dish at Arzak. If the reader is a vegan, he or she can imagine that none of the dishes have animal ingredients, of course.
Finally, we will briefly explain how to solve the problem with the usual approach, which requires us to know beforehand how many courses we are going to eat during the meal. We also assume that, depending on what we like, each dish has an unambiguous “gastronomic value”, and all of them are different, so we could put the values in order. We eat the dishes one after the other (of course, the value of the dish and its order in the menu have no correlation). We discover the value of the dish when we eat it and our goal is to choose the dish with the highest value. If we don’t manage to do that, we don’t care if we have chosen the second, in terms of value, or the last (in reality, they are all delicious, we can console ourselves).
Let’s start by analysing the case of three courses: olives, aubergines and cocochas (they are brought to us in that order), and whose gastronomic values (how much we like a dish) we denote by \(A\), \(B\) and \(C\) (three different real numbers). If we were to choose at random, we would have a 1/3 chance of choosing the dish with the highest value, which is what we want to achieve. We are going to see a strategy that will allow us to choose the best dish with probability 1/2.
After receiving the plate of olives, we rule out repeating it. When the aubergines are brought to us, if we like them better than the olives, we decide to repeat the aubergines; if we like them less, we wait for the cocochas, and we are obliged to repeat the cocochas. According to their gastronomic value, the three dishes can be ordered in the following ways: (i) \(A > B > C\), (ii) \(A > C > B\), (iii) \(B > A > C\), (iv) \(B > C > A\), (v) \(C > A > B\), (iv) \(C > B > A\). It is easy to check that, with the strategy described above, we will have managed to repeat from the best plate in cases (iii), (iv) and (v).
This strategy can be applied to any number of \(n\) courses and, although we will not always achieve a 50% success rate, we can obtain a surprisingly high percentage (greater than 1/3 regardless of the number of courses), much higher than the success we would obtain with a random choice, which would be \(1/n\).
In general, if the number of dishes is \(n\), we taste the first \(k\) dishes and discard their possible repetition, but note the gastronomic value of those \(k\) dishes. We then continue eating dishes and choose the first one that has a higher value than the first \(k\) courses. If none of them has a higher value, we will have to repeat the last dish, of course.
The important thing is to know how to choose the right \(k\) depending on the number of \(n\) courses. Let’s analyse it.
For an arbitrary \(n \ge 3\), and with \(0 < k < n\) (it is not worth worrying about the cases \(k=0\) or \(k=n\)), the probability of choosing the best plate with this strategy is
\begin{align*}
P_n(k) &= \sum_{i=1}^n P(\text{choose course $i$} \cap \text{course $i$ is the best one}) \\
&= \sum_{i=1}^n P(\text{choose course $i$} \mid \text{course $i$ is the best one})
\cdot P(\text{course $i$ is the best one}) \\
&= \sum_{i=1}^k 0 \cdot \frac{1}{n} +
\sum_{i=k+1}^n \bigg(
\begin{matrix}
\text{the best of the first $i-1$ courses}\\
\text{is in the first $k$ courses}
\end{matrix}
\,\bigg|\, \text{course $i$ is the best one} \bigg) \cdot \frac{1}{n} \\
&= \sum_{i=k+1}^n \frac{k}{i-1} \cdot \frac{1}{n} = \frac{k}{n} \sum_{i=k+1}^n \frac{1}{i-1}
\end{align*}
The goal now is to identify the \(k\) such that \(P_n(k)\) is as large as possible. This \(k\) is said to be the optimal \(k\); and the value of \(P_n(k)\) is the probability of success (choosing the best course) following this strategy.
With the help of a computer it is easy to check that, for the first values of \(n\), we have the following:
| Number of courses n | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Optimal k | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 |
| Success with this strategy | 50% | 45.8% | 43.3% | 42.8% | 41.4% | 40.6% | 40.6% | 39.9% |
| Success without strategy | 33.3% | 25% | 20% | 16.5% | 14.3% | 12.5% | 11.1% | 10% |
In general, how to find the optimal \(k\) or, at least, how to estimate it for large \(n\)?
Note that, if we split the interval \([0,1]\) into \(n\) pieces,
$$
P_n(k) = \frac{k}{n} \sum_{i=k+1}^n \frac{1}{i-1}
$$
are the Riemann sums of the integral
$$
P(x) = x \int_{x}^1 \frac{1}{t}\,dt = -x \log(x), \qquad x \in [0,1],
$$
therefore, for a large \(n\), \(P_n(k) \sim P(k/n)\).
Since \(P'(x) = -1 – \log(x)\), the maximum of \(P(x)\) is at \(x=e^{-1}\), and is \(P(e^{-1}) = e^{-1}\). Thus, for large \(n\), the optimal \(k\) will be the one that makes \(k/n \sim e^{-1}\) (i.e., \(k \sim n/e\)). In turn, since \(P(e^{-1}) = e^{-1} \sim 0.367879\), the probability of success of the strategy choosing the optimal \(k\) will be approximately \(36.8\%\). In fact, it can be seen that, with the optimal strategy, the probability of hitting the best plate is always greater than \(e^{-1}\).
We have just seen that the optimal \(k\) should be approximately \(n/e\), but there is no simple exact formula to express it as a function of \(n\). Here we will content ourselves with commenting on the relation with the continued fraction of \(e^{-1}\), which is
$$
e^{-1} = (0, 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1,\dots),
$$
and whose first convergents are
$$
0, \frac{1}{2}, \frac{1}{3}, \frac{3}{8}, \frac{4}{11}, \frac{7}{19}, \frac{32}{87}, \frac{39}{106},
\frac{71}{193}, \frac{465}{1264}, \frac{536}{1457}, \frac{1001}{2721}, \frac{8544}{23225};
$$
Well, as far as is known, these convergent \(k/n\) always correspond to \((k,n)\) pairs where \(k\) is the optimal value with \(n\) plates, but it is not proved that this is always true.
More details can be found in [4, section 13.13], [5, chapter 5] and [6, problem 47], in particular the relation of this problem to the Euler-Mascheroni constant \(\gamma\) and to the Lambert function \(W\). It is also worth mentioning that, in the On-Line Encyclopedia of Integer Sequences, the sequence of optimal \(k\) is https://oeis.org/A054404.
To conclude, let us briefly comment on the origins of this problem; a much more complete history can be found in [2]. Apparently, the first one who came up with it was Merrill M. Flood in 1949, and he reported it in several mathematicians’ conferences, so it started to be noticed. But it was first published in February 1960 in Martin Gardner’s Mathematical Games section in Scientific American (talking about ballots with positive numbers written on one side). Actually, quite similar problems had already been posed by Arthur Cayley in 1875 and Johannes Kepler in 1613 (the latter, with the real aim of choosing a new wife after being widowed in 1611).
References
[1] A. J. Durán, Vida de los Números, T Ediciones, 2006.
[2] T. S. Ferguson, Who solved the secretary problem?, Statist. Sci. 4 (1989), no. 3, 282-289.
[3] J. M. Grau, A new look at the returning secretary problem, J. Comb. Optim. 37 (2019), no. 4, 1216-1236.
[4] J. Havil, Gamma: Exploring Euler’s Constant, Princeton University Press, Princeton, NJ, 2003.
[5] R. Honsberger, Mathematical Plums, Math. Assoc. Amer., Washington, DC, 1979.
[6] F. Mosteller, Fifty Challenging Problems in Probability with Solutions, Dover, New York, DC, 1987.
[7] O. Pekonen, Gerberto de Aurillac: Matemático y Papa, La Gaceta de la RSME 4 (2001), no. 2, 399-408.
En Arzak jamás pediría un sumatorio, y mucho menos una integral. Eso sí, no me importaría ir con mi secretaria si la tuviera.