Prueba de Selección de Equipos de Alemania 2007 Problema 2
2 Un pastel tiene la forma de un cuadrado de $ n$ x $ n$ compuesto por $ n^{2}$ cuadrados unitarios. Hay fresas sobre algunos de los cuadrados unitarios de modo que cada fila o columna contiene exactamente una fresa; llame a este arreglo $\mathcal{A}$ . Sea $\mathcal{B}$ otro arreglo de este tipo. Suponga que todo rectángulo de la cuadrícula con un vértice en la esquina superior izquierda del pastel no contiene menos fresas del arreglo $\mathcal{B}$ que del arreglo $\mathcal{A}$ . Demuestre que el arreglo $\mathcal{B}$ se puede obtener de $ \mathcal{A}$ realizando un número de intercambios, definidos de la siguiente manera: Un intercambio consiste en seleccionar un rectángulo de la cuadrícula con solo dos fresas, situadas en su esquina superior derecha y en su esquina inferior izquierda, y mover estas dos fresas a las otras dos esquinas de ese rectángulo.
0
0
Inicia sesión para agregar soluciones y pistas