El problema de repetir plato en Arzak

Sancho Garcés III el Mayor (nacido entre los años 992 y 996) fue rey de Pamplona desde 1004 hasta su muerte en 1035. Su reinado es considerado la etapa de mayor hegemonía del reino de Pamplona (y, por extensión, del de Navarra) sobre el ámbito hispano-cristiano en toda su historia.

Entre otras posesiones, unas por herencia, otras por matrimonio, y alguna más por conquista, Sancho III reinó sobre las actuales tierras riojanas (de hecho, Nájera fue durante esa época residencia habitual de los reyes de Navarra, alternándose con Pamplona por diversas circunstancias históricas). En particular, dominaba sobre los escritorios monásticos de San Millán de la Cogolla y de San Martín de Albelda donde, en el siglo X, se elaboraron impresionantes manuscritos de gran belleza y de indudable valor histórico.

De San Millán merece la pena mencionar el Códice Emilianense 60, en cuya página 72 se encuentran las denominadas glosas emilianenses, que son explicaciones, en un lenguaje y una estructura gramatical romance, hechas por o para algún monje que ya no dominaba el latín; actualmente, dicho códice se conserva en la Biblioteca de la Real Academia de la Historia en Madrid. De San Martín de Albelda destacaremos el Códice Vigilanus (o Códice Albeldense), escrito el año 976 por un monje denominado Vigila, y que contiene bellísimas miniaturas de vivos colores; hoy en día, este códice se encuentra en la Biblioteca del Real Monasterio de San Lorenzo del Escorial. Los riojanos estamos profundamente agradecidos a los madrileños por guardarnos nuestros códices milenarios (esos dos y unos cuantos más), para evitar que a nosotros se nos estropeen.

El caso es que, del 26 de enero al 30 de abril de 2006, se celebró en Pamplona la magna exposición «La edad de un Reyno», conmemorativa (con un par de años de retraso) del milenario de la coronación de Sancho Garcés III el Mayor, y que contaba con un impresionante despliegue de piezas y manuscritos históricos de gran valor. Entre ellos, el Códice Vigilanus, que muy raramente se presta para exposiciones.

Por sus ilustraciones, decir que dicho códice es precioso es quedarse muy corto. Pero para los matemáticos tiene un atractivo aún mayor, pues en él se muestran las nueve cifras (no está el cero) de nuestro actual sistema de numeración y se alude a su valor posicional:

Y también a propósito de las cifras de la aritmética, es necesario saber que los indios poseen una inteligencia muy sutil y que los restantes conceptos les ceden el paso en lo que concierne a la aritmética, la geometría y demás disciplinas liberales. Esto se pone de manifiesto de la mejor manera en las nueve figuras a través de las cuales expresan cada grado de no importa qué nivel. Esta es la forma:

No solo es la primera vez que en el occidente cristiano aparecen los números indoarábigos —sistema que no empezará a generalizarse hasta el siglo XIII y que mantendrá su pugna con el uso de otros métodos hasta el siglo XV— sino que, posiblemente, es el documento más antiguo del mundo en el que están representadas las nueve cifras; se pueden ver más detalles en [7] y [1].

Ese mismo año 2006, unos meses más tarde, iba a tener lugar en Madrid el Congreso Internacional de los Matemáticos (ICM 2006) que, como las olimpiadas, se organiza una vez cada cuatro años (fue inaugurado por el rey Juan Carlos y a él asistieron unos cuatro mil matemáticos de más de 100 países). Una de las actividades culturales que acompañaban a las propiamente científicas era la exposición «Vida de los Números» en la Biblioteca Nacional (véase [1]), y el Códice Vigilanus iba a ser una de las obras en ella expuestas.

Aprovechando una reunión del Comité Ejecutivo del ICM 2006 en Castro Urdiales, el que esto escribe, Guillermo Curbera y Antonio Durán —que estábamos involucrados en la organización del ICM— fuimos a Pamplona a ver el Códice Vigilanus allí expuesto, y posteriormente hicimos noche en San Sebastián. Tras el disfrute espiritual que supuso la exposición de Pamplona, procedimos en San Sebastián a un disfrute más mundano: cenar en un templo de la gastronomía, el restaurante de Juan Mari Arzak.

Un menú degustación con muchos platos pequeñitos a cuál más rico y, salvo en una opción entre dos platos, sin posibilidad de elegir. Un par de veces, alguien de la cocina —el propio Arzak— viene a saludarnos y a preguntar qué tal la comida. En una de estas ocasiones surgió la siguiente conversación: «Nos ha gustado todo muchísimo, pero nos ha surgido una duda. Nos hemos imaginado que, al principio de la comida, nos hubierais dicho que podíamos repetir un plato, uno solo, pero que teníamos que decir cuál justo después de comerlo, no podíamos pedir uno anterior. Y nuestro problema es ¿cuándo decir que queremos repetir plato si no sabemos si los posteriores nos van a gustar más o menos?»

