Em 8 de abril de 2018 13:36, Luiz Antonio Rodrigues <rodrigue...@gmail.com> escreveu: > Olá, pessoal! > Boa tarde! > Estou tentando fazer o exercício abaixo (por indução) há algum tempo e não > tive sucesso... > > Prove que para todo natural n, uma grade de quadrados 2^n × 2^n com qualquer > um de seus quadrados removidos pode ser coberta por ladrilhos de > tamanho fixo em forma de um L formado por 3 quadrados. > > Parece que alguma coisa está errada... se n=1 teremos um quadrado com 1 > quadradinho e não vale a hipótese. Se n=2 teremos um quadrado com 4 > quadradinhos; é impossível preencher este quadrado com 1 L... Será que > interpretei o problema de forma incorreta?
Você confundiu o problema totalmente. A ideia é a seguinte: imagine que duas pessoas estejam jogando um jogo, em um tabuleiro estilo xadrez 2^n por 2^n. A primeira pessoa pinta exatamente um destes quadradinhos. A segunda então pega uma certa quantidade de ladrilhos em formato de L, e os encaixa de forma a preencher toda a área que não foi pintada. O problema então consiste em provar que a segunda pessoa sempre conseguirá cobrir toda a área que não foi pintada. Assim sendo, se você tem um só quadrado 1x1, ele obviamente estará pintado de vermelho, e não existirá área para cobrir. Como "o que não tem remédio, remediado está", o problema está resolvido já aí. Se você tem um quadrado 2x2, uma das casas será pintada, e as três restantes obviamente formarão um L. Basta encaixar um L neste L. Bem, para o caso 4x4, aí você já pode começar a brincar... > Alguém pode me ajudar? > Agradeço desde já. > Um abraço! > Luiz > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
