El problema de las hormigas en una pelota

Question

Supongamos que pongo una hormiga en un pequeño coche de carreras en cada cara de un balón de fútbol. A continuación, cada hormiga recorre los bordes de su cara en sentido contrario a las agujas del reloj. El objetivo es demostrar que dos de las hormigas acabarán chocando (siempre que no se les permita quedarse quietas o ir arbitrariamente despacio).

Mi hermano me habló de este resultado, pero no puedo probarlo. En lugar de un balón de fútbol, deberíamos poder utilizar cualquier gráfico conectado en una esfera (siempre que no haya vértices de valencia 1). También podemos suponer que tampoco hay vértices de valencia 2, ya que siempre se pueden fusionar las dos aristas.

Yo (y algunas personas con las que he hablado) hemos hecho una serie de observaciones y planteamientos:

• Obsérvese que si dos hormigas se encuentran alguna vez en la misma arista, entonces chocarán, por lo que el problema es discreto. Puedes llevar la cuenta de en qué borde está cada hormiga y dejar que las hormigas se muevan de una en una. Entonces el objetivo es demostrar que no hay forma de que las hormigas se muevan sin chocar, a menos que alguna hormiga se mueva sólo un número finito de veces.
• Puedes asumir que todas las caras son triángulos. Si hay una cara con más de tres aristas, entonces puedes triangularla y hacer que las hormigas de los triángulos se muevan de tal manera que se vea exactamente igual "desde fuera". Si hay un 1-gon, es fácil mostrar que las hormigas se estrellarán. Si hay un 2-gon, es fácil demostrar que se puede convertir en un borde sin cambiar si hay o no un choque.
• Un enfoque es inducir en el número de caras. Si hay un contraejemplo, creo que deberías poder fusionar dos caras adyacentes o reducir una cara a un punto para obtener un contraejemplo más pequeño, pero no consigo que ninguno de estos enfoques funcione.
• Si tienes un contraejemplo en un gráfico, creo que tienes un contraejemplo en el gráfico dual. Haz que la hormiga dual esté en la siguiente arista por la que una hormiga (no dual) pasará por el vértice dado.
• Parece que podría haber una solución muy hábil utilizando el teorema de la bola peluda.

Answer 1

Esto se conoce como el teorema del accidente de coche de Klyachko. Se demostró para probar un teorema sobre los grupos finitamente presentados. De hecho, el resultado permite que las hormigas se muevan a velocidades arbitrarias no nulas siempre que hagan infinitas vueltas alrededor de su celda 2. La conclusión es que, o bien hay una colisión entre hormigas en el interior de una arista, o bien hay una "colisión completa", lo que significa que hay una colisión en un vértice de todas las hormigas de aristas adyacentes.

EDIT: Oh, en realidad es importante que haya dos colisiones completas, lo que es algo más difícil de demostrar que una (una colisión en medio de una arista también es una colisión completa).

Puede leer un artículo expositivo de Colin Rourke aquí .

Answer 2

El puesto consta de ideas iniciales en la parte superior y la prueba en la parte inferior.

---

Creo que la idea clave es realizar el proceso inverso a lo que describes sobre la subdivisión en triángulos. De hecho, nuestro problema puede pensarse como un gráfico plano en el que todas las hormigas se mueven en el sentido contrario a las agujas del reloj, excepto una en el círculo exterior que va en el sentido de las agujas del reloj .

Ahora fíjate que parece que puedes combinar varias zonas en una sola, debe quedar igual o peor por fuera, y obtienes al final dos hormigas en el mismo círculo moviéndose en direcciones opuestas.

La parte de "igual o peor" es conjetural, pero la intuición es que suponiendo que tienes sólo dos círculos con borde común, "lo mejor" que puedes hacer es dejar que uno pase por el borde e inmediatamente después dejar que el siguiente siga. Si piensas en cómo afecta eso al mundo exterior, es muy similar a tener una sola hormiga recorriendo todo el material.

---

La prueba. Introduzcamos algo de notación. Primero, consideraré hormigas en el plano que juntas forman algo con un círculo exterior. Supongamos que las hormigas han decidido el horario y han empezado a conducir. La hormiga exterior es conductor ebrio que va en el sentido de las agujas del reloj.

Probaremos que el choque se producirá necesariamente antes de que el conductor ebrio haga un ciclo completo.

