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