Q15 Matemática  (Baltic Way 1992)

Noé tem 8 espécies de animais para caber em 4 jaulas da arca. Ele planeja colocar espécies em cada gaiola. Acontece que, para cada espécie, existem no máximo 3 outras espécies com as quais não pode dividir o alojamento. Prove que existe uma maneira de alocar os animais em suas gaiolas para que cada espécie compartilhe com espécies compatíveis.