Un maleducado y un avión

Ayer en el programa que emitimos de Los 3 chanchitos planteé un problema (otro) que encontré, de nuevo, en FiveThirtyEight. Puesto que mucha gente me está reclamando una solución más reposada, aprovecho para ponerla aquí.

El problema en cuestión es el siguiente:

Está en una cola de 100 personas para embarcar en un avión que tiene 100 plazas, todas previamente asignadas. Tú estás el último y la primera persona es idiota, muy maleducado o una suma de diversos factores que, entre otras taras, le impiden seguir las mínimas normas sociales, de tal forma que entra en el avión y se sienta en una plaza cualquiera al azar. El segundo, si ve su asiento libre, se sienta en él, pero si estuviera ocupado escoge otro al azar y así sucesivamente. ¿Qué probabilidades hay de que consigas sentarte en tu asiento previamente asignado?

Ahora lo que toca es que el amable lector (el lector siempre es amable, como el marco incomparable) piense un rato sobre el problema. Estaría muy feo que te lanzaras en busca de la respuesta como una hiena hambrienta sobre un ñu recién caído (puede que me tenga que trabajar mejor el símil). Así que voy a poner una imagen ilustrativa y confiar en que vas a pensar antes de rendirte.

¿Has pensado un rato? voy con la solución:

Antes una cuestión previa pero que tiene importancia:

Cuando es tu turno de embarcar (eres el último) sólo hay un asiento vacío y ese asiento forzosamente es el tuyo o el asignado al primer pasajero.
Veamos que esto es cierto: pensemos en cualquier otro asiento y comprobemos que no puede estar libre. Por ejemplo, el pasajero número 50, cuando llega, si su asiento está ocupado, escoge otro cualquiera, y si está libre, se sienta en él, así que el asiento del pasajero 50 no puede estar libre cuando tú llegas.

Lo anterior es la clave para resolverlo, ya que no existe preferencia de ningún tipo, ni entre el primer pasajero, ni entre los demás que vean su asiento ocupado, para haber ocupado el del primer pasajero o el tuyo: son hechos totalmente equiprobables. Así que tenemos en la mitad de los casos estará libre el tuyo y en la otra mitad el otro.

Por lo tanto, la probabilidad de que tu asiento esté libre es de 1/2 (y da igual que el avión tenga dos plazas o mil).

También puedes hacer las cuentas: si es un avión de dos, la probabilidad de que el primero se siente en su asiento es de 1/2. Si es de 3, encontrarás tu asiento ocupado si el primero se sienta en él (1/3) o el primero se sienta en el del segundo y este en el tuyo ((1/3)(1/2)=1/6). Pero 1/3+1/6=1/2. Y así para cualquier número de asientos.

Muchas casillas, un dado y unas monedas

Puede que leas esto después del 8 de noviembre de 2016, espero muy sinceramente que para entonces Donald Trump no sea el presidente electo. Pero yo estoy escribiendo esto bastante antes de dicha fecha y no sé si Nate Silver volverá a acertar los resultados de las elecciones presidenciales americanas con impresionante precisión tal y como hizo en 2008 y 2012. Acierte o no, recomiendo la lectura de su libro La señal y el ruido, en él explica parte de su trayectoria y de sus métodos para analizar los datos y saber quedarse con la señal (la información valiosa) distinguiéndola del ruido (los datos que no solo no aportan nada, sino que pueden llevar a conclusiones erróneas). El bueno de Nate ha pasado del póker y las apuestas deportivas a ganarse la vida, muy bien, haciendo predicciones de todo tipo. Pero, FiveThirtyEight, el blog que creó en 2008, no se limita a decirnos quién ganará el próximo partido de la NBA o las elecciones presidenciales, también propone el tipo de acertijos y problemas que le gustan a los que allí trabajan. Uno de los retos que han aparecido allí me ha llamado poderosamente la atención y quiero comentarlo aquí.

En esta entrada, se recogen dos problemas, el primero de ellos es un clásico y como lo he visto tantas veces asumo que el lector también, aunque es muy posible que yo esté equivocado, así que le puedes echar un vistazo. Pero el problema que quiero plantear aquí es el segundo:

