Estaba yendo aunque problems en la teoría de los gráficos publicado por Prof. Ericksson de mi alma-mater y encontré esta pregunta bastante única sobre las palomas y su tendencia innata a formar pedidos de picoteo. La pregunta es la siguiente:¿Orden de picoteo de palomas?
Cada vez que se reúnen grupos de palomas, de modo instintivo, establecer una ley del más fuerte orden. Para cualquier par de palomas, una paloma picotea siempre a la otra, alejándola de los alimentos o parejas potenciales. El mismo par de palomas siempre elige el mismo orden jerárquico, incluso después de años de separación, sin importar qué otras palomas están alrededor. Sorprendentemente, el orden global picoteo puede contener ciclos, por ejemplo, paloma A picotea paloma B, que picotea paloma C, que picotea paloma A.
Demostrar que cualquier conjunto finito de palomas puede estar dispuesto en una Rema desde la izquierda hasta derecha para que cada paloma picotee la paloma inmediatamente a su izquierda.
Dado que se trata de una cuestión de teoría de grafos, lo primero que se me pasó por la cabeza es que se trata simplemente de un tipo topológico de relaciones (las relaciones son el orden jerárquico). Lo que hizo esto un poco más complejo fue el hecho de que puede haber relaciones cíclicas entre las palomas. Si tenemos una dependencia cíclica como sigue:
A-> B-> C-> A
donde A picotazos en B, B picotazos en C y C va y picotazos en A
Si lo representamos en la forma sugerida por el problema, tenemos algo de la siguiente manera: CBA
Pero lo anterior fila de pedido determinado no tiene en cuenta el orden jerárquico entre C y A.
tuve otra idea de resolverlo por inducción matemática El caso base es para dos palomas dispuestas de acuerdo a su orden jerárquico, suponiendo que el orden de picoteo es válido para n palomas y luego se demuestra que es cierto para n + 1 palomas.
No estoy seguro de si voy por la pista incorrecta aquí. Algunas ideas sobre cómo debería analizar este problema serán útiles.
Gracias
No es mi área de especialización, por mi lógica simplista dice que si es circular o cíclica, obviamente no pueden alinearse de izquierda a derecha en una línea * recta *. Círculos interconectados, similares al logo de los Juegos Olímpicos quizás, pero no en una fila recta. – MJB
Si tienes cuatro palomas, entonces hay 6 parejas de palomas. La forma lineal implicará tres de esos pares. Por lo tanto, tendrá que ignorar algunos de los emparejamientos. La tarea, mientras la leo, es mostrar que siempre puede seleccionar emparejamientos para producir un orden lineal, en lugar de que haya un orden lineal que represente todos los emparejamientos. –
El caso cíclico de 3 palomas también me hizo preguntarme, pero luego verifiqué nuevamente la redacción de la pregunta: > cada paloma picotea a la paloma inmediatamente a su izquierda. Esto parece no exigir que haya nada a la izquierda de C, solo que puedes acomodar las palomas en * alguna fila * de modo que cada paloma que * tiene * otra a su izquierda, la picotee. Entonces 'C B A' sería válido, como lo haría' B A C', al igual que 'A C B'. Del mismo modo, si tiene 'A-> B',' A-> C' y 'B-> C', alinear las palomas en una fila no puede transmitir tanto' A-> B' como 'A-> C '. Pero 'C B A' es la (única) respuesta en ese caso. ¡Problema interesante! – shambulator