Olá galerinha do LeGauss!
Nesse post vou mostrar pra vocês uma solução de um problema que eu vi no livro 21 Aulas de Matemática Olímpica do Shine, publicado pela SBM. De acordo com esse mesmo livro esse problema foi proposto na lista de discussão da OBM no dia 16/07/2003.
(A imagem é a famosa cena dos elevadores do filme O Iluminado, um filme do Stanley Kubrick sobre um livro do Stephen King, não dá para ficar melhor que isso!)
Vamos para o problema!
Bom primeiro vamos tentar obter alguma limitação superior para o número de andares...
Repare que temos no máximo 42 paradas (uma parada é uma dupla
onde 
é um elevador, 
um andar e o elevador para no andar ).
Vamos chamar de
o número de andares no nosso prédio.
Temos que:
De fato, se temos
, obrigatoriamente teremos, pelo menos, 3 paradas em cada andar, pois se tivéssemos apenas 2 elevadores em algum andar poderíamos ir para no máximo outros 10 andares diferentes pegando apenas um elevador.
Logo temos que:
Bem agora vou mostra uma solução com 14 andares, que de acordo com a desigualdade acima nos mostra que o número máximo de andares é 14.
Se você não sabe o que é um plano projetivo dê uma olhada antes nesse post, eu explico lá o que é e mostro um problema mais fácil que esse para você entender melhor como utilizar um plano projetivo em problemas de combinatória.
Vamos pensar no plano projetivo
.
Ele tem essa cara:
Esse é um plano projetivo de ordem 3, isto é, cada linha possui 3 pontos, ele possui 7 retas e 7 pontos.
Vamos chamar de
Vamos identificar cada andar com um ponto diferente de
e vamos associar cada elevador a um subconjunto dos conjunto de pares 
onde 
é uma reta de 
e 
, uma reta de 
, sendo que, nesse subconjunto, uma reta de cada um dos dois planos projetivos representa apenas UM elevador (não existe, por exemplo um elevador 
e um outro elevador 
com 
nem 
)
E isso é uma solução.
Dados os andares
e os elevadores 
temos a seguinte imagem:
(Para ver melhor clique na imagem)
Repare que todos elevadores passam em exatamente 6 andares, o que respeita nosso enunciado e de qualquer andar você consegue chegar em outro pegando apenas um elevador!
É isso espero que tenham curtido.
A desigualdade foi obtida pelo professor Nicolau Saldanha e a solução com o plano projetivo pelo professor Carlos Gustavo Moreira (Gugu).
Nesse post vou mostrar pra vocês uma solução de um problema que eu vi no livro 21 Aulas de Matemática Olímpica do Shine, publicado pela SBM. De acordo com esse mesmo livro esse problema foi proposto na lista de discussão da OBM no dia 16/07/2003.(A imagem é a famosa cena dos elevadores do filme O Iluminado, um filme do Stanley Kubrick sobre um livro do Stephen King, não dá para ficar melhor que isso!)
Vamos para o problema!
Num prédio há 7 elevadores que param em não mais que 6 andares.
É possível ir de um andar a qualquer outro sem trocar de elevador. Qual é o número máximo de andares que esse prédio pode ter?
Bom primeiro vamos tentar obter alguma limitação superior para o número de andares...
Repare que temos no máximo 42 paradas (uma parada é uma dupla
onde é um elevador, um andar e o elevador para no andar ).Vamos chamar de
o número de andares no nosso prédio.Temos que:
De fato, se temos
, obrigatoriamente teremos, pelo menos, 3 paradas em cada andar, pois se tivéssemos apenas 2 elevadores em algum andar poderíamos ir para no máximo outros 10 andares diferentes pegando apenas um elevador.Logo temos que:
Bem agora vou mostra uma solução com 14 andares, que de acordo com a desigualdade acima nos mostra que o número máximo de andares é 14.
Se você não sabe o que é um plano projetivo dê uma olhada antes nesse post, eu explico lá o que é e mostro um problema mais fácil que esse para você entender melhor como utilizar um plano projetivo em problemas de combinatória.
Vamos pensar no plano projetivo
.Ele tem essa cara:
Esse é um plano projetivo de ordem 3, isto é, cada linha possui 3 pontos, ele possui 7 retas e 7 pontos.
Vamos chamar de
Vamos identificar cada andar com um ponto diferente de
e vamos associar cada elevador a um subconjunto dos conjunto de pares onde é uma reta de e , uma reta de , sendo que, nesse subconjunto, uma reta de cada um dos dois planos projetivos representa apenas UM elevador (não existe, por exemplo um elevador e um outro elevador com nem )E isso é uma solução.
Dados os andares
e os elevadores temos a seguinte imagem:
(Para ver melhor clique na imagem)
Repare que todos elevadores passam em exatamente 6 andares, o que respeita nosso enunciado e de qualquer andar você consegue chegar em outro pegando apenas um elevador!
É isso espero que tenham curtido.
Notas
A desigualdade foi obtida pelo professor Nicolau Saldanha e a solução com o plano projetivo pelo professor Carlos Gustavo Moreira (Gugu).
Nenhum comentário:
Postar um comentário