Se tiene una cinta con 1000 casillas, tres monedas, un dado normal de seis caras y una ficha. Puedes situar las monedas en las casillas que quieras, pero una vez colocadas ya no se pueden mover. Ahora se trata de tirar el dado y avanzar con la ficha tantas casillas como indique el dado. Si en algún momento caes en una de las casillas que tiene una moneda, has ganado, en caso contrario, pierdes. ¿Dónde situarías las monedas? ¿Qué probabilidades tienes de vencer? 

Naturalmente, te sugiero que pienses un poco el problema. Para evitar que caigas en la tentación de mirar inmediatamente la solución que propongo, pondré una imagen.

Espero que el sucio truco que he utilizado haya dado sus frutos y que ya tengas pensado algo.

Lo primero que se puede ocurrir es situar las monedas en cualquier sitio, ya que no está claro que el azar favorezca unas casillas sobre otras. Así que pensemos que ponemos las tres monedas en las casillas 1, 2 y 3, es muy fácil comprobar que en tal caso tu probabilidad de ganar es de 1/2: si sale en la primera tirada uno de dichos números, has ganado, en otro caso, pierdes seguro. Pero si las sitúas en las posiciones 2, 3 y 4 tus posibilidades aumentan, ya que si sale 2, 3 o 4 en la primera tirada, has ganado, si sale 5 o 6 pierdes seguro, pero si sale 1 aún puedes ganar en la segunda tirada (con una probabilidad de 1/2). Por lo tanto, en este caso, si calculamos las posibilidades de ganar hemos de sumar 1/2 (que salga 2, 3 o 4) con el producto de 1/6 (que saquemos un 1) por 1/2 (que obtengamos 1, 2 o 3 después del 1). Esto es, 1/2+1/12.

Así que ¿dónde nos tenemos que situar? Tal y como aconseja Descartes en su Discurso del método, si no sabes resolver un problema hay que «conducir con orden mis pensamientos, empezando por los objetos más simples y más fáciles de conocer, para ascender poco a poco, gradualmente, hasta el conocimiento de los más compuestos». En román paladino: tratemos de pensar que tenemos sólo una moneda y veamos dónde hemos de situarla.

Llamaremos P[k] a la probabilidad de ganar si situamos una moneda en la casilla "k". Evidentemente, sólo podemos llegar a una posición directamente, en una sola tirada, desde las seis anteriores y desde cualquiera de ellas, llegaremos a la "k" con una probabilidad de 1/6, por lo tanto:

P[k]=1/6*(P[k-1]+P[k-2]+P[k-3]+P[k-4]+P[k-5]+P[k-6])

Desde las primeras 6 casillas, también se puede llegar directamente en la primera tirada, por lo tanto, las probabilidades en cada caso son:

P[0]=1 (significa que empezamos en una casilla "0")

P[1]=1/6*P[0]

P[2]=1/6*(P[0]+P[1])

P[3]=1/6*(P[0]+P[1]+P[2])

P[4]=1/6*(P[0]+P[1]+P[2]+P[3])

P[5]=1/6*(P[0]+P[1]+P[2]+P[3]+P[4])

P[6]=1/6*(P[0]+P[1]+P[2]+P[3]+P[4]+P[5])

Si calculamos (en mi caso he usado Sagemath que es gratuito y código abierto para realizar todos los cálculos) todas estas posibilidades obtenemos:

P[1]= 0.166666666667
P[2]= 0.194444444444
P[3]= 0.226851851852
P[4]= 0.264660493827
P[5]= 0.308770576132
P[6]= 0.36023233882
P[7]= 0.25360439529
P[8]= 0.268094016728
P[9]= 0.280368945441
P[10]= 0.28928846104
P[11]= 0.293393122242
P[12]= 0.29083021326
P[13]= 0.279263192334
P[14]= 0.283539658507
P[15]= 0.286113932137
P[16]= 0.28707142992
P[17]= 0.286701924733
P[18]= 0.285586725149
P[19]= 0.284712810463
P[20]= 0.285621080152
P[21]= 0.285967983759
P[22]= 0.285943659029
P[23]= 0.285755697214
P[24]= 0.285597992628

En realidad, na habría hecho falta calcular nada para ver que el mayor valor se obtiene en P[6], ya que en su expresión aparece el P[0] que vale 1 y todos los demás valores se pueden acotar muy fácilmente.

