Re: [obm-l] Re: [obm-l] Re: [obm-l] Desafio: ladrilhar um triân gulo

[Anderson Sales Pereira <aspx@xxxxxxxxxxxx>]

Nicolau,

Obrigado novamente. Estou "digerindo" as duas soluções que você enviou. Ao 
final terei aprendido muito.

Valeu,

Anderson - SP

At 10:12 30/6/2003 -0300, Nicolau C. Saldanha wrote:
>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
>=========================================================================


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