Question

Hay una colección de $25$ fichas blancas indistinguibles y $25$ fichas negras indistinguibles. Halla el número de maneras de colocar algunas de estas fichas en una cuadrícula de $5 \times 5$ de modo que:

• cada celda contenga a lo sumo una ficha

• todas las fichas de una misma fila y todas las fichas de una misma columna tengan el mismo color, y

• cualquier ficha adicional colocada en la cuadrícula violaría una o más de las dos condiciones anteriores.

There is a collection of $25$ indistinguishable white chips and $25$ indistinguishable black chips. Find the number of ways to place some of these chips in a $5 \times 5$ grid such that:

• each cell contains at most one chip

• all chips in the same row and all chips in the same column have the same color, and

• any additional chip placed on the grid would violate one or more of the previous two conditions.

Respuesta

Solución:

En una colocación válida, cada fila no vacía tiene un solo color, e igualmente cada columna. Si alguna fila estuviera vacía, elige cualquier celda de ella: una ficha del color de la columna de esa celda (cualquier color si la columna también está vacía) podría añadirse legalmente, contradiciendo la tercera condición. Así que cada fila y cada columna es no vacía, y podemos hablar de su color.

Una ficha en una celda obliga a que los colores de su fila y su columna coincidan; recíprocamente, si una fila y una columna comparten color pero su celda común está vacía, se podría añadir una ficha de ese color. Por lo tanto las fichas ocupan exactamente las celdas cuyo color de fila es igual al color de columna. Para que cada fila sea no vacía, el color de cada fila debe aparecer entre los colores de columna, y viceversa: las filas y las columnas usan el mismo conjunto de colores. Cualquier coloración de este tipo produce recíprocamente una colocación maximal válida (a lo sumo $25$ celdas contienen fichas de cada color, así que el suministro alcanza), y coloraciones distintas dan colocaciones distintas.

Contando las coloraciones: todas las filas y columnas blancas, todas negras, o ambos colores usados por las filas y por las columnas: $1 + 1 + (2^5 - 2)^2 = 2 + 900$ $= 902.$

In a valid placement, each nonempty row has a single color, and likewise each column. If some row were empty, choose any cell of it: a chip of the color of that cell's column (either color if the column is also empty) could legally be added, contradicting the third condition. So every row and every column is nonempty, and we may speak of its color.

A chip at a cell forces its row and column colors to agree; conversely, if a row and a column share a color but their common cell is empty, a chip of that color could be added. Hence chips occupy exactly the cells whose row color equals the column color. For every row to be nonempty, each row's color must appear among the column colors, and vice versa — the rows and the columns use the same set of colors. Any such coloring conversely yields a valid maximal placement (at most $25$ cells hold chips of each color, so the supply suffices), and distinct colorings give distinct placements.

Counting the colorings: all rows and columns white, all black, or both colors used by the rows and by the columns: $1 + 1 + (2^5 - 2)^2 = 2 + 900$ $= 902.$

2024 AIME II Problema 9

Solución:

El Problema 9 en otros años