Bien, ya sabemos que si situamos una única moneda, esta tenemos que colocarla en la casilla 6 que nos da una sorprendente probabilidad de salvarnos de 0.36 (más de un tercio).

Este es el momento de dar un paso más y tratar de calcular que ocurre si situamos dos monedas. Si llamamos L[i,j] a la probabilidad de salvarnos situando una moneda en la casilla "i", y la otra en la "j". L[i,j]="probabilidad de caer en i"+probabilidad de caer en j"-"probabilidad de caer en las dos". Obsérvese que tenemos que restar la probabilidad de caer en los dos porque, en caso contrario, estaríamos contando dos veces dicha probabilidad. Pero la probabilidad de caer en la segunda (digamos j) estando en la primera (la i) es igual a la probabilidad de caer desde el inicio en la casilla "j-i", puesto que la probabilidad de estar en la primera es P[i], la probabilidad de caer en los dos es P[i]*P[j-i], así tenemos:

L[i,j]=P[i]+P[j]-P[i]*P[j-i]

Y podemos calcular todo con lo ya calculado anteriormente. Si metemos las instrucciones correspondientes en Sagemath, obtenemos que el máximo valor se obtiene situando las monedas en las posiciones 5 y 6  y la probabilidad en este caso es un increíble 0,62 (poco menos de 2/3).

Con las ideas anteriores no es difícil de ver qué ocurre con tres monedas. Utilizamos el mismo principio de exclusión-inclusión y la probabilidad de tres es la suma de las probabilidades individuales, menos las probabilidades de caer en dos de las casillas seleccionadas, más la probabilidad de caer en las tres. Esto es, si llamamos T[i,j,k] a la probabilidad de salvarnos poniendo las monedas en las posiciones "i", "j" y "k", tenemos:

T[i,j,k]=P[i]+P[j]+P[k]-(P[i]*(P[j-i]+P[k-i])+P[j]*P[k-j])+P[i]*P[j-i]*P[k-j]

Así que es muy fácil pedirle a Sagemath que realice los cálculos pertinentes y obtenemos que el máximo valor se obtiene situando las monedas en las casillas 4, 5 y 6 y nos salvaremos con una probabilidad muy cercana a 0,8. 

Naturalmente, podemos utilizar todos estos datos para responder a muchas más preguntas que se pueden plantear asociadas a este problema, pero pienso que ya está bien por hoy.

PS: Este es el fichero de Sagemath que he creado para realizar los cálculos.

Tazas, rosquillas y un Nobel de Física

Minutos antes de sentarme a escribir estas líneas, se acaba de otorgar el premio Nobel de Física 2016 a David J. Thouless, al que le corresponde la mitad del premio y a F. Duncan M. Haldane y J. Michael Kosterlitz, con un cuarto de premio a cada uno "por los descubrimientos teóricos de las transiciones de fase topológica y fases topológicas de la materia". Podéis leer esta fantástica entrada de otro de los chanchitos sobre los aspectos físicos de dicha temática; pero la palabra "topológica" se repite dos veces y da la casualidad que mi tesis y mis primeros diez años de trabajo (sort of) en la universidad estuvieron centrados en la topología. Voy a tratar de explicar en qué consiste dicha disciplina porque esta noche, para mi, tendremos un especial de Los 3 chanchitos sobre dicho Nobel (por cierto, si cuando lees esto aún estás a tiempo, te agradecería el voto a nuestro podcast para los premios Bitácoras, lo puedes hacer dándole a este enlace).

La topología es una rama de las matemáticas que trata de estudiar las propiedades de los cuerpos cuando no tenemos en consideración ningún tipo de medición (ni de distancia, ni de distancia, etc.).
Se podría decir que a la topología no le importa tus medidas, sino lo que encierras. 

Voy a poner algunos ejemplos para tratar de hacerme comprender:
El que algo sea una circunferencia es una propiedad métrica ya la definición nos dice que es el conjunto de puntos que "equidista" de otro. Pero ser un segmento también depende de la métrica (es el camino "más corto" entre dos puntos) , por lo tanto, ser un triángulo o un cuadrilátero, etc., también son propiedades métricas. Así que en topología no podemos tener circunferencias, ni triángulos o, mejor dicho, no hay ninguna propiedad topológica que distinga a una circunferencia de un triángulo: si nos ponemos las gafas de visión topológicas una circunferencia y un triángulo son la misma cosa. podemos asignar a cada punto del triángulo un punto de la circunferencia de manera biunívoca conservando todas las propiedades topológicas.

