Estrazione di cellule non duplicati in una particolare matrice con voci ripetute

Question

Si consideri una scheda di $ n $ x $ n $ cellule, dove $ n = 2k, k=2 $. Ognuno dei numeri da $ S = \ left \ {1, ..., \ frac {n ^ 2} {2} \ right \} $ è scritto a due cellule in modo che ogni cellula contiene esattamente un numero.

Come faccio a dimostrare che $ n $ cellule $ c_ {i, j} $ può essere scelto con una cella per riga e una cella per ogni colonna in modo tale che nessuna coppia di celle contiene lo stesso numero.

Questo è stato un problema ad esempio per un esame sto studiando per. Ho provato ora per diverse ore, ma non riesco a farlo bene. Penso permutazioni casuali possono aiutare qui, ma non sono sicuro.

Answer 1

Scegli una permutazione $ \ pi $ uniformemente a caso, e lasciare che $ P = \ {a_ {i, \ pi (i)} \ metà i \ in [n] \} $. Il set $ P $ contiene esattamente un elemento in ogni riga e ogni colonna della proposta matrice $ A $.

Ora consideriamo una qualsiasi coppia di voci in $ A $ con lo stesso valore. Se queste due voci trovano nella stessa riga o colonna stessa, non possono essere sia in $ P $. Se queste due voci sono in diverse righe e colonne di $ A $, allora la probabilità che entrambe le voci si trovano in $ P $ è esattamente $ 1 / n (n-1) $.

Ci sono $ n ^ 2/2 $ valori diversi nella matrice. Così il numero atteso di valori con entrambe le voci in $ P $ è al più $ n ^ 2 / 2n (n-1) = n / 2 (n-1) $. Se $ n \ ge 4 $, questo valore atteso è inferiore a $ 1 $, il che implica che la probabilità di scegliere non accoppiamenti deve essere positivo.

Answer 2

Ci sono $ n! $ Modi per scegliere le cellule. Il numero di modi diversi possibili della scelta di cellule tale che abbiamo almeno due celle con lo stesso contenuto è al massimo $ n \ cdot (n-2)! $. Per $ n \ ge 4 $, questo numero sempre soddisfa $ n! \ Gt n \ cdot (n-2)! $, Quindi dal principio dei cassetti ci sono sempre alcune selezioni con numeri distinti.

---

Perché?

In primo luogo $ n $ è ovvio, tutti permutations.But $ n \ cdot (n-2) $: prendere uno dei pochi elementi dalla prima colonna, presuppongono che vuole avere un duplicato di questo elemento, è possibile selezionare in al massimo $ n $ modo diverso (dimostrare il motivo per cui al massimo). Trova un'altra colonna che ha uno stesso oggetto, (se c'è una colonna con questo elemento in diversi fila), correzione della colonna, tutte le altre colonne con $ (n-2)! $ Permutazioni possibili, anche questo a due colonna fissa avranno a più $ n $ permutazione, in modo totale i modi possibili è $ n \ cdot (n-2)! $.