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