This is problem 2.2 from Junka's Extremal Combinatorics. The problem is as follows:
Let $A=(a_{ij})$ be an $n \times n$ matrix with $n \geq 4$. The matrix is filled with integers, and each integer appears exactly twice. Show that there exists a permutation $\pi$ of $\{1,2,\dots,n\}$ such that all the numbers $a_{i,\pi(i)}$, for $i=1,2,\dots,n$, are distinct.
Here is my attempt: There are $n!$ total permutations. Since each element appears exactly twice in $A$, there are (at most) $n^2/2$ pairs of positions in the matrix that are forbidden for our permutation. By the principle of inclusion-exclusion, we are interested in $$n! - \frac{n^2}{2}(n-2)! + \frac{1}{2} \frac{n^2}{2} \frac{(n-2)^2}{2}(n-4)! - \dots $$ $$\geq n! - \frac{n^2}{2}(n-2)!$$ But $n! > \frac{n^2}{2}(n-2)!$ when $n>2$, so we are done.
Is this correct? Something seems off, though I am unable to point it. Besides, PIE is covered only in the next chapter, so is there a nice proof of this using just double-counting?
Here's a more formal proof.
Let $H=\{\{(i,k),(j,l)\}, a_{ik} = a_{jl}\}$ be the unordered pairs of indices which correspond to duplicates in the matrix. Since the matrix has $n^2$ entries and each of them appears exactly twice, $|I|=\frac{n^2}2$.
For $\{(i,k),(j,l)\}\in H$ define $A_{\{(i,k),(j,l)\}}=\{\pi \in \mathcal S_n, \pi(i) = k \text{ and } \pi(j) = l\}$.
Note that if $\mathbf {i\neq j}$, $|A_{\{(i,k),(j,l)\}}| = (n-2)!$
The standard union bound (i.e. $|\cup_i B_i|\leq \sum_i |B_i|$, which follows from trivial induction on the number of sets) yields $$\left|\bigcup_{\substack{\{(i,k),(j,l)\}\in H,\\ \mathbf{i\neq j}} }A_{\{(i,k),(j,l)\}} \right|\leq |\{\{(i,k),(j,l)\}\in H, \mathbf{i\neq j} \}|\cdot (n-2)!$$
Next, $|\{\{(i,k),(j,l)\}\in H, i\neq j \}|\cdot (n-2)!\leq |\{\{(i,k),(j,l)\}\in H \}|\cdot (n-2)!\leq \frac{n^2}2 (n-2)!$
It is trivial that for $n>2$, $\frac{n^2}2 (n-2)! < n!$, thus $$\left|\bigcup_{\substack{\{(i,k),(j,l)\}\in H,\\ i\neq j} }A_{\{(i,k),(j,l)\}} \right|<n!$$
Thus there exists $\pi\in \bigcap_{\substack{\{(i,k),(j,l)\}\in H,\\ i\neq j} }A_{\{(i,k),(j,l)\}}^c$.