[obm-l] RE: [obm-l] uma questão difícil

["Artur Costa Steiner" <artur@xxxxxxxxxxxxx>]

Estou entendendo que a estrada de 1680 m eh a linha horizontal do T e a
de 2940 eh a linha vertical. Sejam M o nunero de postes a colocar na
estrada de 1680 m e N o numero a colocar na outra. Estou admitindo que o
poste do cruzamento eh comum a ambas, de modo que temos M + N -1 postes.
Para que a distribuicao dos postes na estrada de 1680 m atenda aos
requisitos, M tem necesariamente que ser impar >=3. Jah o N pode ser
qualquer inteiro >=2. para facilitar, seja m = (M-1)/2 (necessariamente
inteiro, pois M eh impar) e n = N-1. Sendo d a distancia enter 2 postes
consecutivos, devemos ter (M-1)d = 1680 e (N-1)d = 2940, pois os postes
dividem as duas estradas em M-1 e N-1 trechos de comprimento d.
Temos portanto que 2md = 1680 e nd = 2940, o que acarreta que m/n =
840/2940. Temos assim o seguinte problema de otimizacao:
Maximizar d = 840/m (que equivale a minimizar m/840), variando m e n
Sujeito a que m/n = 84/294, m e n inteiros.
Nao eh preciso recorrer a um algoritmo do tipo Branch and Bound. Basta
observar que m sera maximo quando m/n for uma fracao irredutivel igual a
84/294. Esta fracao eh 2/7, de modo que m= 2 e n=7, acarretando d = 420
m. Teremos assim M= 5 postes na estrada de 1680 m e N=8 postes na de
2940, sendo um comum a ambas. Logo, o proprietario da estrada vai ter
que investir em apenas M+N-1  = 12 postes. Que usura!! As estradas estao
muito mal ilumidas, 420 m de distância entrea os postes! Deve ser contra
as normas do DNER.
Nao sei o que sao aqueles numeros que vc colocou ao final de sua
mensagem. Muito diferentes de meu resultado. Esdpero que eu tenha
entendido o problema corretamente.
Um abraco.
Artur        
 
> Duas estradas que se cortam em formato de um T, Tem
> 2.940 m e 1.680 m respectivamente. Pretende-se colocar
> postes de iluminação ao longo das estradas, de modo
> que exista um poste em cada extremidade do trecho
> considerado e um no cruzamento das duas estradas.
> Exige-se que a distância entre cada dois postes seja a
> mesma e a maior possível?
> 
> 12
> 11
> 10
> 9
> 8
> 
> 
> 
> 
>
_______________________________________________________________________
> Desafio AntiZona: participe do jogo de perguntas e respostas que vai
> dar um Renault Clio, computadores, câmeras digitais, videogames e
muito
> mais! www.cade.com.br/antizona
>
========================================================================
=
> 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
=========================================================================