[obm-l] Re: [obm-l] Re: [obm-l] Exercício Estranho
Olá, Luciano! Olá, Anderson! Verdade: não havia entendido o problema... Muito obrigado pela ajuda! Um abraço! Luiz On Sun, Apr 8, 2018, 2:44 PM Anderson Torres wrote: > Em 8 de abril de 2018 13:36, Luiz Antonio Rodrigues > 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 > = > -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
[obm-l] Re: [obm-l] Exercício Estranho
Em 8 de abril de 2018 13:36, Luiz Antonio Rodrigues 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 =
Re: [obm-l] Exercício Estranho
Para n=0 teremos um quadrado 1x1 se retirarmos 1, cabera exatamente 0 L. Para n=1 teremos um quadrado 2x2 se retirarmos 1 peca ficamos com um L. > Em 8 de abr de 2018, às 13:36, Luiz Antonio Rodrigues > 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? > 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.
[obm-l] Exercício Estranho
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? 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.