Entonces, ¿qué cosas puede distinguir la topología? Lo primero que podríamos destacar como propiedad topológica es si algo tiene un pedazo (es conexo, aunque hay muchas matizaciones sobre ello) o más de uno. Así, un segmento no es lo mismo, aún con las gafas de visión topológicas puestas, que dos segmentos. Y si tenemos una pieza de pan, para un topólogo es lo mismo que qcualquier otra pieza de pan, pero si una de ellas la partimos en dos, ya sí se pueden diferenciar.

Estos dos representantes de la especie humana son topológicamente indistinguibles, salvo si partimos a uno de ellos por la mitad. Sin embargo, es muy probable que la ropa que llevan sí los pueda diferenciar (a simple vista da la sensación de que el individuo de la izquierda lleva más trozos de ropa en su vestimenta). 

En realidad, esta propiedad, la de ser un trozo (o conexo) o no serlo, se puede considerar como la propiedad topológica fundamental, la que nos va a permitir distinguir entre multitud de objetos (técnicamente el número de componentes conexas de un objeto).
Veamos cómo. Nos podemos preguntar si un segmento es lo mismo que una circunferencia: los dos tienen sólo un trozo, así que podría parecer que no, que no vamos a poder distinguirlos. Así que supongamos que el segmento y la circunferencia son la misma cosa para la topología y que cada punto del segmento se corresponde de manera biunívoca con uno de la circunferencia de tal forma que se conservan todas las propiedades topológicas.
Pensemos ahora en el punto medio del segmento, ese punto mediante la correspondencia que acabamos de suponer, se ha de corresponder con algún punto de la circunferencia, pero ¿qué ocurre al quitar el punto medio del segmento? Que se parte en dos el segmento. Sin embargo, no existe ningún punto en la circunferencia que al quitarlo parta en dos a ella. Por ello, podemos decir que la circunferencia y el segmento no son la misma cosa desde un punto de vista topológico: necesitamos dos puntos para romper en dos pedazos disconexos una circunferencia.

Tratemos de avanzar un poco y saltemos al mundo tridimensional. El equivalente ahora a una circunferencia sería una esfera. Es fácil ver que si pintamos cualquier circunferencia sobre la superficie de la esfera y quitamos exactamente los puntos de esa circunferencia de la esfera, dividimos a la esfera en dos trozos.

Y lo mismo ocurre si le quitamos a la esfera cualquier curva equivalente a una circunferencia (esto se conoce como el Teorema de curva cerrada de Jordan). 

Sin embargo, en la superficie de un donut (lo que los topólogos llamamos un toro), podemos encontrar circunferencias que no la dividen en dos:

Si cortamos por la circunferencia marcada con una v, no dividimos ala toro en dos 

Por lo tanto, para un topólogo no es lo mismo una esfera que un toro (y si para casi nadie es lo mismo, dicho sea de paso). Sin embargo, es todo un clásico decir que el topólogo es incapaz de distinguir entre una taza de desayuno y un donut. Efectivamente, como prueba esta imagen, podemos pasar de forma continua (y esta palabra es clave) de una al otro.

Lo curioso es que se sabe cuáles son todas las superficies que existen desde un punto de vista topológico y hay tres propiedades que las caracterizan: tener borde o no, ser orientable o no (un ejemplo de no orientable es la banda de Möbius de la que nos habló la chanchita en este vídeo) y el numero de asas: la esfera no tiene, el toro tiene una, el doble toro tiene dos, etc.

Triple toro (con tres asas)

Naturalmente, existen otras propiedades topológicas, pero digamos que lo que acabamos de ver es lo fundamental. Tal y como se ve en la imagen publicada por el académico Johan Jarnestad para explicar la concesión del Nobel:

  

Cada vez que se produce un "pow" se cambia la topología

Pues ya sabéis, estás rosquillas se acaban de llevar un Nobel de física y este es casi el único consuelo que nos queda a los matemáticos por haber sido excluidos de tamaña distinción.