Motivación para esta solución a un problema olímpico británico.

Question

Me estaba haciendo la pregunta 6 de este BMO1 de papel: https://bmos.ukmt.org.uk/home/bmo1-2019.pdf y no he podido conseguirlo. Entonces miré en la solución y encontré la solución. Puedo ver cómo funciona la solución, pero hay un paso que no puedo ver cómo alguien hubiera pensado que lo han intentado. Yo estoy tratando de mejorar para resolver el problema, entonces, me gustaría saber cómo iba yo a suponer que pensar en algo como eso.

Ada la hormiga comienza en un punto de $O$ sobre un plano. Al inicio de cada minuto que ella elige el Norte, el Sur, el Este o el Oeste, y las marchas $1$ metros en esa dirección. Al final de la $2018$ minutos ella se encuentra de vuelta en $O$. Deje $n$ el número de posibles viajes que ella podría haber hecho. Cuál es la potencia máxima de $10$ que se divide $n$.

(LEER toda la PREGUNTA ANTES de IR A VIDEO) Aquí está el video de la solución: https://bmos.ukmt.org.uk/solutions/bmo1-2019/ El paso que estoy confundido acerca de cómo alguien podría pensar que es la parte en 4:15 en la solución de vídeo. Cómo es que alguien destinado a pensar en la creación de un nuevo conjunto de coordenadas ((x + y), (x - y))? No puedo ver cómo le iba a dar ese salto, o incluso pensar que probarlo. Si usted desea para tratar el problema por sí mismo en primer lugar, tal vez usted será más capaz de explicarme cómo se dieron cuenta de que usted necesita para hacer que paso, sin embargo si lo desea, puede simplemente mirar el video de la solución.

Answer 1

La solución de vídeo es muy inteligente, pero también puede resolver el problema por sólo penosamente a lo largo de. Como el presentador dijo al principio, tenemos que elegir a $2k$ este-oeste se mueve, $k$ de los cuales serán del oeste y, a continuación, tenemos que elegir a $1009-k$ norte se mueve. El resto de los $1009-k$ movimientos serán sur. Esto le da $$ n=\sum_{k=0}^{1009}{2018\elija k}{2018 -k\elegir k}{2018-2k\choose1009-k}$$ possible paths. Let's try to simplify this before giving up. We have $$\begin{align} n&=\sum_{k=0}^{1009}{2018!\over k!(2018-k)!}{(2018-k)!\over k!(2018-2k)!}{(2018-2k)!\over (1009-k)!(1009-k)!}\\&=\sum_{k=0}^{1009}{2018!\over k!(1009-k)!k!(1009-k)!}\\&={2018!\over 1009!1009!}\sum_{k=0}^{1009}\left({1009!\over k!(1009-k)!}\right)^2\\&={2018\choose 1009}\sum_{k=0}^{1009}{1009\choose k}^2\end{align}$$

Hasta aquí, creo que es bastante sencillo. Los factores de $k!(1009-k)!$ debe sugerir tratando de expresar las cosas en términos de ${1009\choose k}$. Ahora viene un truco, Vandermonde de la identidad. Incluso si usted no recuerda exactamente lo que dice, si alguna vez has visto la prueba, usted debe ser capaz de recrear la fórmula. $$ \sum_{k=0}^{1009}{1009\elija k}^2=\sum_{k=0}^{1009}{1009\elija k}{1009\elegir 1009-k}={2018\elegir 1009}$$ The last equality comes because to choose $1009$ elements from a collection of $2018$ we can choose $k$ from the first $1009$ and the remaining $1009-k$ from the second $1009.$

Poniendo todo junto, tenemos $$n={2018\choose1009}^2$$

No estoy en absoluto inteligente, así es como yo lo hice.

Answer 2

Usted puede simplemente contar cómo muchos de los posibles caminos que la hormiga puede tomar suponiendo hace $k$ pasos al este y $k$ hacia el oeste, a continuación, decidir el orden de los este-oeste de las rutas, de manera similar a aquellos de la norte-sur ($1009-k$) y, finalmente, decidir cómo mezclar ambas secuencias. Todo lo que se puede por lo tanto ser expresada en términos de los coeficientes binomiales: $$\sum_{k=0}^{N}C_k^{2k}C_{N-k}^{2N-2k}C_{2k}^{2N}=\sum_{k=0}^{N}\frac{(2k)!}{(k!)^2}\frac{(2N-2k)!}{((N-k)!)^2}\frac{(2N)!}{(2k)!(2N-2k)!}$$ $$=\sum_{k=0}^{N}\frac{(2N)!}{(k!)^2((N-k)!)^2}$$ $$=\frac{(2N)!}{(N!)^2}\sum_{k=0}^{N}\left(C_N^k\right)^2=\left(C_{2N}^N\right)^2$$ donde $N=1009$.

