MW: Alienígenas matemáticos – Los sombreros de los vamisos

Escribo este pequeño adendo al artículo de Alienígenas matemáticos – Entrenamiento civil con un doble objetivo. Por una parte para avisaros de que he actualizado el texto del artículo, ya que no sólo había algún error en la explicación del problema más difícil de todos, el último –entre otras cosas, a medio escribir en mi cabeza se cambiaron “amarillo” y “naranja”–, sino que además la explicación en sí era bastante pobre y confusa. Espero que ahora esté más claro: cuando le echéis un ojo me lo decís.

Por otro lado, entre los problemas alternativos que me habéis propuesto parecidos a los propuestos en el artículo, hay uno que encaja lo suficientemente bien en esta serie como para merecer una mención aparte. Me lo ha apuntado Gregorio Morales de modo que, aunque los adornos sean míos, el núcleo del problema y la solución son suyos. Gracias a Gregorio, quienes disfrutáis de esta absurda serie tenéis un pequeño apéndice al artículo anterior con un problema adicional endiabladamente difícil. Además, Gregorio se ha ofrecido amablemente a resolver dudas y pegas en comentarios, de modo que disfrutemos: la única cosa más divertida que pensar es pensar juntos.

Finalmente, por razones que no vienen al caso este mes está siendo espantoso y no voy a poder publicar un artículo semanal. Esta semana este pequeño adendo es el sustituto del artículo habitual. ¡Lo siento! A veces la vida se entromete.

Los sombreros de los vamisos

En la historia sobre el Banco Estelar de Deneb conocimos a los vamisos de Petrovichi, unas extrañas criaturas de origen probablemente artificial capaces de razonar, memorizar y calcular a una velocidad imposible para cualquier otra criatura de las galaxias conocidas –bueno, cualquier otra criatura con una excepción–. No hay más que ofrecer a uno de estos seres una alcaparra y calculará cosas para ti sin el menor problema, ya que aman esos encurtidos más que cualquier otra cosa en el mundo.

El caso es que, durante la conquista del planeta de los vamisos de Petrovichi, los Alienígenas matemáticos realizaron horrores genocidas que no puedo relatar aquí: los horrores habituales, por otro lado. Entre ellos, ¡sorpresa!, los monstruos hicieron espantosos experimentos matemático-psicológicos con las pobres criaturas, experimentos tanto más interesantes por las extraordinarias capacidades de los vamisos.

El más célebre de estos experimentos se produjo tras una modificación genética de un grupo de vamisos: se introdujo en su código genético ADN de lutrino, lo cual permitió a estos vamisos reproducirse a un ritmo gigantesco. Cuando empezó el experimento, el grupo de vamisos de Petrovichi modificados constaba de infinitos individuos.

Estos infinitos vamisos fueron informados por parte de sus captores de que a la mañana siguiente realizarían el siguiente proceso:

Todos los vamisos se pondrían en una fila –de longitud infinita, por supuesto–, mirando en el mismo sentido y con los ojos tapados. El del final de la fila, el número 1, vería a todos los demás vamisos frente a él –pero no su propio sombrero, claro–. El número 2 vería los sombreros de los vamisos 3 en adelante, el número 4 el de los vamisos 5 en adelante, etc.
Cada vamiso recibiría entonces un sombrero de color blanco o negro, un papel con su nú y dos bolas, una blanca y otra negra, y se le informaría de su número de posición (por ejemplo, “Eres el vamiso número 236″), siempre contando desde el vamiso 1 que ve a todos los demás.
Todos los vamisos abrirían los ojos a la vez, de modo que podrían ver a todos los demás vamisos frente a ellos (pero no su propio sombrero ni los que tienen detrás).
Cinco segundos después, todos los vamisos simultáneamente dejarían caer una de las dos bolas, blanca o negra, y se quedarían con la otra.
Cada vamiso cuya bola coincidiera con el color de su sombrero sobreviviría, y quienes tuvieran una bola del color contrario a su sombrero morirían.

Entonces, antes de irse a dormir, se permitió a los vamisos de Petrovichi que discutiesen una estrategia óptima que permitiese sobrevivir al mayor número posible de ellos. Tras la discusión nocturna, al día siguiente se realizó el experimento y la sorpresa de los Alienígenas matemáticos fue mayúscula: los vamisos habían planeado una estrategia que no sólo hizo sobrevivir a un número infinito de ellos, sino que sólo murió un número finito de vamisos.

¿Qué estrategia acordaron esa noche? Observa que, además de la diferencia obvia con el problema anterior –el hecho de que hay infinitos vamisos en vez de un número finito de humanos–, en este caso no hay manera de dar información al jugador frente a ti, ya que los vamisos hacen sus apuestas simultáneamente.

Como pista, recuerda que los vamisos pueden memorizar y calcular infinitamente rápido y con una capacidad ilimitada, además de ver infinitos vamisos frente a ellos, lo cual ya tiene mérito. ¿Eres capaz de inventar una estrategia con la que muera sólo un número finito de ellos? Si te sirve de consuelo, yo no: Gregorio tuvo que darme la solución, e incluso al leerla por primera vez no la entendí. Pero, por si acaso, dejo un espacio antes de seguir con el problema, que nunca se sabe cuándo hay un genio entre nosotros.