Supongo que nuestro interlocutor no se dio cuenta de la profundidad del problema —no es fácil para alguien que no está acostumbrado a esas sutilezas que sí se usan en matemáticas—, y fue difícil continuar por ahí, debatiendo estrategias. Pero, como solución alternativa, nos ofreció que, como cuando había que elegir entre dos platos sólo habíamos comido uno, nos iban a traer también el otro. ¡Magnífico!

Ahí quedó la cosa. En los siguientes años, de vez en cuando comentábamos la anécdota, pero la verdad es que nunca pensamos en darle al problema un planteamiento matemático preciso y profundizar en su estudio.

Tiempo más tarde, en otro congreso de matemáticas, un colega —José María Grau— me comentó que estaba trabajando en variantes y generalizaciones del problema de la secretaria (véase, por ejemplo, [3]). «¿Qué es eso?», le dije yo. Y me lo explicó: un directivo de una empresa quiere contratar a una secretaria, y para ello va entrevistando candidatas una tras otra; pero, a cada una, solo puede contratarla justo después de entrevistarla, no se puede entrevistar previamente a todas y decidir después (tras la entrevista, cada candidata se va y no vuelve).

«¡Anda, es el mismo problema que el de repetir plato en Arzak!». El caso es que el problema que nos habíamos planteado es un problema de toma de decisiones y de parada óptima bien estudiado y sobre el que, además, se sigue haciendo investigación matemática. Se suele explicar con el ejemplo de la secretaria pero también tiene nombres más técnicos.

Está claro que, actualmente, plantear el problema en términos de un directivo que quiere contratar a una secretaria no es políticamente atractivo, y los adjetivos que puede recibir el que lo presente de esa forma pueden no ser agradables (y no digamos con otros de los nombres que recibe en ocasiones, como problema de las hijas del sultán o del pretendiente exigente). Afortunadamente, creo que nadie se sentirá ofendido por el problema de repetir plato en Arzak. Si el lector es vegano, se puede imaginar que ningún plato tiene ingredientes de procedencia animal, claro.

Para acabar, vamos a explicar someramente cómo solucionar el problema con su planteamiento habitual, que requiere saber previamente cuántos platos vamos a degustar a lo largo de la comida. Suponemos asimismo que, según lo que nos gusta, cada plato tiene un «valor gastronómico» sin ambigüedad, y todos ellos son distintos, con lo cual los valores los podríamos poner en orden. Los platos los vamos comiendo uno tras otro (por supuesto, el valor del plato y su orden en el menú no tienen ninguna correlación). El valor del plato lo descubrimos cuando lo comemos y nuestro objetivo es elegir el plato de más valor. Si no conseguimos eso, nos da igual haber elegido el segundo, en cuanto a valor, o el último (en realidad, todos están riquísimos, podemos consolarnos).

Comencemos analizando el caso de tres platos, aceitunas, berenjenas y cocochas (nos los traen en ese orden), y cuyos valores gastronómicos (lo que nos gusta un plato) los denotamos mediante \(A\), \(B\) y \(C\) (tres números reales distintos). Si eligiéramos al azar, tendríamos 1/3 de probabilidades de escoger el plato de mayor valor, que es lo que queremos conseguir. Vamos a ver una estrategia que nos va a permitir elegir el mejor plato con probabilidad 1/2.

Tras recibir el plato de aceitunas, descartamos repetirlo. Cuando nos traen las berenjenas, si nos gustan más que las aceitunas decidimos repetir berenjenas; si nos gustan menos, esperamos a las cocochas, y forzosamente estaremos obligados a repetir cocochas. Según su valor gastronómico, los tres platos pueden estar ordenados de las siguientes formas: (i) \(A > B > C\), (ii) \(A > C > B\), (iii) \(B > A > C\), (iv) \(B > C > A\), (v) \(C > A > B\), (iv) \(C > B > A\). Es fácil comprobar que, con la estrategia antes descrita, habremos conseguido repetir del mejor plato en los casos (iii), (iv) y (v).

Esta estrategia se puede aplicar a cualquier número de platos \(n\) y, aunque no se conseguirá siempre un éxito del 50%, sí que podemos obtener un porcentaje sorprendentemente alto (mayor de 1/3 independientemente del número de platos), mucho mayor que el éxito que obtendríamos con una elección al azar, que sería de \(1/n\).

