Problema matemático del concurso acerca de tachar números en la tabla

Question

Una tabla de $n\times n$ está lleno de pares de diferentes números naturales. Ann y Ben son del siguiente juego: Ann elige el número más grande, luego cruza la fila y la columna que contiene. Ella, a continuación, elige el mayor número de lo que se quedó y se repite todo el proceso, a menos que la tabla está atravesado por completo.

Ben lleva exactamente la misma tabla, y se repite el mismo proceso, pero la elección de la menos cantidad en cada paso.

Tenemos que mostrar que la suma de $A$ de los números elegidos por Ann es mayor (o igual) a la suma de $B$ de los números elegidos por Ben.

Creo que debe ser realizado a través de la presentación de dichas $C$ que $A\geq C\geq B$. Sin embargo, si $a_i$ e $b_i$ son los números elegidos por Ann y Ben en $i$-ésimo paso, respectivamente, la desigualdad de $a_i\geq b_{n-i+1}$ no posee. Por lo tanto, estoy atascado en este punto.

Answer 1

Deje $a_1,a_2\dots a_n$ ser los números seleccionados por Ann y $b_1,b_2,\dots b_n$ ser los números seleccionados por Benjamin.

Lema: $a_i\geq b_{n+1-i}$ para todos los $1\leq i \leq n$.

Prueba: Consideremos el conjunto $A$ de todos los números que fueron elegibles cuando hemos seleccionado $a_i$ y el conjunto de $B$ de todos los números elegibles cuando hemos seleccionado $b_{n+1-i}$. Observe que estos dos conjuntos se intersecan (debido a $n-i+1$ filas son elegibles en $A$ e $i$ filas son elegibles en $B$, y lo mismo sucede con las columnas) así que la afirmación es verdadera, ya que $a_i=\max(A)$ e $b_i=\min B$.

El problema se sigue del lema:

$\sum\limits_{i=1}^n a_i \geq \sum\limits_{i=1}^n b_{n+1-i} = \sum\limits_{i=1}^n b_i$

Answer 2

Y, de hecho, para agregar a @Jorge de la respuesta estricta desigualdad no es siempre posible: Para cualquier entero $n$ hay $n \times n$ tablas de $A$ que la fuerza del Jugador a y el Jugador B tiene la misma suma: Vamos a $A$ ser cualquier $n \times n$ tabla donde las entradas se hacen más grandes a medida que la cabeza hacia abajo de una columna, y a la derecha en una fila: por ejemplo, $A =[a_{ij}]$ donde la $ij$-ésima es $i(n+1) + j$. [Tenga en cuenta que todas las entradas de $A$ son distintos.] A continuación, tanto el Jugador a y el Jugador B se eligen los elementos de la diagonal de a$A$: el Jugador a va a terminar de recoger las diagonales de sureste a noroeste al Jugador B, de noroeste a sureste.