Encontrei uma solução para o problema da suruba, mas não está muito elegante. Vou postar pra ver se ajuda alguém a encontrar uma melhor:
O problema fala de uma relação entre o conjunto H, dos homens, e o conjunto M, das mulheres. Essa relação pode ser representada pela matriz R, tendo os homens h1, h2, h3, ... hx como colunas e as mulheres m1, m2, m3, ... my como linhas, sendo x e y os cardinais dos conjuntos H e M, respectivamente. Quando mi transa com hj, o elemento Rij da matriz vale 1, em caso contrário vale 0. Os conjuntos H e M não são ordenados, por isso podemos trocar as linhas de posição à vontade; o mesmo vale para as colunas.
Queremos provar que existem a, b, c e d, com a e b entre 1 e y, e c e d entre 1 e x, tais que Rac = 1, Rad = 0, Rbc = 0 e Rbd = 1. (Hipótese)
Como toda mulher transa com pelo menos um homem, toda linha da matriz tem pelo menos um elemento com valor 1; como nenhum homem transa com todas as mulheres, toda coluna da matriz tem pelo menos um elemento com valor 0. (Condições)
Escolhamos um elemento de valor 1 da matriz. Chamemos de L1 e C1 à linha e à coluna onde ele se encontra. Sabemos que na mesma coluna deve haver um elemento de valor 0. Chamemos de L2 à linha onde este se encontra. Sabemos que em L2 deve haver pelo menos um elemento de valor 1; chamemos de C2 à coluna onde ele se encontra. Agora, se o elemento em (L1,C2) valer 0, a afirmativa da hipótese é verdadeira. Veja abaixo:
Situação 1:
R
| 1 0 |
| 0 1 |
R11 = 1, R21 = 0, R22 = 1, R12 = 0
Hipótese verificada (linhas 1 e 2, colunas 1 e 2)
Situação 2:
R
| 1 1 |
| 0 1 |
R11 = 1, R21 = 0, R22 = 1, R12 = 1
Hipótese não verificada
Mas, se R12 valer 1, temos 2 elementos de valor 1 na coluna C2, portanto deve haver um elemento de valor 0 na mesma coluna. Chamemos de L3 à linha onde ele se encontra. Sabemos que deve existir pelo menos um elemento de valor 1 nessa linha. Chamemos de C3 à coluna onde ele se encontra. Agora, se tivermos valor 1 em (L2,C3), confirma-se a hipótese:
Situação 2:
R
| 1 1 X |
| 0 1 0 |
| X 0 1 |
R11 = 1, R21 = 0, R22 = 1, R12 = 1, R32 = 0, R33 = 1, R23 = 0
Hipótese verificada (linhas 2 e 3, colunas 2 e 3)
Situação 3:
R
| 1 1 X |
| 0 1 1 |
| X 0 1 |
R11 = 1, R21 = 0, R22 = 1, R12 = 1, R32 = 0, R33 = 1, R23 = 1
Hipótese não verificada
Mas, se R23 valer 1, temos 2 elementos de valor 1 na coluna C3, portanto deve haver um elemento de valor 0 na mesma coluna. Chamemos de L4 à linha onde ele se encontra. Sabemos que deve existir pelo menos um elemento de valor 1 nessa linha. Chamemos de C4 à coluna onde ele se encontra. Agora, se tivermos valor 1 em (L3,C4), confirma-se a hipótese. Não vou desenhar mais matriz aqui não, VTNC, dá um trabalho do pirú. Continuando o raciocínio, sabemos que o número de linhas e colunas da matriz é finito, por isso um dia fatalmente chegaremos ao Rmn que valerá 0, confirmando a hipótese.
Em outras palavras, para que a hipótese fosse falsa, a matriz R precisaria ser uma matriz diagonal, o que não é possível de acordo com as condições do problema. Facim, né?
????