Tan pronto como estuvieron solos para su conversación nocturna los vamisos de Petrovichi, ni cortos ni perezosos, empezaron a crear definiciones y teoremas. En vez de pensar en sombreros concretos, lo hicieron acerca del conjunto de todos los sombreros. Al fin y al cabo, una vez todos tuvieran sombrero, el resultado sería una secuencia infinitamente larga de sombreros blancos y negros.

Esa fue su primera definición: una secuencia es una serie concreta de infinitos sombreros, por ejemplo BNBNBNBN… Y la solución es la secuencia correcta de infinitos sombreros.

¿Cuántas posibles secuencias de sombreros podría haber? Evidentemente, infinitas, de las cuales sólo una es la solución. Sin embargo, no todas las secuencias diferentes serían igualmente diferentes. Unas serían más parecidas que otras. Por ejemplo, estas dos secuencias son diferentes: BNBNBNBNBNBN… y NBNBNBNBNBNB… De hecho, en esas dos secuencias absolutamente todos los sombreros son diferentes, pues cuando en una el sombrero n es blanco, en la otra es negro y viceversa. Hay infinitos sombreros diferentes entre ambas.

Otro ejemplo de dos secuencias muy diferentes: supongamos que ambas empiezan igual, digamos que BBBNNB para ambas, pero a partir de ahí absolutamente todos los sombreros son diferentes. Una vez más, ya que las secuencias no acaban nunca, hay infinitos sombreros diferentes entre ambas –aunque en este caso hay un número finito de sombreros que son iguales, BBBNNB–.

Otro ejemplo más: imaginemos dos secuencias en las que los sombreros pares son todos exactamente iguales en ambas, pero los sombreros impares son diferentes. Por ejemplo, BBBBBBB… y NBNBNBNB…. En ellas hay un número infinito de posiciones idénticas y también un número infinito de posiciones diferentes. Pero, para lo que importaba a los vamisos, la clave era esa segunda parte: hay un número infinito de sombreros diferentes.

¿Es posible que haya secuencias en las que sólo un número finito de posiciones tengan sombreros diferentes? Por supuesto que sí: el caso opuesto al de la secuencia inicial idéntica. Si existe un punto a partir del cual todos los sombreros son iguales, la diferencia será entonces la secuencia finita de sombreros hasta ese punto. Por ejemplo, BBBBBNBNBNBNB… y NNNNNNBNBNBNB…. a partir de la posición 6 son secuencias idénticas, pero las cinco primeras posiciones no lo son. Por lo tanto, la diferencia entre ambas es sólo un número finito de posiciones.

De modo que los vamisos realizaron la siguiente definición: dos secuencias son semejantes si se diferencian en un número finito de posiciones, y desemejantes si se diferencian en un número infinito de posiciones.

A continuación dividieron las infinitas secuencias posibles en conjuntos de secuencias semejantes. Hay infinitos conjuntos de este tipo, y cada conjunto tiene un número infinito de secuencias, pero entre sí todas las secuencias semejantes de un conjunto difieren, como es natural, tan sólo en un número finito de elementos.

Aquí viene la clave de la cuestión: para cada conjunto de secuencias semejantes los vamisos eligieron un patrón, una secuencia concreta del conjunto que consideraron representante de todo el conjunto. Daba igual cuál fuese el sistema para elegir patrón, siempre que estuviera claro para todos los vamisos cuál era el patrón de un conjunto determinado.

El teorema correspondiente, la clave de su estrategia, fue éste: un patrón es semejante a todas las secuencias de su conjunto. La demostración es tan tonta que no voy ni a mencionarla. La consecuencia, también perogrullesca, es esencial: un patrón sólo se diferencia de todas las secuencias de su clase en un número finito de sombreros.

¿Por qué era esto importante? Porque, cuando un vamiso determinado –cualquiera que fuese– abriera los ojos, vería infinitos sombreros frente a él y, lo que es más importante, el número de sombreros que no podría ver sería finito. Y esto es verdad para todos ellos, luego todos tienen esa ventaja, el hecho de que a su espalda hay un número finito de sombreros, y frente a ellos un número infinito de sombreros.

Al ver un número infinito de sombreros, todo vamiso puede identificar la secuencia frente a él y, por tanto, el conjunto de secuencias semejantes al que pertenece. Fijémonos, por ejemplo, en el vamiso n. Cuando abre los ojos puede ver la parte de la solución desde n+1 hasta el infinito, pero no puede ver los elementos de la solución 1 hasta n. Ve un número infinito de vamisos y no ve un número finito.

De modo que todos los vamisos acordaron lo siguiente:

