Problem 1513

1. Define the necessary quantities:
- Let $\mathbb{I}$ be a non-empty subset of $\mathbb{Z}$.
- Let $f$ and $g$ be two functions defined on $\mathbb{I}$.
- Define $m$ as the number of pairs $(x, y)$ for which $f(x) = g(y)$.
- Define $n$ as the number of pairs $(x, y)$ for which $f(x) = f(y)$.
- Define $k$ as the number of pairs $(x, y)$ for which $g(x) = g(y)$.

2. Introduce the notation for counting values:
- For each $t$, let $n_f(t)$ be the number of values of $x$ for which $f(x) = t$.
- Similarly, let $n_g(t)$ be the number of values of $y$ for which $g(y) = t$.

3. **Express $m$, $n$, and $k$ in terms of these counts:**
- $m = \sum_t n_f(t) n_g(t)$
- $n = \sum_t n_f(t)^2$
- $k = \sum_t n_g(t)^2$

4. Use the Cauchy-Schwarz inequality:
- The Cauchy-Schwarz inequality states that for any sequences of real numbers $a_i$ and $b_i$,
$$\left( \sum_i a_i b_i \right)^2 \leq \left( \sum_i a_i^2 \right) \left( \sum_i b_i^2 \right)$$
- In our case, let $a_i = n_f(t)$ and $b_i = n_g(t)$. Then,
$$\left( \sum_t n_f(t) n_g(t) \right)^2 \leq \left( \sum_t n_f(t)^2 \right) \left( \sum_t n_g(t)^2 \right)$$

5. Apply the inequality to our problem:
- Substituting the expressions for $m$, $n$, and $k$, we get:
$$m^2 \leq n \cdot k$$
- Taking the square root of both sides, we obtain:
$$m \leq \sqrt{n \cdot k}$$

6. Strengthen the inequality:
- Since $\sqrt{n \cdot k} \leq \frac{n + k}{2}$ (by the arithmetic mean-geometric mean inequality), we have:
$$m \leq \frac{n + k}{2}$$
- Multiplying both sides by 2, we get:
$$2m \leq n + k$$

Thus, we have shown that $2m \leq n + k$.

$\blacksquare$