Barajar las cartas y colocarlas en orden

Question

Los números del 1 al 50 están impresos en tarjetas. Las cartas se barajan y se colocan boca arriba en 5 filas de 10 cartas cada una. Las cartas de cada fila se reordenan para que aumenten de izquierda a derecha. Las Las cartas de cada columna se reordenan para que aumenten de de arriba a abajo. En la disposición final, ¿las cartas de las filas siguen aumentando de izquierda a derecha?

-De la Olimpiada Matemática Canadiense de 1980

He jugado con algunos casos y la disposición final parecía aumentar de izquierda a derecha, pero ¿hay alguna forma de probar/desmentir si esto será siempre así? He buscado en Internet pero no he encontrado ninguna solución.

Answer 1

Para $r=1,2,3,4,5$ y $c=1,2,\ldots,10$ dejar $n_{r,c}$ sea el número de la fila $r$ , columna $c$ después de la primera reordenación, de modo que $n_{r,c}<n_{r,c+1}$ para $r=1,\ldots,5$ y $c=1,\ldots,9$ . Sin pérdida de generalidad podemos suponer que la primera columna está en orden ascendente de arriba a abajo, por lo que $n_{r,1}<n_{r+1,1}$ para $r=1,2,3,4$ Si no es así, intercambia filas enteras hasta que lo sea.

Supongamos ahora que $n_{r,2}>n_{s,2}$ para algunos $r,s$ tal que $r>s$ . Para $c=2,\ldots,10$ cambiar las tarjetas $n_{r,c}$ y $n_{s,c}$ ; $n_{r,1}<n_{s,1}<n_{s,2}$ et $n_{s,1}<n_{s,2}<n_{r,2}$ , de modo que cada fila de la matriz sigue aumentando de izquierda a derecha. Repite esta maniobra tantas veces como sea necesario para que la columna $2$ en orden ascendente de arriba a abajo.

Continúa de forma similar reparando una columna cada vez, trabajando de izquierda a derecha, asegurándote de que cuando intercambias dos elementos en una columna, intercambias los elementos correspondientes en cada columna a la derecha. Después de cada intercambio de este tipo, cada fila sigue aumentando de izquierda a derecha, por lo que este seguirá siendo el caso al final, cuando cada columna se haya ordenado en orden creciente de arriba a abajo.