Al abrir los ojos y ver los infinitos sombreros frente a ellos –pero no los que tienen detrás– sabrían a qué conjunto de secuencias semejantes pertenecía la secuencia que estaban viendo. Por lo tanto, sabrían cuál es el patrón de esa secuencia, y se ajustarían a ese patrón. Finalmente, una vez decidido el patrón correspondiente al conjunto de secuencias similares a la que veían, elegirían como su sombrero el que correspondiese a su posición en el patrón elegido.

¿Por qué funciona esta estrategia como óptima? Hay que ir poco a poco para entenderlo.

Supongamos que tú, pacientísimo lector, eres informado de que eres el vamiso número 7. Miras frente a ti y ves una secuencia de sombreros infinita, digamos que BBNBBNBBNBBN… desde la posición 8 hasta el infinito.

Siendo un vamiso, en primer lugar identificas el conjunto al que pertenece esta secuencia, y luego recuerdas el patrón acordado para ese conjunto. Digamos que el patrón es NNNNNNNNNNBBNBBNBBNBBN… El patrón y la secuencia real que estás viendo son iguales desde la posición 10 en adelante. De hecho, las posiciones 8 y 9 no son iguales en el patrón (NN) y en la secuencia que ves (BB), pero eso da exactamente igual. No estás intentando encontrar la solución, sino el patrón correspondiente a la secuencia dada incluso aunque sepas seguro que no coincide con ella. Puede que patrón y secuencia visible no sean iguales, pero lo importante es que son semejantes.

Por lo tanto, dado que tu posición es la 7 y que el patrón tiene en la posición 7 un sombrero negro (N), cuando llegue el momento te quedarás en la mano con la bola negra y esperarás tener suerte.

¿Qué hará, en la misma jugada, el vamiso que hay frente a ti en la posición 8? Él ve un sombrero menos que tú, BNBBNBBNBBN…, pero una vez vislumbrados los infinitos sombreros asociará a la secuencia el mismo conjunto y, por lo tanto, el mismo patrón que tú. Dado que en el patrón la posición de su sombrero, la número 8, se corresponde con el negro (N), cuando llegue el momento él también se quedará con la bola negra en la mano.

El pobre vamiso número 8 no puede saberlo, pero está condenado: tú sí puedes ver su sombrero, que es blanco. Pobrecillo… pero es que este sistema no garantiza la supervivencia de ningún vamiso concreto, y tu compañero es una de las víctimas del sistema.

Veamos, no lo que le pasa a un vamiso concreto, sino a todos. Para eso nos hace falta la secuencia completa, es decir, la solución, no sólo lo que veías tú desde la posición 7. Supongamos que la solución es NBBNBBNBBNBBNBBNBBN…. Absolutamente todos los vamisos, independientemente de su posición, identificarán el conjunto de la secuencia que ven y elegirán su patrón –el representante que acordaron la noche anterior– que fue NNNNNNNNNNBBNBBNBBNBBN…

¿Qué le pasa entonces a cada vamiso? Cada uno se queda con la bola correspondiente del patrón. El vamiso 1 se queda con la bola N, y su sombrero es N, luego sobrevive. El vamiso 2 se queda con la bola N y su sombrero es B, luego muere. Lo mismo le pasa al vamiso 3. El vamiso 4 sobrevive pues su sombrero real coincide con el del patrón, pero los vamisos 5 y 6 mueren, porque tienen sombreros B pero el patrón tenía N en esas posiciones. El vamiso 7 (tú) sobrevive, pero el 8 y el 9 mueren ambos por tener sombreros blancos.

Pero quiénes viven y mueren de este conjunto inicial es absolutamente irrelevante –para la solución óptima, claro, no para los pobres vamisos involucrados–. ¿Por qué (y ésta es, otra vez, la clave de la cuestión)? Porque el número de vamisos iniciales hasta que el patrón y la solución coincidan, ya que ambos son semejantes, es finito.

Así, en nuestro ejemplo los vamisos 10 en adelante son ya la secuencia idéntica al patrón, luego absolutamente todos sobrevivirán, y son infinitos. Pero la clave de la cuestión, insisto, no es que ellos sean infinitos: es que la diferencia de sombreros entre el patrón y la solución es finita, porque son soluciones semejantes. Dado que todos los vamisos se ajustan al mismo patrón, sólo un número finito de ellos puede morir: aquellos infortunados de las posiciones en las que se diferencian patrón y solución.

¿Qué sistema deben elegir los vamisos para acordar un patrón de cada conjunto? Ésa es la belleza del sistema: da exactamente igual. Lo que no da igual, porque es lo que garantiza que el número de muertos sea finito, es que todos elijan el mismo patrón.

Como todos los problemas con infinito, va bastante contra la intuición y sospecho que al principio causará dudas y arqueamiento de cejas a casi todos. A mí me costó Dios y ayuda –ayuda de Gregorio– acabar entendiéndolo. De hecho, aunque podría ayudaros en comentarios, creo que será más divertido si planteáis las dudas o pegas que os surjan y Gregorio puede intentar resolverlas. Si no puedo evitarlo intervendré, pero intentaré hacerlo lo menos posible. Que comience la batal… quiero decir, que ustedes lo disfruten.