Question

Una partícula se mueve en el plano cartesiano de un punto reticular a otro según las siguientes reglas:

• Desde cualquier punto reticular $(a, b),$ la partícula solo puede moverse a $(a+1, b),$ $(a, b+1),$ o $(a+1, b+1).$

• No hay giros en ángulo recto en la trayectoria de la partícula. Es decir, la sucesión de puntos visitados no contiene ni una subsucesión de la forma $(a, b),$ $(a+1, b),$ $(a+1, b+1)$ ni una subsucesión de la forma $(a, b),$ $(a, b+1),$ $(a+1, b+1).$

¿Cuántas trayectorias diferentes puede tomar la partícula desde $(0, 0)$ hasta $(5, 5)$ ?

A particle moves in the Cartesian plane from one lattice point to another according to the following rules:

• From any lattice point $(a, b),$ the particle may move only to $(a+1, b),$ $(a, b+1),$ or $(a+1, b+1).$

• There are no right angle turns in the particle's path. That is, the sequence of points visited contains neither a subsequence of the form $(a, b),$ $(a+1, b),$ $(a+1, b+1)$ nor a subsequence of the form $(a, b),$ $(a, b+1),$ $(a+1, b+1).$

How many different paths can the particle take from $(0, 0)$ to $(5, 5)?$

Respuesta

Solución:

Los giros en ángulo recto prohibidos dicen exactamente que un paso hacia la derecha nunca puede seguir inmediatamente a un paso hacia arriba, y viceversa; un paso diagonal puede seguir o preceder a cualquier cosa. Así que en cada punto reticular $(x, y)$ lleve tres conteos $D(x,y),$ $R(x,y),$ $U(x,y):$ los números de trayectorias válidas desde $(0,0)$ que llegan ahí por un paso diagonal, hacia la derecha o hacia arriba. Las reglas dan $\begin{aligned} &D(x,y) = D + R \\ &\quad {}+ U \text{ at } (x-1, y-1), \\ &R(x,y) = D(x-1,y) \\ &\quad {}+ R(x-1,y), \\ &U(x,y) = D(x,y-1) \\ &\quad {}+ U(x,y-1). \end{aligned}$

Partiendo de la única trayectoria vacía en $(0,0)$ (que puede comenzar con cualquier paso), complete la cuadrícula hasta $(5,5).$ A lo largo de los ejes solo sobreviven las trayectorias todas hacia la derecha o todas hacia arriba, y el interior se acumula rápidamente; en $(5, 5)$ los tres conteos resultan $27,$ $28,$ y $28.$

El número total de trayectorias es $27 + 28 + 28 = 83.$

The forbidden right-angle turns say exactly that a rightward step may never immediately follow an upward step, and vice versa; a diagonal step may follow or precede anything. So at each lattice point $(x, y)$ track three counts $D(x,y),$ $R(x,y),$ $U(x,y):$ the numbers of legal paths from $(0,0)$ arriving there by a diagonal, rightward, or upward step. The rules give $\begin{aligned} &D(x,y) = D + R \\ &\quad {}+ U \text{ at } (x-1, y-1), \\ &R(x,y) = D(x-1,y) \\ &\quad {}+ R(x-1,y), \\ &U(x,y) = D(x,y-1) \\ &\quad {}+ U(x,y-1). \end{aligned}$

Starting from the single empty path at $(0,0)$ (which may begin with any step), fill in the grid up to $(5,5).$ Along the axes only all-rightward or all-upward paths survive, and the interior builds up quickly; at $(5, 5)$ the three counts come out to $27,$ $28,$ and $28.$

The total number of paths is $27 + 28 + 28 = 83.$

2005 AIME I Problema 13

Solución:

El Problema 13 en otros años