Question

En un juego de Chomp, dos jugadores se turnan para dar mordiscos a una cuadrícula de $5$ por $7$ cuadrados unitarios. Para dar un mordisco, un jugador elige uno de los cuadrados restantes y luego elimina (“come”) todos los cuadrados del cuadrante definido por el borde izquierdo del cuadrado elegido, prolongado hacia arriba, y su borde inferior, prolongado hacia la derecha. Por ejemplo, el mordisco determinado por el cuadrado sombreado del diagrama eliminaría ese cuadrado y los cuatro cuadrados marcados con $\times.$ (Los cuadrados con dos o más bordes punteados fueron eliminados del tablero original en jugadas anteriores.)

El objetivo del juego es obligar al oponente a dar el último mordisco. El diagrama muestra uno de los muchos subconjuntos del conjunto de $35$ cuadrados unitarios que pueden aparecer durante una partida de Chomp. ¿Cuántos subconjuntos distintos hay en total? Incluye en el conteo el tablero completo y el tablero vacío.

In a game of Chomp, two players alternately take bites from a $5$ -by- $7$ grid of unit squares. To take a bite, a player chooses one of the remaining squares, then removes (“eats”) all squares in the quadrant defined by the left edge (extended upward) and the lower edge (extended rightward) of the chosen square. For example, the bite determined by the shaded square in the diagram would remove the shaded square and the four squares marked by $\times.$ (The squares with two or more dotted edges have been removed from the original board in previous moves.)

The object of the game is to make one’s opponent take the last bite. The diagram shows one of the many subsets of the set of $35$ unit squares that can occur during the game of Chomp. How many different subsets are there in all? Include the full board and empty board in your count.

Respuesta

Respuesta: 792

Conceptos:caminos reticulares combinaciones subconjuntos

Nivel de dificultad: 2320

Pista pequeña:

Un conjunto alcanzable queda determinado por alturas de columnas no crecientes entre $0$ y $5$

A reachable set is determined by nonincreasing column heights between $0$ and $5$

Pista grande:

Codifica el borde de tal conjunto como un camino reticular con $5$ pasos verticales y $7$ horizontales

Encode the boundary of such a set as a lattice path with $5$ vertical and $7$ horizontal steps

Solución:

Después de cualquier sucesión de mordiscos, los cuadrados restantes forman un conjunto cerrado hacia abajo y hacia la izquierda: las alturas de las siete columnas son enteros no crecientes entre $0$ y $5.$ Recíprocamente, todo borde de este tipo puede producirse y corresponde a un camino reticular a través de un rectángulo de $5$ por $7$ . Cada camino consta de $5$ pasos verticales y $7$ horizontales, así que el número de estados, incluidos el completo y el vacío, es $\binom{12}{5}=792.$

After any sequence of bites, the remaining squares form a lower-left order ideal: the seven column heights are nonincreasing integers between $0$ and $5.$ Conversely, every such boundary can be produced and corresponds to a lattice path across a $5$ -by- $7$ rectangle. Each path consists of $5$ vertical and $7$ horizontal steps, so the number of states, including full and empty, is $\binom{12}{5}=792.$

1992 AIME Problema 12

Respuesta: 792

Nivel de dificultad: 2320

Pista pequeña:

Pista grande:

Solución:

El Problema 12 en otros años