[obm-l] Cobrindo um tabuleiro

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Oi, pessoal:

Estou com um probleminha:

Temos um tabuleiro quadriculado retangular m x n, o qual queremos cobrir com
retangulos p x q  (m,n,p,q: inteiros positivos).
Ache a condicao necessaria e suficiente para m, n, p, q de modo que isso
seja possivel.

Uma condicao necessaria obvia eh que: p*q | m*n.
Mas essa condicao nao eh suficiente. Por exemplo, tome um tabuleiro 4 x 9 e
retangulos 1 x 6.
  
Uma condicao suficiente obvia eh que: p | m, q | n   ou   p | n, q | m.
Mas essa condicao nao eh necessaria. Por exemplo, tome um tabuleiro 5 x 6 e
retangulos 2 x 3.

Agradeco qualquer ajuda.

Um abraco,
Claudio.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================