En general, si el número de platos es \(n\), degustamos los \(k\) primeros y descartamos su posible repetición, pero anotamos el valor gastronómico de esos \(k\) platos. A continuación, seguimos comiendo platos y escogemos el primero que tenga un valor mayor que el de los \(k\) primeros. Si ninguno tiene más valor tendremos que repetir el último plato, claro.

Lo importante es saber elegir bien el \(k\) conveniente en función del número de platos \(n\). Vamos a analizarlo.

Para un \(n \ge 3\) arbitrario, y con \(0 < k < n\) (no merece la pena preocuparse de los casos \(k=0\) o \(k=n\)), la probabilidad de elegir el mejor plato con esa estrategia es

\begin{align*}
P_n(k) &= \sum_{i=1}^n P(\text{elegir plato $i$} \cap \text{plato $i$ es el mejor}) \\
&= \sum_{i=1}^n P(\text{elegir plato $i$} \mid \text{plato $i$ es el mejor})
\cdot P(\text{plato $i$ es el mejor}) \\
&= \sum_{i=1}^k 0 \cdot \frac{1}{n} +
\sum_{i=k+1}^n \bigg(
\begin{matrix}
\text{el mejor de los primeros $i-1$ platos}\\
\text{está entre los primeros $k$ platos}
\end{matrix}
\,\bigg|\, \text{plato $i$ es el mejor} \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*}

Se trata ahora de identificar el \(k\) tal que \(P_n(k)\) sea lo mayor posible. Ese \(k\) decimos que es el \(k\) óptimo; y el valor de \(P_n(k)\) es la probabilidad de éxito (elegir el mejor plato) siguiendo esa estrategia.

Con ayuda de un ordenador es fácil comprobar que, para los primeros valores de \(n\), se tiene lo siguiente:

En general, ¿cómo encontrar el \(k\) óptimo o, al menos, cómo estimarlo para \(n\) grande?

Obsérvese que, si partimos el intervalo \([0,1]\) en \(n\) trozos,

$$
P_n(k) = \frac{k}{n} \sum_{i=k+1}^n \frac{1}{i-1}
$$

son las sumas de Riemann de la integral

$$
P(x) = x \int_{x}^1 \frac{1}{t}\,dt = -x \log(x), \qquad x \in [0,1],
$$

luego, para \(n\) grande, \(P_n(k) \sim P(k/n)\).

Como \(P'(x) = -1 – \log(x)\), el máximo de \(P(x)\) está en \(x=e^{-1}\), y vale \(P(e^{-1}) = e^{-1}\). Así pues, para \(n\) grande, el \(k\) óptimo será el que haga \(k/n \sim e^{-1}\) (es decir, \(k \sim n/e\)). A su vez, como \(P(e^{-1}) = e^{-1} \sim 0.367879\), la probabilidad de éxito de la estrategia eligiendo el \(k\) óptimo será, aproximadamente, de un \(36.8\%\). De hecho se puede comprobar que, con la estrategia óptima, la probabilidad de acertar con el mejor plato siempre es mayor que \(e^{-1}\).

Acabamos de ver que el \(k\) óptimo deberá ser, aproximadamente \(n/e\), pero no hay una fórmula exacta sencilla para expresarlo en función de \(n\). Aquí nos contentaremos con comentar la relación con la fracción continua de \(e^{-1}\), que es

$$
e^{-1} = (0, 2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1,\dots),
$$

y cuyos primeros convergentes son

$$
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};
$$

pues bien, hasta donde se conoce, estos convergentes \(k/n\) siempre se corresponden con pares \((k,n)\) donde \(k\) es el valor óptimo con \(n\) platos, pero no está demostrado que eso sea cierto siempre.

Se pueden ver más detalles en [4, sección 13.13], [5, capítulo 5] y [6, problema 47], en particular la relación de este problema con la constante de Euler-Mascheroni \(\gamma\) y con la función \(W\) de Lambert. Merece la pena asimismo mencionar que, en la On-Line Encyclopedia of Integer Sequences, la sucesión de los \(k\) óptimos es https://oeis.org/A054404

Para concluir, comentemos someramente los orígenes de este problema; en [2] se puede ver una historia mucho más completa. Aparentemente, el primero que se lo planteó fue Merrill M. Flood en 1949, y lo divulgó en varias conferencias de matemáticos, con lo cual comenzó a ser conocido. Pero la primera vez que se publicó fue, en febrero de 1960, en la columna Mathematical Games de Martin Gardner en Scientific American (hablando de papeletas con números positivos escritos en una cara). En realidad, problemas bastante similares ya los habían planteado Arthur Cayley en 1875 y Johannes Kepler en 1613 (este último, con el objetivo real de elegir una nueva esposa tras enviudar en 1611).

Referencias

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