La extracción de células no duplicados en una matriz particular con las entradas repetidas

Question

Considere una junta de $ n $ x $ n $ células, donde $ n = 2k, k=2 $. Cada uno de los números del $ S = \ left \ {1, ..., \ frac {n ^ 2} {2} \ right \} $ se escribe en dos células, de modo que cada célula contiene exactamente un número.

¿Cómo puedo demostrar que los $ n $ células $ c_ {i, j} $ se puede elegir con una célula por fila y una célula por la columna de tal manera que ningún par de células contiene el mismo número.

Este fue un problema de ejemplo para un examen que estoy estudiando para. Lo he probado ahora por varias horas, pero no puedo hacerlo bien. Creo permutaciones aleatorias pueden ayudar aquí, pero no estoy seguro.

Answer 1

Escoja una permutación $ \ pi $ uniformemente al azar, y dejar que $ P = \ {a_ {i, \ pi (i)} \ mediados i \ in [n] \} $. El conjunto $ P $ contiene exactamente un elemento en cada fila y cada columna de la matriz dada $ A $.

Ahora considere cualquier par de entradas en $ A $ con el mismo valor. Si esos dos entradas se encuentran en la misma fila o columna de la misma, no pueden ser a la vez en $ P $. Si esos dos entradas están en diferentes filas y columnas de $ A $, entonces la probabilidad de que ambas entradas se encuentran en $ P $ es exactamente $ 1 / n (n-1) $.

Hay $ n ^ 2/2 $ diferentes valores en la matriz. Así que el número esperado de valores con las dos entradas en $ P $ es como máximo $ n ^ 2 / 2n (n-1) = n / 2 (n-1) $. Si $ n \ ge $ 4, este valor esperado es menos de $ 1 $, lo que implica que la probabilidad de elegir no los correspondientes pares debe ser positivo.

Answer 2

Hay $ n! $ Maneras de elegir las células. El número de diferentes formas posibles de la elección de las células de tal manera que tenemos por lo menos dos células con el mismo contenido es a lo sumo $ n \ cdot (n-2)! $. Por $ n \ ge $ 4, este número siempre satisface $ n! \ Gt n \ cdot (n-2)! $, Por lo que por el principio del palomar siempre hay algunas selecciones con números distintos.

---

¿Por qué?

En primer lugar $ n $ es obvio, todo permutations.But $ n \ cdot (n-2) $: toman una de un elementos de la primera columna, se presupone que desea tener un duplicado de este elemento, puede seleccionar en a lo sumo $ n $ manera diferente (demostrar por qué en la mayoría). Encuentra otra columna que tiene un mismo elemento, (si hay una columna con este tema en fila diferente), corrección de esa columna, todas las demás columnas tener $ (n-2)! $ Permutaciones posibles, también presente en dos columnas fijas tendrán por lo más $ n $ permutación, por lo que en total maneras posibles es $ n \ cdot (n-2)! $.