Para selecionar um recruta dentre 225 voluntários, o sargento de determinado batalhão os dispõe em um quadrado de 15 linhas por 15 colunas e, a princípio, manda sair o mais alto de

Gabarito

D

Comentário do professor

Defina: A = menor entre os máximos de cada linha; B = maior entre os mínimos de cada coluna.

Para qualquer entrada \(a_{ij}\) vale \(\min_i a_{ij}\le a_{ij}\le\max_j a_{ij}\). Tomando máximo nas colunas e mínimo nas linhas obtemos a desigualdade geral \(\displaystyle B=\max_j\!\big(\min_i a_{ij}\big)\le\min_i\!\big(\max_j a_{ij}\big)=A\). Assim, sempre \(B\le A\).

Dessa relação seguem as duas possibilidades reais: A>B (estrito) ou A=B (igualdade).

Exemplo com \(A>B\) (3×3):

[9,2,2;
2,9,2;
2,2,9] → máximos das linhas = 9,9,9 ⇒ \(A=9\); mínimos das colunas = 2,2,2 ⇒ \(B=2\).

Exemplo com \(A=B\) (2×2):

[5,1;
6,0] → máximos das linhas = 5,6 ⇒ \(A=5\); mínimos das colunas = 5,0 ⇒ \(B=5\). Aqui a mesma pessoa é tanto o mais alto de sua linha quanto o mais baixo de sua coluna (ponto de sela).