[obm-l] Re: [obm-l] Re: [obm-l] Desafio: ladrilhar um tri�ngulo

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Fri, Jun 27, 2003 at 04:49:17PM -0300, Anderson Sales Pereira wrote:
> Ola Nicolau,
> 
> Obrigado pela corre��o.
> 
> >On Thu, Jun 26, 2003 at 05:29:33PM -0300, Anderson Sales Pereira wrote:
> > > 2. Um museu tem um terreno de exposi��o na forma de um tri�ngulo
> > > ret�ngulo de catetos 50m e 60m. A dire��o do museu decidiu ladrilhar
> > > a �rea. Cada ladrilho � um quadrado de 10 cm de lado. Os ladrilhos
> > > s�o feitos de um material que pode ser cortado apenas 1 vez, devido
> > > ao risco de rachaduras. Al�m disso, apenas uma das partes do
> > > ladrilho cortado pode ser aproveitada. Responda:
> > > a) Qual o n�mero exato de ladrilhos que ser� empregado na obra?

Depois de mandar a outra mensagem achei que valia a pena resolver
algo mais geral.

Considere o tri�ngulo (fechado) de v�rtices (0,0), (a,0) e (0,b)
onde a e b s�o inteiros positivos:
(i) Quantos quadrados da forma [i,i+1]x[j,j+1] est�o totalmente contidos
no tri�ngulo (onde i e j s�o inteiros)?
    [ Estes correspondem aos ladrilhos inteiros. ]
(ii) Para quantos quadrados da forma acima o interior do quadrado e
o interior do tri�ngulo t�m pontos em comum?
    [ Estes correspondem aos ladrilhos usados. ]

Acho que o n�mero mais interessante de se estudar � (ii) - (i), i.e.,
o n�mero de quadradinhos cortados pelo segmento (a,0) - (0,b).
Ora, este segmento come�a dentro de um quadradinho e, antes de chegar
ao �ltimo quadradinho corta (a-1) linhas verticais e (b-1) linhas horizontais.
Cada vez que cortamos uma linha mudamos de quadradinho. Assim cortamos
1 + (a-1) + (b-1) quadradinhos, certo?

Errado. O problema � que podemos passar exatamente por um ponto de coordenadas
inteiras e portanto gastar duas linhas mas s� trocar de quadrado uma vez.
O n�mero de vezes onde isso acontece � mdc(a,b) - 1 logo temos a + b - mdc(a,b)
quadradinhos cortados.

O ret�ngulo com v�rtices (0,0), (a,0), (0,b), (a,b) fica dividido pelo
segmento de (a,0) a (0,b) em dois tri�ngulos iguais. Temos um total de ab
quadradinhos dos quais a + b - mdc(a,b) sobre a diagonal e metade do que
resta para cada lado. Assim a resposta do item (i) �
(ab + a + b - mdc(a,b))/2.

No seu caso a = 600 e b = 500 donde isso d� um total de
(600*500 + 600 + 500 - 100)/2 = 301000/2 = 150500 ladrilhos usados.

[]s, N.

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