在具有重复条目的特定矩阵中提取非塑料单元格

Question

考虑一个$ n $ x $ n $单元的板，其中$ n = 2k，k≥2$。来自$ s = left {1，...， frac {n^2} {2} {2} right } $的每个数字都写入两个单元格，以便每个单元格完全包含一个数字。

我如何表明$ n $ cell $ c_ {i，j} $可以用每个行一个单元格和每个列的一个单元格选择，从而使得没有一对单元格包含相同的数字。

这是我正在研究考试的示例问题。我现在尝试了几个小时，但我无法做对。我认为随机排列可以在这里提供帮助，但我不确定。

Answer 1

随机选择一个置换$ pi $，然后让$ p = {a_ {i， pi（i）} mid i in [n] } $。集合$ p $在每一行中完全包含一个元素和给定矩阵$ a $的每一列。

现在考虑具有相同值的$ A $中的任何一对条目。如果这两个条目位于同一行或同一列中，则它们都不能在$ p $中。如果这两个条目在$ a $的不同行和列中，则两个条目在$ p $中的概率正好为$ 1/n（n-1）$。

矩阵中有$ n^2/2 $不同的值。因此，$ p $中两个条目的预期值数量最多为$ n^2/2n（n-1）= n/2（n-1）$。如果$ n ge 4 $，则此预期价值小于$ 1 $，这意味着选择的可能性 不 匹配对必须是正面的。

Answer 2

有$ n！$选择单元格的方法。选择单元格的不同可能方法的数量，使我们至少有两个具有相同内容的单元格是$ n cdot（n-2）！$。对于$ n ge 4 $，此数字总是满足$ n！ gt n cdot（n-2）！$，因此，根据鸽子洞原理，总有一些不同的数字选择。

---

为什么？

第一个$ n！$很明显，所有排列。但是$ n cdot（n-2）！$：拿起第一列中的一个项目之一，假设您要对此项目进行重复大多数$ n $不同的方式（最多证明原因）。找到具有相同项目的另一列（如果在不同行中有一列），修复该列，所有其他具有$（n-2）！$的其他列，此两个固定列也将在大多数$ n $排列，因此总可能的方法是$ n cdot（n-2）！$。