(a) Para cada delegado, exactamente una rotación de la mesa lo pone en la silla correcta. Como hay 15 delegados, pero solamente 14 rotaciones no triviales, necesariamente alguna rotación tiene que acomodar dos o más delegados.
Comentarios. Muchas personas hicieron notar que el mismo argumento funciona para cualquier número n > 1 de delegados.
Matthew Lim nos recuerda que no debemos estar tan sorprendidos por tal arreglo – concretamente, del hecho de que cada delegado elija al azar una silla diferente de la asignada. La realidad es que hay una probabilidad de 1/3 de que esto suceda. Para más información sobre esta pregunta de probabilidad se puede buscar (en inglés) “derangements”. Por ejemplo, http://mathworld.wolfram.com/Derangement.html.
(b) La solución más popular fue ubicar a los delegados en el orden opuesto al de los carteles. Vamos a argumentar de dos maneras por qué este orden funciona, una geométrica y otra algebraica. Después de ello daremos algunas soluciones recibidas, y finalmente analizaremos la cuestión de si hubiera n delegados en lugar de 15.
Solución geométrica a (b).
Tenemos que mostrar que cuando las tarjetas y los delegados son puestos en órdenes opuestos, hay exactamente un delegado correctamente sentado para cada una de las 15 rotaciones de la mesa. Pero esto es un hecho standard sobre las simetrías de un polígono regular de n lados, que consisten de n rotaciones y n reflexiones. Las rotaciones preservan el orden de los vertices, mientras que las reflexiones lo invierten. Cuando n es impar, cada reflexión fija un vértice, digamos v, e intercambia el vértice que está a distancia j a la izquierda de v con el que está a distancia j a la derecha de v. Solamente queda observar que una reflexión seguida de una rotación tiene el mismo efecto que una sola reflexión: se revierte el orden, de manera que tiene que haber un solo vértice fijo. En el contexto del problema, esa posición fija representa al delegado sentado delante del cartel correcto.
Solución algebraica a (b).
Numeremos los delegados d = 0, 1, ... 14, y sea c(d) el número en el cartel originalmente delante del delegado d (de manera que c(d) también varía entre 0 y 14). Trabajamos “mod 15”, o sea que si j es mayor o igual a 15, lo reemplazamos por j – 15 (15 es 0 (mod 15), 16 es 1 (mod 15), etc.) Una rotación de la mesa de k posiciones lleva la posición representada por c(d) a c(d) + k (mod 15). Nuestra tarea es describir una permutación c(d) con la propiedad de que para cada k entre 0 y 14, existe exactamente un d tal que c(d) + k = d (mod 15). La permutación c(d) = 15 – d pone los carteles en el orden inverso. Es sencillo verificar que para cada valor de k, la ecuación d = (15 – d) + k (mod 15), que se reduce a
2d = 15 + k,
tiene la propiedad deseada. Como 2d (mod 15) toma cada uno de los 15 valores posibles exactamente una vez, la ecuación tiene una única solución d para cada k; o sea, cada rotación tiene exactamente una posición donde el cartel correcto está enfrente del delegado.
Soluciones alternativas a (b).
En la solución algebraica anterior, podemos poner c(d) = Md + J, donde M y J son números menores que 15, y M tiene la propiedad de que tanto él como M – 1 son coprimos con 15. (M tiene que ser coprimo con 15 para que Md sea una permutación de los números 0 a 14, mientras que M – 1 tiene que serlo para que d = Md + J se satisfaga para un solo valor de d independientemente del valor de J). Mir hace notar que
M = 2, 8, 14
son las únicas posibilidades. Como 14 = -1 (mod 15), este valor de M da la solución popular mencionada arriba (donde los carteles y los delegados están en órdenes opuestos). Las otras dos soluciones se obtienen poniendo el cartel 2d delante del delegado d, o poniendo el cartel 8d delante del delegado d (que es lo mismo que poner al delegado 2d enfrente del cartel d).
Soluciones para cuando hay n delegados.
Las soluciones de Bornztein y Lim tratan independientemente el caso de n delegados. Muestran que, como en la solución alternativa, cuando n es impar c(d) = -d es siempre solución (porque n – 1 y n – 2 son siempre coprimos con n para cualquier número impar n). Está claro que no hay solución de la forma c(d) = Md + J cuando n es par (porque M o M – 1 será par, y por tanto no coprimo con n). He aquí el argumento usado tanto por Bornztein como por Lim para mostrar que, más generalmente,
