Re: [obm-l] Cobrindo um tabuleiro

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Imagine uma função R(k) que nos dê o número de blocos rotacionados que
aparecem na k'ésima coluna (dá pra imaginar?), e N(k) a função que dá o
número de blocos não rotacionados na k'ésima coluna.

R' e N' são funções análogas nas linhas do tabuleiro.

então sabemos que
R(k)*p + N(k)*q = m e
R'(k)*q + N'(k)*p = n

Uma das condições necessárias então é que o sistema acima deve ter solução,
ou seja
as eq. diofantinas Xp + Yq = m e Xp + Yq = n têm solução (não negativa).

Não consegui pensar em nada mais interessante...

Uma idéia menos ambiciosa seria restringir o universo de soluções a casos
mais simples, como por exemplo, formar um retângulo somente com blocos não
rotacionados e complementá-lo com os blocos rotacionados até chegar ao
retângulo desejado.

A propósito, estou quebrando a cabeça no problema de combinatória da obm-u
do ano passado (problema 3 da segunda fase), mas sem muito sucesso... tentei
converter o problema pra linguagem da teoria extremal dos conjuntos mas.
Adaptando aquele teorema que conta as permutações 'compatíveis' f: Z/nZ ->
[n] pra estimar o tamanho máximo de famílias intersectantes eu encontrei
limitantes folgados demais...
Qualquer ajuda/solução é bem vinda...

[ ]'s


> 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
=========================================================================