Let $\{m, n, k\}$ be positive integers. $\{k\}$ coins are placed in the squares of an $m \times n$ grid. A square may contain any number of coins, including zero. Label the $\{k\}$ coins $C_1, C_2, · · · C_k$. Let $r_i$ be the number of coins in the same row as $C_i$, including $C_i$ itself. Let $s_i$ be the number of coins in the same column as $C_i$, including $C_i$ itself. Prove that \[\sum_{i=1}^k \frac{1}{r_i+s_i} \leq \frac{m+n}{4}\]
Problem
Source: Canada Repechage 2022/8 CMOQR
Tags: repechage, inequalities
Dankster42
19.03.2022 03:08
Assume that $m$ represents the amount of rows and $n$ represents the amount of columns. We will prove the inequality for if both sides are multiplied by four. We notice by Titu's lemma:
\[\sum_{i=1}^{k} \frac{4}{r_i+s_i} = \sum_{i=1}^k \frac{(1+1)^2}{r_i+s_i} \leq \sum_{i=1}^k \frac{1}{r_i} + \frac{1}{s_i}\]Let the last expression above be $T$. We now need to prove that $T$ is less than or equal to $m+n$. For each row and column in the grid, let the number of coins in each row be $\{R_1, R_2, \ldots, R_m\}$, and let the number of coins in each column be $\{S_1, S_2, \ldots, S_n\}$. For any row $x$ with a non-zero amount of coins, where $x$ is a positive integer in $[1, m]$, each coin contributes $\frac{1}{R_x}$ to $T$, and since there are $R_x$ coins, the row contributes $R_x \frac{1}{R_x} = 1$ to $T$. In the same vein, any column $S_y$ with a non-zero amount of coins, where $y$ is a positive integer in $[1, n]$, contributes a value of $1$ to $T$. Therefore, if $R$ is a non-negative integer that represents the amount of rows that contain zero coins, and $S$ is a non-negative integer that represents the amount of columns that contain zero coins, the sum comes out to be $m-R+n-S$, which suffices the inequality $m-R+n-S \leq m+n$.