Aquí hay una pregunta que tenemos como tarea:
Un partido de fútbol entre el equipo A y el equipo B termina con un empate 9-9. Se sabe que en algún momento del juego el equipo A tenía la delantera y que luego fue el equipo B quien la tuvo. ¿Cuántas series de 18 goles pueden representar el curso del juego?
Sugerencia: utilice la técnica de doble reflexión.
Entonces, esta sugerencia realmente no me ayuda, ya que no entiendo qué es un doble reflejo. Aparte de eso: pensé en contar todas las series posibles, que es el número catalán C 9 , y luego restar todas las series donde B anotó el primer gol, pero es un poco vago en mi mente.
Cualquier pista que me ayudaría a empezar sería genial. ¡Gracias!
Sugerencia : probablemente sea más fácil contar las formas en que la condición puede fallar: es decir, el número de series en las que B gana/empata hasta cierto punto de inflexión, y luego A gana/empata por el resto del torneo.
Aquí hay una imagen canónica de tipo catalán que demuestra esto:
El punto marcado en rojo y amarillo es el punto de inflexión aquí. Ahora, ¿cómo puedes usar la técnica de reflexión en esto para obtener un gráfico catalán donde la línea negra siempre está arriba de la diagonal? ¿Puedes usar esto para terminar el problema?
No pude resolver el problema basándome solo en la sugerencia de Lopsy, así que aquí hay un poco más.
Primero, está muy bien aplicar ingeniosos trucos de reflexión, pero son mucho más fáciles de encontrar si ya sabes el resultado que estás buscando; así que primero derivemos mecánicamente el resultado usando funciones de generación y luego pensemos en cómo obtenerlo de manera más elegante.
Las secuencias que no cumplen el requisito constan de un segmento (posiblemente vacío) en el que está a la cabeza, seguido de un segmento (posiblemente vacío) en el que está a la cabeza. Dichos segmentos en los que la delantera no cambia se cuentan con los números catalanes, por lo que estas secuencias no válidas se cuentan mediante una convolución de los números catalanes consigo mismos (con la suma corriendo sobre el punto donde cambia la delantera). En términos de funciones generadoras, eso significa que la función generadora de las sucesiones inválidas es el cuadrado de la función generadora de los números catalanes. Con
que rinde
De este modo, es solo con el término constante eliminado y desplazado hacia abajo en uno, es decir, .
Conociendo el resultado, es un poco más fácil ver cómo aplicar la reflexión. El problema de seguir la sugerencia de Lopsy es que no es obvio cómo obtener una biyección: es fácil reflejar la parte debajo de la diagonal hacia arriba, pero no está claro qué biyección establece. Sabiendo que queremos terminar con los números catalanes uno más arriba, podemos usar la ranura adicional para hacer que la secuencia reflejada sea única: al insertar un paso hacia arriba antes del segmento reflejado y un paso hacia abajo después, obtenemos una biyección de las secuencias inválidas a las secuencias que evitan la diagonal con dos pasos más, ya que el punto de inflexión ahora está marcado únicamente como la última intersección con la diagonal en la nueva secuencia.
Esto sigue de cerca la sugerencia de Lopsy y la respuesta de Joriki. Copio aquí mi respuesta a un problema de sci.math .
Pregunta: Supongamos que hay ' ' y ' '. ¿Cuál es la relación de recurrencia para las permutaciones donde todos los subtotales que comienzan desde la izquierda no son negativos?
Respuesta: Llamemos a un arreglo de ' 'arena ' 's un paseo de tipo . Llamemos también un paseo que no tiene suma parcial negativa un paseo unilateral.
Dejar sea el número de caminatas unilaterales de tipo . Clasifiquemos estos paseos por el tipo de su subpaseo inicial más pequeño. Aquellos cuyo subpasillo inicial más pequeño es del tipo se parece a esto:
Ahora que tenemos la relación recursiva, intentemos encontrar una forma cerrada. La mejor manera es mirar la función generadora:
Respuesta a la pregunta mal leída
Al principio, interpreté mal la pregunta buscando la cantidad de juegos empatados en los que cada lado tenía la ventaja en algún momento. En caso de que esto responda alguna consulta futura, dejo esta solución, pero tenga en cuenta que no responde la pregunta realizada.
Puesto que hay paseos de tipo , restando los paseos unilaterales a ambos lados, hay
Respuesta a la pregunta formulada
La pregunta pide el número de juegos empatados donde A tiene la ventaja en algún momento y B tiene la ventaja en un punto posterior. La negación de esta condición es un juego empatado donde cualquier ventaja que tenga B es anterior a cualquier ventaja que tenga A. Así que el número de juegos que no queremos contar es
No entiendo de qué están hablando los carteles anteriores, pero creo que este problema es sencillo. Básicamente, A está a la cabeza de goles y luego B toma la delantera para el otro objetivos.
Así que la respuesta es simplemente:
dónde es el número catalán
En este caso, en realidad es mucho más fácil aplicar el doble reflejo en la pista de la pregunta que el enfoque de la función generadora en las respuestas. Si reflexiona una vez (alrededor de y=1 donde y es el déficit de objetivos entre A y B), obtiene los caminos en los que A estaba a la cabeza al menos una vez. esto te da , el término que restamos de los caminos totales para obtener los números catalanes. Pero, queremos caminos donde A estaba a la cabeza y luego, B estaba a la cabeza. Entonces, necesitamos reflexionar una vez más, esta vez sobre la línea y=-1. Cuando hacemos esto, obtenemos . Enchufar aquí y allá está tu respuesta. Vea la respuesta aquí: Caminos en una cuadrícula que no van por debajo o superior antes de llegar a su objetivo. para otra demostración de este truco de "reflexión múltiple" en acción.
Hizo
yotamoo
joriki
yotamoo