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