Lema crucial. Supongamos que tengo dos áreas A y B combinadas por un borde y un programa de conducción que incluye al conductor ebrio haciendo un ciclo completo. Entonces es posible elegir una de las áreas, A o B, y la modificación de la ruta del conductor ebrio que hace un ciclo completo alrededor del área elegida.

El lema se establece haciendo un dibujo (actualización: se ha publicado una respuesta que remite a un documento con la solución. la respuesta es la misma así que puedes leer la descripción correspondiente allí). Después de tener el lema, ya está hecho, porque se ve que debe haber una cara simple (área mínima) con una hormiga sobria y otra borracha que debe chocar.

Answer 3

Un comentario rápido sobre la idea de "una solución muy hábil utilizando el teorema de la bola peluda". Cualquier muy seguramente sólo utilizará el hecho de que la característica de Euler es distinta de cero, por lo que debería aplicarse igualmente a superficies de mayor género (al menos dos). Por ejemplo, si lo entiendo bien, la respuesta de Reid de arriba funcionaría igual de bien en una superficie de género superior, por el teorema de Poincare-Hopf.

Pero el teorema no no se mantienen en superficies de género superior.

Lo que sigue probablemente sería mejor con imágenes, pero intentaré describirlo sin ellas y esperar lo mejor.

Por ejemplo, es fácil dividir un toro en dos rectángulos de manera que haya "horarios de tráfico" sin choques. (De acuerdo, la característica de Euler de un toro es cero, pero tenedme en cuenta). (Además, ¿qué es para las hormigas lo que un horario de tráfico es para los coches?)

Consideremos ahora la superficie de género dos como un octógono con los lados identificados, como es habitual. Puedes dividirlo en dos rectángulos y dos pentágonos de forma que se imiten dos copias de la imagen del toro del párrafo anterior: la superficie es la unión de dos toros con límite, y cada toro se divide en un rectángulo y un pentágono. Programe cada toro como antes (extendiendo el recorrido de una de las hormigas sobre el quinto lado del pentágono). Como sólo una hormiga de cada toro atraviesa el quinto lado del pentágono, es fácil organizar que las hormigas de diferentes toros lo hagan en momentos diferentes.

¿Tiene sentido, o alguien quiere una foto?

EDITAR:

Ah, y por supuesto se deduce que el teorema también es falso en cualquier superficie orientable de género aún mayor, ya que todas cubren la superficie de género dos.

Answer 4

Quiero utilizar el teorema de la bola peluda de la siguiente manera. Supongamos, para simplificar, que empezamos en el tiempo 0 y que cada hormiga vuelve a su ubicación original en el tiempo 1. Supongamos que nunca se encuentran dos hormigas; entonces, por compacidad, hay ε > 0 tal que no hay dos hormigas que pasen por el mismo punto en tiempos más cercanos que ε. Deformemos cada cara ligeramente hacia adentro cerca de sus vértices para que se convierta en una incrustación suave de un disco en S^2. Supongamos también que las hormigas se mueven a lo largo de la frontera con velocidad positiva (de modo que el tiempo define un homeomorfismo de S^1 = [0, 1] / {0, 1} a la frontera de este disco).

Para cada cara defina un campo vectorial en la frontera por p -> R _t(p) v(p), donde v(p) es el vector unitario tangente al disco en p, t(p) es el tiempo que la hormiga está en el punto p, y R _a es la rotación (en el sentido de las agujas del reloj alrededor del vector exterior) en 2πa radianes. Este campo vectorial se extiende sobre el disco. Extiéndelo al resto de la esfera haciendo que caiga a 0 rápidamente fuera del disco.

La suma de todos estos campos vectoriales es distinta de cero en todas partes, excepto posiblemente cerca de los vértices, porque a lo largo de cualquier arista, el ángulo entre los vectores procedentes de las dos caras está acotado por debajo en términos de ε. Si se pudiera controlar lo que ocurre cerca de los vértices, esto contradiría el teorema de la bola peluda.

Answer 5

Digamos que hay n caras. El espacio de fase en el que se mueven las hormigas es T^n, y el movimiento de las hormigas está descrito por una curva en T^n que tiene velocidad acotada por abajo en cualquier dirección. Por lo tanto, basta con demostrar que si se corta T^n a lo largo de los lugares de colisión, se reduce la dimensión del H^1. Esta es una afirmación puramente combinacional, que (parece - no he comprobado todos los detalles) se puede demostrar por inducción.