A continuación, puede calcular el $2$- e $5$-ádico valoraciones con la fórmula habitual:

$$\nu_p(A!)=\left\lfloor A/p \right\rfloor + \left\lfloor A/p^2 \right\rfloor + \ldots $$

Así:

$$\nu_5(2018!)=502, \nu_5(1009!)=250$$ $$\nu_2(2018!)=2011, \nu_2(1009!)=1002$$

Así que el mayor poder es $10^4$.

Answer 3

Sólo traté de resolver el problema en mi cabeza, y pensó en el cambio de coordenadas truco dentro de un minuto o dos (punto en el que me detuve, sabiendo que es sólo el cálculo a partir de ahí).

Para responder a su pregunta de "¿cómo hace uno para venir para arriba con él", voy a tratar de volver a trazar el proceso intuitivo en mi mente. Pensé que más o menos la siguiente:

"OK, así que un punto en el plano Euclidiano es descrito por un par de números (sus coordenadas). Así que una ruta es una secuencia de pares de números. En realidad, parece que la coordenada x y la coordenada y no interactúan en todos aquí - así que también podría codificar rutas de pares de secuencias de números.

OK, ahora ¿cuáles son las condiciones precisas que tal un par de secuencias de números deben cumplir para proporcionar una solución?

Respuesta: $((x_1, \ldots, x_{2018}), (y_1, \ldots, y_{2018}))$ válida es par si y sólo si cada término de cada secuencia es $-1$, $0$o $1$, la suma de cada secuencia es $0$, y, para cada $i$, $x_i$ e $y_i$ nunca son simultáneamente cero exactamente uno de $x_i$ e $y_i$ es distinto de cero.

Dang! de hecho, resulta que las dos secuencias de hacer interactuar - y en un lugar sucio camino. Esta última condición parece difícil tomar en cuenta a la hora de resolver el problema.

Así que vamos a empezar por resolver un problema más sencillo, que consta de dos copias independientes de la uno-dimensional versión de este problema: por lo dejemos $x_i$ e $y_i$ tomar solamente los valores de $\pm 1$, pero con las cuatro combinaciones permitidas.

Oh, espera --- pero en realidad este es el mismo como el problema original, sólo girado 45 grados (y reescalado)! Así que aquí estamos."

Answer 4

Una buena idea para cuando no sepa cómo empezar una combinatoria problema que se le pide calcular algo por un muy alto número entero (en este caso, 2018) es calcular algunos casos pequeñas y buscar un patrón. Para empezar en esto, tenga en cuenta que el número de caminos de longitud $n$ a cualquier punto dado es la suma de caminos de longitud $n-1$ a la vecina puntos. Esto hace que sea fácil de calcular pequeño casos:

n=0                         
                1           
n=1                         
                1           
            1       1       
                1           
n=2                         
                1           
            2       2       
        1       4       1   
            2       2       
                1           
n=3                         
                1           
            3       3       
        3       6       3   
    1       6       6       1
        3       6       3   
            3       3       
                1            

Ver el patrón todavía? Los bordes de las filas del triángulo de Pascal, y el interior de las diagonales son sólo múltiplos de la misma fila del triángulo de Pascal. Demostrar mediante la inducción. El centro del elemento (para los números de $n$ de pasos) será sólo el cuadrado de la central de coeficiente binomial $\binom{n}{n/2}^2$. Evaluar el patrón de $n=2018$, busque el más alto poder de $5$, y ya tienes tu respuesta.

Veo mención de un cambio de coordenadas en varias respuestas y comentarios. En las fotos anteriores, es claro el por qué de que podría ser una buena idea. Sin embargo, creo que, realmente, no es necesario una vez que vea el patrón.

---

Comentario: Desde el OP está interesado en estrategias de resolución de problemas, una menor metaprinciple me gustaría mencionar es que los coeficientes binomiales y el triángulo de Pascal subido mucho en celosía problemas de ruta de acceso, por lo que es recomendable que se espera de ellos. Otro cuidada ejemplo (en realidad dos ejemplos, que estrechamente relacionados entre sí) son los números de catalán y Bertrand de la boleta teorema, que yo recomendaría estudiar para cualquier persona interesada en la competencia matemática.