[obm-l] Re: [obm-l] NOVO MEMBRO E UMA D�VIDA

["Thiago Sobral" <thiago-sobral@xxxxxxxxxx>]

  Falando nesse problema, nao teria um valor menor q 4 
para a soma das areas q garantisse a cobertura do 
inicial? A 1a vista, 4 parece um valor meio 
q "folgado"...   
  A minha solucao ficou incompleta, e naum sei se eh 
possivel conclui-la. eh +- isso:
  Tentei criar um algoritmo para preencher o quadrado 
inicial, do seguinte modo: sejam q1, q2,...,qn os 
quadradinhos, colocados em ordem decrescente de area. 
Comece colocando q1 no canto inferior esquerdo do 
inicial, q2 ao seu lado e assim por diante, ate 
extrapolar os limites do quadrado inicial. O passo sera o 
seguinte: Num dado momento da cobertura, como estou 
colocando todos os q_is com lados paralelos aos lados do 
inicial, havera uma altura minima q ainda naum foi 
preenchida:
                        _____
 ____                  |      
     |      ____       |      
     |     |    |      |       
     |_____|    |      |      
                |_aqui_|      
                |      |      
                | q_i  |      

  Seja qi o quadradinho q origina essa altura minima. 
entao, faco como fiz no inicio, colocando qj, q(j+1)... 
comecando pelo canto inferior esquerdo, ate q alguma area 
seja superposta, cortando o quadradinho do lado direito.
  Agora observo as perdas q ocorrem, com a superposicao: 
Como a area de qj (e o lado tb) eh menor q a area de qi, 
na pior das hipoteses colocarei no minimo qj e q(j+1), 
e "perderei" apenas uma parte de q(j+1). Mas, desse modo, 
mais de 50% da area q coloquei foi realmente utilizada 
para cobrir o quadrado inicial, pois a area de qj foi 
toda util e eh maior q a area de q(j+1). 
Assim, eh de se pensar q se a soma das areas fosse 2, jah 
conseguiriamos cobrir o inicial! Mas ha dois problemas: 
um eh q, quando seguirmos cobrindo desse modo, ao chegar 
no "teto", jah teremos perdas, com parte do 1o 
quadradinho colocado fora dos limites do quadrado 
inicial. O outro esta no lado direito do quadrado 
inicial, pois pode ser q, ao colocarmos o 1o quadradinho 
seguindo o algoritmo, jah saia dos limites do inicial:

                |<- lado do inicial
           __   |
             |  |     
             |__|__             
             |     |
             |     |
     ... ____|_____|

  Sugestoes para resolver esses problemas? 
  Desculpe pelo mail longo, eh q essa deu trabalho pra 
explicar =]

[]s, thiago sobral

> Segue abaixo a solu��o do problema 5 da olimp�ada do 
n�vel 3. (� +- a
> solu��o dada por um aluno meu, o Ant�nio Munhoz, que 
foi prata).
> S� pra relembrar o enunciado :
> "Temos um n�mero finito de quadrados, de �rea total 4. 
Prove que � poss�vel
> arranj�-los de modo a cobrir um quadrado de lado 1.
> 
> Obs: � permitido sobrepor quadrados e parte deles pode 
ultrapassar os
> limites do quadrado a ser coberto."



 
__________________________________________________________________________
Venha para a VilaBOL!
O melhor lugar para voc� construir seu site. F�cil e gr�tis!
http://vila.bol.com.br


=========================================================================
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
O administrador desta lista � <nicolau@mat.puc-rio.br>
=========================================================================