Re: [obm-l] Tabuleiro n x n
Primeiro, note que como cada peça tem 6 quadradinhos, n^2 é múltiplo de 6, ou seja, n é múltiplo de 6. Assim, n^2 é múltiplo de 36, de modo que n^2=36k, e a quantidade de peças é 6k, que é par. Agora, pense nos centros dos quadradinhos como pontos de coordenadas inteiras, de (1,1) a (n,n), e pinte os quadradinhos com ambas as coordenadas pares. Com isso, a quantidade de quadradinhos é (n/2)^2. Mas pode-se verificar, testando todos os casos, que cada peça cobre uma ou três casas pintadas, ou seja, é sempre ímpar. Com isso, como a quantidade de peças é par, o total (n/2)^2 é par, ou seja, n/2 é par, e com isso, n é múltiplo de 4. Portanto n é múltiplo de 12, e como o amigo já notou, é possível cobrir um 12 x 12, e portanto todo n múltiplo de 12 funciona. []'sShine On Thursday, May 7, 2015 1:10 PM, Pedro José petroc...@gmail.com wrote: Bom dia! Temos que verificar os retângulos que podem ser gerados pela peça em destaque. Além disso eliminar os que podem ser gerados por outros retãngulos. Por exemplo o retângulo abaixo pode gerar | | | | | | | | | | | | | | | Por exemplo o retângulo acima pode gerar o retângulo abaixo: | | | | | | | | | | | | | | | | | | | | | | | | | | | Usando k peças para gerar um retângulo que não pode ser gerado por nenhum outro retângulo (retângulo básico), teremos que a área desse retângulo é 6k (restrições: não pode sair do tabuleiro, nem superposição. ). Só não consegui provar que o retângulo 3x4 é o único retângulo básico.Vou prosseguir tentando. Aí fica que n = 12 m com m Ɛ |N* Saudações,PJMS Em 6 de maio de 2015 20:40, Mariana Groff bigolingroff.mari...@gmail.com escreveu: Boa noite,Estou com dúvida no seguinte problema, alguém poderia ajudar-me? Determine para quais números naturais n é possível cobrir completamente um tabuleiro de n × ndividido em casas de 1 × 1 com peças como a da figura, sem buracos nem superposições e semsair do tabuleiro. Cada uma das peças cobre exatamente seis casas. Nota: As peças podem girar. _ |_|_|_|_|_|_|_|_| Obrigada,Mariana -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�us e acredita-se estar livre de perigo. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Tabuleiro n x n
Boa noite! Não consegui provar que só os retângulos 3x4 e 4 x3 atendem. Um retângulo é básico, quando ele só pode ser obitido através da rotação de apenas um retângulo. A definição estava ruim, pois sé era único não poderiam já haver 2. Então temos que mmc(3,4) | n, onde | significa divide. == n = 12 m com m Ɛ |N*. Se conseguíssemos outro triângulo (a,b), teríamos que aceitar também qualquer n que fosse múltiplo de mmc (a,b). Por exemplo se conseguíssemos um retângulo com os lados 6 e 10, teríamos que n = 30 m também atenderia. Note que o mmc sempre será múltiplo de 6. Se acharmos um mmc que é múltiplo de 12, mesmo que esse novo retângulo seja básico, ele trará como solução um subconjunto do gerado com 3 x 4 ou 4 x 3. Por exemplo: 10 x 6. Todavia, se existirem retângulos ai x bi que mmc(ai,bi) | 6 e mmc (ai,bi) ∤ 12 (onde ∤ significa não divide) e tomarmos o que mmc(ai,bi) = mi, teremos que incluir as soluções n = j. mi, j Ɛ 2 |N + 1 e i Ɛ |N*. variando de 1 até t, onde t é o número de retângulos possíveis. Com mmc igual a 6 é fácil mostrar que não existe, mas para mmc(a,b) Ɛ {18, 30,42,54, 66 ...} mostrar que não existe nenhum retângulo (que é o que acredito, intuitivamente) ou determinar para que valores de {18, 30,42,54, 66 ...} atende, o que suponho ser deveras complicado. Portanto se alguém observar uma restrição para que não seja possível se formar retângulos a x b, cujo mmc(a,b) é um múltiplo ímpar de 6, favor ajudar para fechar o problema. Saudações, PJMS Em 7 de maio de 2015 13:10, Pedro José petroc...@gmail.com escreveu: Bom dia! Temos que verificar os retângulos que podem ser gerados pela peça em destaque. Além disso eliminar os que podem ser gerados por outros retãngulos. Por exemplo o retângulo abaixo pode gerar Por exemplo o retângulo acima pode gerar o retângulo abaixo: Usando k peças para gerar um retângulo que não pode ser gerado por nenhum outro retângulo (retângulo básico), teremos que a área desse retângulo é 6k (restrições: não pode sair do tabuleiro, nem superposição. ). Só não consegui provar que o retângulo 3x4 é o único retângulo básico. Vou prosseguir tentando. Aí fica que n = 12 m com m Ɛ |N* Saudações, PJMS Em 6 de maio de 2015 20:40, Mariana Groff bigolingroff.mari...@gmail.com escreveu: Boa noite, Estou com dúvida no seguinte problema, alguém poderia ajudar-me? Determine para quais números naturais n é possível cobrir completamente um tabuleiro de n × n dividido em casas de 1 × 1 com peças como a da figura, sem buracos nem superposições e sem sair do tabuleiro. Cada uma das peças cobre exatamente seis casas. Nota: As peças podem girar. _ |_|_ |_|_|_ |_|_|_| Obrigada, Mariana -- 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.
Re: [obm-l] Tabuleiro n x n
Bom dia! Temos que verificar os retângulos que podem ser gerados pela peça em destaque. Além disso eliminar os que podem ser gerados por outros retãngulos. Por exemplo o retângulo abaixo pode gerar Por exemplo o retângulo acima pode gerar o retângulo abaixo: Usando k peças para gerar um retângulo que não pode ser gerado por nenhum outro retângulo (retângulo básico), teremos que a área desse retângulo é 6k (restrições: não pode sair do tabuleiro, nem superposição. ). Só não consegui provar que o retângulo 3x4 é o único retângulo básico. Vou prosseguir tentando. Aí fica que n = 12 m com m Ɛ |N* Saudações, PJMS Em 6 de maio de 2015 20:40, Mariana Groff bigolingroff.mari...@gmail.com escreveu: Boa noite, Estou com dúvida no seguinte problema, alguém poderia ajudar-me? Determine para quais números naturais n é possível cobrir completamente um tabuleiro de n × n dividido em casas de 1 × 1 com peças como a da figura, sem buracos nem superposições e sem sair do tabuleiro. Cada uma das peças cobre exatamente seis casas. Nota: As peças podem girar. _ |_|_ |_|_|_ |_|_|_| Obrigada, Mariana -- 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.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Ola' Pacini, o loop que eliminava a igualdade por rotacao, tambem ja' contava cada combinacao permitida. Neste caso, o total e' de 9612 pinturas. []'s Rogerio Ponce 2015-03-30 14:55 GMT-03:00 Pacini Bores pacini.bo...@globo.com: Oi Ponce, na verdade é para considerar todas as possibilidades, ou seja, não é um tabuleiro apesar do enunciado ter sido inicialmente com o tabuleiro, ok ? Desculpe, caso tenha dado algum transtorno. abraços Pacini Em 30 de março de 2015 13:38, Rogerio Ponce abrlw...@gmail.com escreveu: Ooopa, quero dizer, 2472. []'s Rogerio Ponce 2015-03-30 11:59 GMT-03:00 Rogerio Ponce abrlw...@gmail.com: Ola' pessoal, eu acho que a questao e' um pouco mais complicada, pois e' razoavel que pinturas obtidas por rotacao do tabuleiro sejam consideradas a mesma pintura. Utilizando forca bruta, encontrei apenas 2724 modos diferentes de se pintar o tabuleiro. []'s Rogerio Ponce 2015-03-30 11:16 GMT-03:00 Pedro José petroc...@gmail.com: Bom dia! Havia feito para exatamente quatro cores. Mas, é fácil adaptar para até quatro cores, há até menos restrições. Resolvi por grafo, fazendo opções. Preenchimento primeiramente de a1,1, depois o par a2,1 e a1,2, depois o par a2,2 e a1,3 em seguida a3,2 e a2,3 e por último a3,1 e a3,3. Abri o grafo sempre iguais ou diferentes. Certamente, não está otimizado. Encontrei: 8640 possibilidades com exatamente 4 cores. Vou refazer para até quatro cores e vos envio o grafo, se possível ainda hoje ao final da tarde (ocupado), vai ser escaneado, pois fiz na mão. Saudações, PJMS Em 30 de março de 2015 10:49, Carlos Victor victorcar...@globo.com escreveu: Acredito que ideia do Bob Roy é o mais rápida para obter a solução. Carlos Victor Em 30 de março de 2015 10:39, Pacini Bores pacini.bo...@globo.com escreveu: Sim Pedro, esta é uma solução; ou seja, há possibilidade de se usar até quatro cores. Pacini Em 30 de março de 2015 10:23, Pedro José petroc...@gmail.com escreveu: Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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. -- 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. -- 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. -- 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.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Boa tarde! Ponce, também achei esse valor, 9612, para tabuleiro orientado, considerando matriz. E encontrei 2472 elimnando as rotações, tabuleiro sem orientação. Como você resolveu? Saudações, PJMS Em 31 de março de 2015 12:58, Rogerio Ponce abrlw...@gmail.com escreveu: Ola' Pacini, o loop que eliminava a igualdade por rotacao, tambem ja' contava cada combinacao permitida. Neste caso, o total e' de 9612 pinturas. []'s Rogerio Ponce 2015-03-30 14:55 GMT-03:00 Pacini Bores pacini.bo...@globo.com: Oi Ponce, na verdade é para considerar todas as possibilidades, ou seja, não é um tabuleiro apesar do enunciado ter sido inicialmente com o tabuleiro, ok ? Desculpe, caso tenha dado algum transtorno. abraços Pacini Em 30 de março de 2015 13:38, Rogerio Ponce abrlw...@gmail.com escreveu: Ooopa, quero dizer, 2472. []'s Rogerio Ponce 2015-03-30 11:59 GMT-03:00 Rogerio Ponce abrlw...@gmail.com: Ola' pessoal, eu acho que a questao e' um pouco mais complicada, pois e' razoavel que pinturas obtidas por rotacao do tabuleiro sejam consideradas a mesma pintura. Utilizando forca bruta, encontrei apenas 2724 modos diferentes de se pintar o tabuleiro. []'s Rogerio Ponce 2015-03-30 11:16 GMT-03:00 Pedro José petroc...@gmail.com: Bom dia! Havia feito para exatamente quatro cores. Mas, é fácil adaptar para até quatro cores, há até menos restrições. Resolvi por grafo, fazendo opções. Preenchimento primeiramente de a1,1, depois o par a2,1 e a1,2, depois o par a2,2 e a1,3 em seguida a3,2 e a2,3 e por último a3,1 e a3,3. Abri o grafo sempre iguais ou diferentes. Certamente, não está otimizado. Encontrei: 8640 possibilidades com exatamente 4 cores. Vou refazer para até quatro cores e vos envio o grafo, se possível ainda hoje ao final da tarde (ocupado), vai ser escaneado, pois fiz na mão. Saudações, PJMS Em 30 de março de 2015 10:49, Carlos Victor victorcar...@globo.com escreveu: Acredito que ideia do Bob Roy é o mais rápida para obter a solução. Carlos Victor Em 30 de março de 2015 10:39, Pacini Bores pacini.bo...@globo.com escreveu: Sim Pedro, esta é uma solução; ou seja, há possibilidade de se usar até quatro cores. Pacini Em 30 de março de 2015 10:23, Pedro José petroc...@gmail.com escreveu: Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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. -- 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. -- 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. -- 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. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Olá, também encontrei 9612 da forma que coloquei anteriormente. Bob Em 31 de março de 2015 13:12, Pedro José petroc...@gmail.com escreveu: Boa tarde! Ponce, também achei esse valor, 9612, para tabuleiro orientado, considerando matriz. E encontrei 2472 elimnando as rotações, tabuleiro sem orientação. Como você resolveu? Saudações, PJMS Em 31 de março de 2015 12:58, Rogerio Ponce abrlw...@gmail.com escreveu: Ola' Pacini, o loop que eliminava a igualdade por rotacao, tambem ja' contava cada combinacao permitida. Neste caso, o total e' de 9612 pinturas. []'s Rogerio Ponce 2015-03-30 14:55 GMT-03:00 Pacini Bores pacini.bo...@globo.com: Oi Ponce, na verdade é para considerar todas as possibilidades, ou seja, não é um tabuleiro apesar do enunciado ter sido inicialmente com o tabuleiro, ok ? Desculpe, caso tenha dado algum transtorno. abraços Pacini Em 30 de março de 2015 13:38, Rogerio Ponce abrlw...@gmail.com escreveu: Ooopa, quero dizer, 2472. []'s Rogerio Ponce 2015-03-30 11:59 GMT-03:00 Rogerio Ponce abrlw...@gmail.com: Ola' pessoal, eu acho que a questao e' um pouco mais complicada, pois e' razoavel que pinturas obtidas por rotacao do tabuleiro sejam consideradas a mesma pintura. Utilizando forca bruta, encontrei apenas 2724 modos diferentes de se pintar o tabuleiro. []'s Rogerio Ponce 2015-03-30 11:16 GMT-03:00 Pedro José petroc...@gmail.com: Bom dia! Havia feito para exatamente quatro cores. Mas, é fácil adaptar para até quatro cores, há até menos restrições. Resolvi por grafo, fazendo opções. Preenchimento primeiramente de a1,1, depois o par a2,1 e a1,2, depois o par a2,2 e a1,3 em seguida a3,2 e a2,3 e por último a3,1 e a3,3. Abri o grafo sempre iguais ou diferentes. Certamente, não está otimizado. Encontrei: 8640 possibilidades com exatamente 4 cores. Vou refazer para até quatro cores e vos envio o grafo, se possível ainda hoje ao final da tarde (ocupado), vai ser escaneado, pois fiz na mão. Saudações, PJMS Em 30 de março de 2015 10:49, Carlos Victor victorcar...@globo.com escreveu: Acredito que ideia do Bob Roy é o mais rápida para obter a solução. Carlos Victor Em 30 de março de 2015 10:39, Pacini Bores pacini.bo...@globo.com escreveu: Sim Pedro, esta é uma solução; ou seja, há possibilidade de se usar até quatro cores. Pacini Em 30 de março de 2015 10:23, Pedro José petroc...@gmail.com escreveu: Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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. -- 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. -- 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. -- 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. -- Esta mensagem foi verificada pelo sistema de
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Obrigado a todos pelas discussões. Pacini Em 31 de março de 2015 13:12, Pedro José petroc...@gmail.com escreveu: Boa tarde! Ponce, também achei esse valor, 9612, para tabuleiro orientado, considerando matriz. E encontrei 2472 elimnando as rotações, tabuleiro sem orientação. Como você resolveu? Saudações, PJMS Em 31 de março de 2015 12:58, Rogerio Ponce abrlw...@gmail.com escreveu: Ola' Pacini, o loop que eliminava a igualdade por rotacao, tambem ja' contava cada combinacao permitida. Neste caso, o total e' de 9612 pinturas. []'s Rogerio Ponce 2015-03-30 14:55 GMT-03:00 Pacini Bores pacini.bo...@globo.com: Oi Ponce, na verdade é para considerar todas as possibilidades, ou seja, não é um tabuleiro apesar do enunciado ter sido inicialmente com o tabuleiro, ok ? Desculpe, caso tenha dado algum transtorno. abraços Pacini Em 30 de março de 2015 13:38, Rogerio Ponce abrlw...@gmail.com escreveu: Ooopa, quero dizer, 2472. []'s Rogerio Ponce 2015-03-30 11:59 GMT-03:00 Rogerio Ponce abrlw...@gmail.com: Ola' pessoal, eu acho que a questao e' um pouco mais complicada, pois e' razoavel que pinturas obtidas por rotacao do tabuleiro sejam consideradas a mesma pintura. Utilizando forca bruta, encontrei apenas 2724 modos diferentes de se pintar o tabuleiro. []'s Rogerio Ponce 2015-03-30 11:16 GMT-03:00 Pedro José petroc...@gmail.com: Bom dia! Havia feito para exatamente quatro cores. Mas, é fácil adaptar para até quatro cores, há até menos restrições. Resolvi por grafo, fazendo opções. Preenchimento primeiramente de a1,1, depois o par a2,1 e a1,2, depois o par a2,2 e a1,3 em seguida a3,2 e a2,3 e por último a3,1 e a3,3. Abri o grafo sempre iguais ou diferentes. Certamente, não está otimizado. Encontrei: 8640 possibilidades com exatamente 4 cores. Vou refazer para até quatro cores e vos envio o grafo, se possível ainda hoje ao final da tarde (ocupado), vai ser escaneado, pois fiz na mão. Saudações, PJMS Em 30 de março de 2015 10:49, Carlos Victor victorcar...@globo.com escreveu: Acredito que ideia do Bob Roy é o mais rápida para obter a solução. Carlos Victor Em 30 de março de 2015 10:39, Pacini Bores pacini.bo...@globo.com escreveu: Sim Pedro, esta é uma solução; ou seja, há possibilidade de se usar até quatro cores. Pacini Em 30 de março de 2015 10:23, Pedro José petroc...@gmail.com escreveu: Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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. -- 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. -- 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. -- 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. -- Esta mensagem foi verificada pelo sistema de antivírus e acredita-se
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Bom dia! Havia feito para exatamente quatro cores. Mas, é fácil adaptar para até quatro cores, há até menos restrições. Resolvi por grafo, fazendo opções. Preenchimento primeiramente de a1,1, depois o par a2,1 e a1,2, depois o par a2,2 e a1,3 em seguida a3,2 e a2,3 e por último a3,1 e a3,3. Abri o grafo sempre iguais ou diferentes. Certamente, não está otimizado. Encontrei: 8640 possibilidades com exatamente 4 cores. Vou refazer para até quatro cores e vos envio o grafo, se possível ainda hoje ao final da tarde (ocupado), vai ser escaneado, pois fiz na mão. Saudações, PJMS Em 30 de março de 2015 10:49, Carlos Victor victorcar...@globo.com escreveu: Acredito que ideia do Bob Roy é o mais rápida para obter a solução. Carlos Victor Em 30 de março de 2015 10:39, Pacini Bores pacini.bo...@globo.com escreveu: Sim Pedro, esta é uma solução; ou seja, há possibilidade de se usar até quatro cores. Pacini Em 30 de março de 2015 10:23, Pedro José petroc...@gmail.com escreveu: Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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. -- 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. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Acredito que ideia do Bob Roy é o mais rápida para obter a solução. Carlos Victor Em 30 de março de 2015 10:39, Pacini Bores pacini.bo...@globo.com escreveu: Sim Pedro, esta é uma solução; ou seja, há possibilidade de se usar até quatro cores. Pacini Em 30 de março de 2015 10:23, Pedro José petroc...@gmail.com escreveu: Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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. -- 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.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Sim Pedro, esta é uma solução; ou seja, há possibilidade de se usar até quatro cores. Pacini Em 30 de março de 2015 10:23, Pedro José petroc...@gmail.com escreveu: Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Ola' pessoal, eu acho que a questao e' um pouco mais complicada, pois e' razoavel que pinturas obtidas por rotacao do tabuleiro sejam consideradas a mesma pintura. Utilizando forca bruta, encontrei apenas 2724 modos diferentes de se pintar o tabuleiro. []'s Rogerio Ponce 2015-03-30 11:16 GMT-03:00 Pedro José petroc...@gmail.com: Bom dia! Havia feito para exatamente quatro cores. Mas, é fácil adaptar para até quatro cores, há até menos restrições. Resolvi por grafo, fazendo opções. Preenchimento primeiramente de a1,1, depois o par a2,1 e a1,2, depois o par a2,2 e a1,3 em seguida a3,2 e a2,3 e por último a3,1 e a3,3. Abri o grafo sempre iguais ou diferentes. Certamente, não está otimizado. Encontrei: 8640 possibilidades com exatamente 4 cores. Vou refazer para até quatro cores e vos envio o grafo, se possível ainda hoje ao final da tarde (ocupado), vai ser escaneado, pois fiz na mão. Saudações, PJMS Em 30 de março de 2015 10:49, Carlos Victor victorcar...@globo.com escreveu: Acredito que ideia do Bob Roy é o mais rápida para obter a solução. Carlos Victor Em 30 de março de 2015 10:39, Pacini Bores pacini.bo...@globo.com escreveu: Sim Pedro, esta é uma solução; ou seja, há possibilidade de se usar até quatro cores. Pacini Em 30 de março de 2015 10:23, Pedro José petroc...@gmail.com escreveu: Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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. -- 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. -- 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.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Ooopa, quero dizer, 2472. []'s Rogerio Ponce 2015-03-30 11:59 GMT-03:00 Rogerio Ponce abrlw...@gmail.com: Ola' pessoal, eu acho que a questao e' um pouco mais complicada, pois e' razoavel que pinturas obtidas por rotacao do tabuleiro sejam consideradas a mesma pintura. Utilizando forca bruta, encontrei apenas 2724 modos diferentes de se pintar o tabuleiro. []'s Rogerio Ponce 2015-03-30 11:16 GMT-03:00 Pedro José petroc...@gmail.com: Bom dia! Havia feito para exatamente quatro cores. Mas, é fácil adaptar para até quatro cores, há até menos restrições. Resolvi por grafo, fazendo opções. Preenchimento primeiramente de a1,1, depois o par a2,1 e a1,2, depois o par a2,2 e a1,3 em seguida a3,2 e a2,3 e por último a3,1 e a3,3. Abri o grafo sempre iguais ou diferentes. Certamente, não está otimizado. Encontrei: 8640 possibilidades com exatamente 4 cores. Vou refazer para até quatro cores e vos envio o grafo, se possível ainda hoje ao final da tarde (ocupado), vai ser escaneado, pois fiz na mão. Saudações, PJMS Em 30 de março de 2015 10:49, Carlos Victor victorcar...@globo.com escreveu: Acredito que ideia do Bob Roy é o mais rápida para obter a solução. Carlos Victor Em 30 de março de 2015 10:39, Pacini Bores pacini.bo...@globo.com escreveu: Sim Pedro, esta é uma solução; ou seja, há possibilidade de se usar até quatro cores. Pacini Em 30 de março de 2015 10:23, Pedro José petroc...@gmail.com escreveu: Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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. -- 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. -- 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.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Oi Ponce, na verdade é para considerar todas as possibilidades, ou seja, não é um tabuleiro apesar do enunciado ter sido inicialmente com o tabuleiro, ok ? Desculpe, caso tenha dado algum transtorno. abraços Pacini Em 30 de março de 2015 13:38, Rogerio Ponce abrlw...@gmail.com escreveu: Ooopa, quero dizer, 2472. []'s Rogerio Ponce 2015-03-30 11:59 GMT-03:00 Rogerio Ponce abrlw...@gmail.com: Ola' pessoal, eu acho que a questao e' um pouco mais complicada, pois e' razoavel que pinturas obtidas por rotacao do tabuleiro sejam consideradas a mesma pintura. Utilizando forca bruta, encontrei apenas 2724 modos diferentes de se pintar o tabuleiro. []'s Rogerio Ponce 2015-03-30 11:16 GMT-03:00 Pedro José petroc...@gmail.com: Bom dia! Havia feito para exatamente quatro cores. Mas, é fácil adaptar para até quatro cores, há até menos restrições. Resolvi por grafo, fazendo opções. Preenchimento primeiramente de a1,1, depois o par a2,1 e a1,2, depois o par a2,2 e a1,3 em seguida a3,2 e a2,3 e por último a3,1 e a3,3. Abri o grafo sempre iguais ou diferentes. Certamente, não está otimizado. Encontrei: 8640 possibilidades com exatamente 4 cores. Vou refazer para até quatro cores e vos envio o grafo, se possível ainda hoje ao final da tarde (ocupado), vai ser escaneado, pois fiz na mão. Saudações, PJMS Em 30 de março de 2015 10:49, Carlos Victor victorcar...@globo.com escreveu: Acredito que ideia do Bob Roy é o mais rápida para obter a solução. Carlos Victor Em 30 de março de 2015 10:39, Pacini Bores pacini.bo...@globo.com escreveu: Sim Pedro, esta é uma solução; ou seja, há possibilidade de se usar até quatro cores. Pacini Em 30 de março de 2015 10:23, Pedro José petroc...@gmail.com escreveu: Bom dia! Uma dúvida há necessidade de se usar as quatro cores ou há a possibilidade de se usar até quatro cores? Por exemplo, 0 1 0 1 0 1 0 1 0 onde 0 e 1 representam duas cores distintas, seria uma solução? Saudações, PJMS Em 29 de março de 2015 11:26, Bob Roy bob...@globo.com escreveu: Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- 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. -- 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. -- 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. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Olá, O melhor para este problema é utlizar o que o grande mestre Morgado falava : devemos inicialmente eliminar as dificuldades. Considerando uma matriz 3x3 , temos que os quadradinhos a12, a21, a23 e a32 não poderão ter todas as cores diferentes. Comece fazendo a análise com duas cores iguais, três cores iguais e depois quatro cores iguais para essas posições. A análise ficará menos trabalhosa . Farei as contas e depois eu posto o resultado. Roy Em 28 de março de 2015 10:22, Carlos Victor victorcar...@globo.com escreveu: Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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. -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo.
Re: [obm-l] Tabuleiro 3x3 com 4 cores
Comece pelo centro e pelas laterais, isto deve diminuir as dificuldades. Abrirão vários casos para serem analisados. E se não me engano, esta questão tem como origem não considerando os quadrados pelos vértices com as mesmas cores. Neste caso a análise fica mais silmplificada. Abraços Carlos Victor Em 28 de março de 2015 09:38, Pacini Bores pacini.bo...@globo.com escreveu: Olá pessoal, como pensar nesta ? De quantas maneiras podemos pintar um tabuleiro 3x3 com 4 cores de tal forma que não tenhamos cores adjacentes ? Nota : em diagonal não é considerado adjacente. Agradeço desde já Pacini. -- 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.
Re: RE: [obm-l] tabuleiro
-- Cabeçalho original --- De: [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: Data: Wed, 4 Apr 2007 21:45:01 -0300 Assunto: Re: RE: [obm-l] tabuleiro Prezado Cláudio, desculpe a minha falta de conhecimento, mas não entendi como você descobriu que as equações ideais são aquelas e não outras sem precisar escrever todas, ou seja, qual o critério estabelicido para saber que aquelas 10 e não outras são as equações que nos darão a soma desejada. Outra pergunta, esse problema é conhecido em forma de algum teorema ou é apenasm mais um dos vários problemas que envolvem tabuleiros? Um abraço, Vanderlei Em (23:08:54), obm-l@mat.puc-rio.br escreveu: Voce achou uma configuracao que funciona. Mas o problema eh provar que qualquer configuracao que obedece ao enunciado tem soma m(m+1). A primeira observacao eh que voce pode reduzir o problema a metade pois se a soma das casas pretas for m(m+1)/2, entao a soma das casas brancas tambem serah m(m+1)/2. Por exemplo, num tabuleiro 8x8 (o problema original), suponha que voce quer descobrir a soma das casas pretas (ou seja, as casas x(i,j) com i+j par - estou supondo que o canto superior esquerdo - casa x(1,1) - eh preto) por meio da solucao de um sistema linear que implementa as condicoes do enunciado. Este sistema consiste de 32 equacoes (uma para cada casa branca) em 32 incognitas (os valores das casas pretas). Por exemplo, algumas das equacoes sao: x(1,1)+x(2,2)+x(1,3)=1 (vizinhos da casa (1,2)) x(3,7)+x(4,6)+x(4,8)+x(5,7)=1 (vizinhos da casa (4,7)) x(7,1)+x(8,2)=1 (vizinhos da casa (8,1)) etc... No entanto, voce quer apenas a soma x(1,1)+x(1,3)+x(1,5)+...+x(8,8) e nao o valor de cada variavel individualmente (ateh porque existe uma infinidade de solucoes - o sistema tem posto 32 - alias, um outro problema interessante eh determinar o posto do sistema ou, equivalentemente, o numero maximo de casas do tabuleiro cujo valor pode ser escolhido arbitrariamente). O que voce tem que fazer, entao, eh tomar um subconjunto dessas 32 equacoes tal que cada variavel aparece em exatamente uma equacao desse subconjunto. Dai, somando as equacoes voce obterah a soma desejada. Um tal subconjunto consiste de exatamente 10 equacoes (veja abaixo). Como o lado esquerdo de cada uma delas eh 1, a soma desejada eh 10. De forma totalmente analoga, voce calcula a soma das casas brancas - tambem igual a 10, claro! Logo, a soma do tabuleiro eh 20. Pra ver que o subconjunto acima consiste de 10 equacoes, o melhor eh visualizar o tabuleiro, onde * representa uma casa branca e letras representam as incognitas das 10 equacoes (duas casas com letras iguais representam incognitas que aparecem numa mesma equacao - por exemplo, a primeira equacao mencionada acima eh representada pela letra a, a terceira pela letra k e segunda nao estah entre as 10): a * a * t * t * c * b * b * e * c * g * h * h * k * g * s * p * O mesmo procedimento funciona no caso geral: num tabuleiro 2mx2m as casas pretas (e as brancas) geram 2m^2 equacoes em 2m^2 incognitas, das quais podemos extrair um subconjunto com m(m+1)/2 equacoes tal que cada incognita aparece em exatamente uma equacao. Uma prova disso pode ser dada por inducao (por exemplo, adicione 2 linhas e 2 colunas ao tabuleiro acima e veja o que acontece) []s, Claudio. -- Cabeçalho original --- De: João Gilberto Ponciano Pereira [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: [EMAIL PROTECTED] Data: Tue, 3 Apr 2007 19:20:34 -0300 Assunto: RE: [obm-l] tabuleiro Uma configuação que sempre dá certo para um tabuleiro 2nx2n é a seguinte: Imagine uma matriz 2n x 2n em camadas... a camada externa seria composta pela linha 1 e 2n mais as colunas 1 e 2n. A segunda camada seria para as linhas 2 e 2n-1 (excluindo os elementos das pontas, que já fazem parte da camada externa) e as colunas na mesma configuração. Logo, uma matriz 2n x 2n teria n camadas. Uma configuração que sempre funciona é atribuir o valor 0.5 para as camadas ímpares e 0 para as camadas pares. alguns exemplos: 2x2: 0.5 0.5 0.5 0.5 4x4 0.5 0.5 0.5 0.5 0.5 0.0 0.0 0.5 0.5 0.0 0.0 0.5 0.5 0.5 0.5 0.5 6x6 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.0 0.0 0.0 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.0 0.0 0.0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 Agora é questão de braço para chegar na fórmula m(m+1) por indução, vamos colocar uma casca nova num tabuleiro 2m x 2m existente. f(m+2) = f(m) + CascaNova, sendo que CascaNova = (m+2) * 4 - 2 (o menos 2 é devido aos vértices) (m+2) * (m+3) = m (m+1) + 4m + 8 -2 E como a fórmula funciona para m=1 (tabuleiro 2x2) e m=2(tabuleiro 4x4) funciona para todos, certo? SDS JG [João Gilberto Ponciano Pereira
Re: RE: [obm-l] tabuleiro
O criterio foi a observacao de que eu nao preciso saber o valor de cada casa preta, mas simplesmente a soma desses valores. No caso, eu simplesmente achei 10 casas brancas tais que as casas pretas vizinhas a cada uma delas nao sao vizinhas de nenhuma das outras 9 e tomei as equacoes relativas aquelas casas brancas. Pra fazer isso eu desenhei um tabuleiro e, apos algumas tentativas, consegui uma particao das casas pretas nas condicoes acima. No caso 8x8, a particao consiste de exatamente 10 subconjuntos disjuntos cuja uniao eh o conjunto das 32 casas pretas. Eu nao conhecia este problema e duvido que seja conhecido como um teorema de combinatoria, ou um caso particular de um tal teorema, ateh porque esta area da matematica eh bem pouco estruturada, ou seja, nao existe uma grande teoria organizada de combinatoria, da mesma maneira que existe uma teoria bem organizada de equacoes diferenciais ou de geometria algebrica. Combinatoria ainda estah na fase em que os problemas sao, em grande parte, resolvidos caso a caso, sem se apelar para uma teoria geral (que nao existe ainda!). []s, Claudio. -- Cabeçalho original --- De: [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: Data: Wed, 4 Apr 2007 21:45:01 -0300 Assunto: Re: RE: [obm-l] tabuleiro Prezado Cláudio, desculpe a minha falta de conhecimento, mas não entendi como você descobriu que as equações ideais são aquelas e não outras sem precisar escrever todas, ou seja, qual o critério estabelicido para saber que aquelas 10 e não outras são as equações que nos darão a soma desejada. Outra pergunta, esse problema é conhecido em forma de algum teorema ou é apenasm mais um dos vários problemas que envolvem tabuleiros? Um abraço, Vanderlei Em (23:08:54), obm-l@mat.puc-rio.br escreveu: Voce achou uma configuracao que funciona. Mas o problema eh provar que qualquer configuracao que obedece ao enunciado tem soma m(m+1). A primeira observacao eh que voce pode reduzir o problema a metade pois se a soma das casas pretas for m(m+1)/2, entao a soma das casas brancas tambem serah m(m+1)/2. Por exemplo, num tabuleiro 8x8 (o problema original), suponha que voce quer descobrir a soma das casas pretas (ou seja, as casas x(i,j) com i+j par - estou supondo que o canto superior esquerdo - casa x(1,1) - eh preto) por meio da solucao de um sistema linear que implementa as condicoes do enunciado. Este sistema consiste de 32 equacoes (uma para cada casa branca) em 32 incognitas (os valores das casas pretas). Por exemplo, algumas das equacoes sao: x(1,1)+x(2,2)+x(1,3)=1 (vizinhos da casa (1,2)) x(3,7)+x(4,6)+x(4,8)+x(5,7)=1 (vizinhos da casa (4,7)) x(7,1)+x(8,2)=1 (vizinhos da casa (8,1)) etc... No entanto, voce quer apenas a soma x(1,1)+x(1,3)+x(1,5)+...+x(8,8) e nao o valor de cada variavel individualmente (ateh porque existe uma infinidade de solucoes - o sistema tem posto 32 - alias, um outro problema interessante eh determinar o posto do sistema ou, equivalentemente, o numero maximo de casas do tabuleiro cujo valor pode ser escolhido arbitrariamente). O que voce tem que fazer, entao, eh tomar um subconjunto dessas 32 equacoes tal que cada variavel aparece em exatamente uma equacao desse subconjunto. Dai, somando as equacoes voce obterah a soma desejada. Um tal subconjunto consiste de exatamente 10 equacoes (veja abaixo). Como o lado esquerdo de cada uma delas eh 1, a soma desejada eh 10. De forma totalmente analoga, voce calcula a soma das casas brancas - tambem igual a 10, claro! Logo, a soma do tabuleiro eh 20. Pra ver que o subconjunto acima consiste de 10 equacoes, o melhor eh visualizar o tabuleiro, onde * representa uma casa branca e letras representam as incognitas das 10 equacoes (duas casas com letras iguais representam incognitas que aparecem numa mesma equacao - por exemplo, a primeira equacao mencionada acima eh representada pela letra a, a terceira pela letra k e segunda nao estah entre as 10): a * a * t * t * c * b * b * e * c * g * h * h * k * g * s * p * O mesmo procedimento funciona no caso geral: num tabuleiro 2mx2m as casas pretas (e as brancas) geram 2m^2 equacoes em 2m^2 incognitas, das quais podemos extrair um subconjunto com m(m+1)/2 equacoes tal que cada incognita aparece em exatamente uma equacao. Uma prova disso pode ser dada por inducao (por exemplo, adicione 2 linhas e 2 colunas ao tabuleiro acima e veja o que acontece) []s, Claudio. -- Cabeçalho original --- De: João Gilberto Ponciano Pereira [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: [EMAIL PROTECTED] Data: Tue, 3 Apr 2007 19:20:34 -0300 Assunto: RE: [obm-l] tabuleiro Uma configuação que sempre dá certo para um tabuleiro 2nx2n é a seguinte: Imagine uma matriz 2n x 2n em camadas... a camada externa seria composta pela linha 1 e 2n mais
Re: RE: [obm-l] tabuleiro
Prezado Cláudio, desculpe a minha falta de conhecimento, mas não entendi como você descobriu que as equações ideais são aquelas e não outras sem precisar escrever todas, ou seja, qual o critério estabelicido para saber que aquelas 10 e não outras são as equações que nos darão a soma desejada. Outra pergunta, esse problema é conhecido em forma de algum teorema ou é apenasm mais um dos vários problemas que envolvem tabuleiros? Um abraço, Vanderlei Em (23:08:54), obm-l@mat.puc-rio.br escreveu: Voce achou uma configuracao que funciona. Mas o problema eh provar que qualquer configuracao que obedece ao enunciado tem soma m(m+1). A primeira observacao eh que voce pode reduzir o problema a metade pois se a soma das casas pretas for m(m+1)/2, entao a soma das casas brancas tambem serah m(m+1)/2. Por exemplo, num tabuleiro 8x8 (o problema original), suponha que voce quer descobrir a soma das casas pretas (ou seja, as casas x(i,j) com i+j par - estou supondo que o canto superior esquerdo - casa x(1,1) - eh preto) por meio da solucao de um sistema linear que implementa as condicoes do enunciado. Este sistema consiste de 32 equacoes (uma para cada casa branca) em 32 incognitas (os valores das casas pretas). Por exemplo, algumas das equacoes sao: x(1,1)+x(2,2)+x(1,3)=1 (vizinhos da casa (1,2)) x(3,7)+x(4,6)+x(4,8)+x(5,7)=1 (vizinhos da casa (4,7)) x(7,1)+x(8,2)=1 (vizinhos da casa (8,1)) etc... No entanto, voce quer apenas a soma x(1,1)+x(1,3)+x(1,5)+...+x(8,8) e nao o valor de cada variavel individualmente (ateh porque existe uma infinidade de solucoes - o sistema tem posto 32 - alias, um outro problema interessante eh determinar o posto do sistema ou, equivalentemente, o numero maximo de casas do tabuleiro cujo valor pode ser escolhido arbitrariamente). O que voce tem que fazer, entao, eh tomar um subconjunto dessas 32 equacoes tal que cada variavel aparece em exatamente uma equacao desse subconjunto. Dai, somando as equacoes voce obterah a soma desejada. Um tal subconjunto consiste de exatamente 10 equacoes (veja abaixo). Como o lado esquerdo de cada uma delas eh 1, a soma desejada eh 10. De forma totalmente analoga, voce calcula a soma das casas brancas - tambem igual a 10, claro! Logo, a soma do tabuleiro eh 20. Pra ver que o subconjunto acima consiste de 10 equacoes, o melhor eh visualizar o tabuleiro, onde * representa uma casa branca e letras representam as incognitas das 10 equacoes (duas casas com letras iguais representam incognitas que aparecem numa mesma equacao - por exemplo, a primeira equacao mencionada acima eh representada pela letra a, a terceira pela letra k e segunda nao estah entre as 10): a * a * t * t * c * b * b * e * c * g * h * h * k * g * s * p * O mesmo procedimento funciona no caso geral: num tabuleiro 2mx2m as casas pretas (e as brancas) geram 2m^2 equacoes em 2m^2 incognitas, das quais podemos extrair um subconjunto com m(m+1)/2 equacoes tal que cada incognita aparece em exatamente uma equacao. Uma prova disso pode ser dada por inducao (por exemplo, adicione 2 linhas e 2 colunas ao tabuleiro acima e veja o que acontece) []s, Claudio. -- Cabeçalho original --- De: João Gilberto Ponciano Pereira [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: [EMAIL PROTECTED] Data: Tue, 3 Apr 2007 19:20:34 -0300 Assunto: RE: [obm-l] tabuleiro Uma configuação que sempre dá certo para um tabuleiro 2nx2n é a seguinte: Imagine uma matriz 2n x 2n em camadas... a camada externa seria composta pela linha 1 e 2n mais as colunas 1 e 2n. A segunda camada seria para as linhas 2 e 2n-1 (excluindo os elementos das pontas, que já fazem parte da camada externa) e as colunas na mesma configuração. Logo, uma matriz 2n x 2n teria n camadas. Uma configuração que sempre funciona é atribuir o valor 0.5 para as camadas ímpares e 0 para as camadas pares. alguns exemplos: 2x2: 0.5 0.5 0.5 0.5 4x4 0.5 0.5 0.5 0.5 0.5 0.0 0.0 0.5 0.5 0.0 0.0 0.5 0.5 0.5 0.5 0.5 6x6 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.0 0.0 0.0 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.0 0.0 0.0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 Agora é questão de braço para chegar na fórmula m(m+1) por indução, vamos colocar uma casca nova num tabuleiro 2m x 2m existente. f(m+2) = f(m) + CascaNova, sendo que CascaNova = (m+2) * 4 - 2 (o menos 2 é devido aos vértices) (m+2) * (m+3) = m (m+1) + 4m + 8 -2 E como a fórmula funciona para m=1 (tabuleiro 2x2) e m=2(tabuleiro 4x4) funciona para todos, certo? SDS JG [João Gilberto Ponciano Pereira] -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of claudio.buffara Sent: Tuesday, April 03, 2007 6:11 PM To: obm-l Subject: Re:[obm-l] tabuleiro De: [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: Data: Mon, 2 Apr 2007 21:25:39 -0300 Assunto: [obm-l
Re: [obm-l] tabuleiro
Talvez o enunciado esteja mal escrito! O que ele quiz dizer é que a soma dos números das casas vizinhas de qualquer casa é igual a 1. Na matriz, por exemplo, as vizinhas do elemento a14 são a13 a15 e a24, cuja soma não é 1. Este foi apenas um exemplo, pois existem casas com 4 vizinhas e a soma das quatro deveria ser 1. Eu já tentei muita coisa, mas não estou conseguindo... Em (23:09:48), obm-l@mat.puc-rio.br escreveu: Ola acredito que nao.. veja esta matriz q satisfaz o que ele diz: 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 cuja soma é 32.. veja ai abracos, Salhab On 4/2/07, vandermath wrote: Mas tem casa que tem mais de uma vizinha não é verdade? eu acho que a resposta não era essa, era 20. Obrigado! Em (22:12:01), obm-l@mat.puc-rio.br escreveu: Ola, ele é 8x8, entao, a soma de cada fila é 4.. para ver isso, basta pegarmos: (a11 + a12) + (a13 + a14) + (a15 + a16) + (a17 + a18) = 1 + 1 + 1 + 1 = 4 assim será em cada uma das linhas.. logo, a soma de todos os numeros é: 4x8 = 32 abracos, Salhab On 4/2/07, vandermath wrote: Alguém poderia me ajudar com essa? Guilherme escreveu um número em cada casa de um tabuleiro 8 x8 (64 casas), de modo que a soma dos números das casas vizinhas de cada tabuleiro é igual a 1. Calcule a soma de todos os números escritos por Guilherme. Observação: duas casas são vizinhas se possuem um lado comum. Obrigado, Vanderlei = 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 = --
Re: [obm-l] tabuleiro
Ola, acho que agora entendi! a soma de todos eh 1.. eh isso? vou tentar novamente dps abracos, Salhab On 4/3/07, vandermath [EMAIL PROTECTED] wrote: Talvez o enunciado esteja mal escrito! O que ele quiz dizer é que a soma dos números das casas vizinhas de qualquer casa é igual a 1. Na matriz, por exemplo, as vizinhas do elemento a14 são a13 a15 e a24, cuja soma não é 1. Este foi apenas um exemplo, pois existem casas com 4 vizinhas e a soma das quatro deveria ser 1. Eu já tentei muita coisa, mas não estou conseguindo... Em (23:09:48), obm-l@mat.puc-rio.br escreveu: Ola acredito que nao.. veja esta matriz q satisfaz o que ele diz: 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 cuja soma é 32.. veja ai abracos, Salhab On 4/2/07, vandermath wrote: Mas tem casa que tem mais de uma vizinha não é verdade? eu acho que a resposta não era essa, era 20. Obrigado! Em (22:12:01), obm-l@mat.puc-rio.br escreveu: Ola, ele é 8x8, entao, a soma de cada fila é 4.. para ver isso, basta pegarmos: (a11 + a12) + (a13 + a14) + (a15 + a16) + (a17 + a18) = 1 + 1 + 1 + 1 = 4 assim será em cada uma das linhas.. logo, a soma de todos os numeros é: 4x8 = 32 abracos, Salhab On 4/2/07, vandermath wrote: Alguém poderia me ajudar com essa? Guilherme escreveu um número em cada casa de um tabuleiro 8 x8 (64 casas), de modo que a soma dos números das casas vizinhas de cada tabuleiro é igual a 1. Calcule a soma de todos os números escritos por Guilherme. Observação: duas casas são vizinhas se possuem um lado comum. Obrigado, Vanderlei = 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 = -- = 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 =
Re:[obm-l] tabuleiro
De:[EMAIL PROTECTED] Para:obm-l@mat.puc-rio.br Cópia: Data:Mon, 2 Apr 2007 21:25:39 -0300 Assunto:[obm-l] tabuleiro Alguém poderia me ajudar com essa? Guilherme escreveu um número em cada casa de um tabuleiro 8 x8 (64 casas), de modo que a soma dos números das casas vizinhas de cada tabuleiro é igual a 1. Calcule a soma de todos os números escritos por Guilherme. Observação: duas casas são vizinhas se possuem um lado comum. Obrigado, Vanderlei Acho que o enunciado deveria ser: dada qualquer casa do tabuleiro, a soma dos números nas casas vizinhas a ela é igual a 1 Nesse caso, proponho a seguinte generalização: Dado um tabuleiro 2mx2m (m inteiro positivo) nas condições do enunciado, a soma dos números escritos no tabuleiro é igual a m(m+1). Em particular, num tabuleiro 8x8 (m=4), a soma é 20. []s, Claudio.
RE: [obm-l] tabuleiro
Voce achou uma configuracao que funciona. Mas o problema eh provar que qualquer configuracao que obedece ao enunciado tem soma m(m+1). A primeira observacao eh que voce pode reduzir o problema a metade pois se a soma das casas pretas for m(m+1)/2, entao a soma das casas brancas tambem serah m(m+1)/2. Por exemplo, num tabuleiro 8x8 (o problema original), suponha que voce quer descobrir a soma das casas pretas (ou seja, as casas x(i,j) com i+j par - estou supondo que o canto superior esquerdo - casa x(1,1) - eh preto) por meio da solucao de um sistema linear que implementa as condicoes do enunciado. Este sistema consiste de 32 equacoes (uma para cada casa branca) em 32 incognitas (os valores das casas pretas). Por exemplo, algumas das equacoes sao: x(1,1)+x(2,2)+x(1,3)=1 (vizinhos da casa (1,2)) x(3,7)+x(4,6)+x(4,8)+x(5,7)=1 (vizinhos da casa (4,7)) x(7,1)+x(8,2)=1 (vizinhos da casa (8,1)) etc... No entanto, voce quer apenas a soma x(1,1)+x(1,3)+x(1,5)+...+x(8,8) e nao o valor de cada variavel individualmente (ateh porque existe uma infinidade de solucoes - o sistema tem posto 32 - alias, um outro problema interessante eh determinar o posto do sistema ou, equivalentemente, o numero maximo de casas do tabuleiro cujo valor pode ser escolhido arbitrariamente). O que voce tem que fazer, entao, eh tomar um subconjunto dessas 32 equacoes tal que cada variavel aparece em exatamente uma equacao desse subconjunto. Dai, somando as equacoes voce obterah a soma desejada. Um tal subconjunto consiste de exatamente 10 equacoes (veja abaixo). Como o lado esquerdo de cada uma delas eh 1, a soma desejada eh 10. De forma totalmente analoga, voce calcula a soma das casas brancas - tambem igual a 10, claro! Logo, a soma do tabuleiro eh 20. Pra ver que o subconjunto acima consiste de 10 equacoes, o melhor eh visualizar o tabuleiro, onde * representa uma casa branca e letras representam as incognitas das 10 equacoes (duas casas com letras iguais representam incognitas que aparecem numa mesma equacao - por exemplo, a primeira equacao mencionada acima eh representada pela letra a, a terceira pela letra k e segunda nao estah entre as 10): a * a * t * t * * a * b * t * e c * b * b * e * * c * b * h * e c * g * h * h * * g * g * h * p k * g * s * p * * k * s * s * p O mesmo procedimento funciona no caso geral: num tabuleiro 2mx2m as casas pretas (e as brancas) geram 2m^2 equacoes em 2m^2 incognitas, das quais podemos extrair um subconjunto com m(m+1)/2 equacoes tal que cada incognita aparece em exatamente uma equacao. Uma prova disso pode ser dada por inducao (por exemplo, adicione 2 linhas e 2 colunas ao tabuleiro acima e veja o que acontece) []s, Claudio. -- Cabeçalho original --- De: João Gilberto Ponciano Pereira [EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: [EMAIL PROTECTED] Data: Tue, 3 Apr 2007 19:20:34 -0300 Assunto: RE: [obm-l] tabuleiro Uma configuação que sempre dá certo para um tabuleiro 2nx2n é a seguinte: Imagine uma matriz 2n x 2n em camadas... a camada externa seria composta pela linha 1 e 2n mais as colunas 1 e 2n. A segunda camada seria para as linhas 2 e 2n-1 (excluindo os elementos das pontas, que já fazem parte da camada externa) e as colunas na mesma configuração. Logo, uma matriz 2n x 2n teria n camadas. Uma configuração que sempre funciona é atribuir o valor 0.5 para as camadas ímpares e 0 para as camadas pares. alguns exemplos: 2x2: 0.5 0.5 0.5 0.5 4x4 0.5 0.5 0.5 0.5 0.5 0.0 0.0 0.5 0.5 0.0 0.0 0.5 0.5 0.5 0.5 0.5 6x6 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.0 0.0 0.0 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.5 0.5 0.0 0.0 0.0 0.0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 Agora é questão de braço para chegar na fórmula m(m+1) por indução, vamos colocar uma casca nova num tabuleiro 2m x 2m existente. f(m+2) = f(m) + CascaNova, sendo que CascaNova = (m+2) * 4 - 2 (o menos 2 é devido aos vértices) (m+2) * (m+3) = m (m+1) + 4m + 8 -2 E como a fórmula funciona para m=1 (tabuleiro 2x2) e m=2(tabuleiro 4x4) funciona para todos, certo? SDS JG [João Gilberto Ponciano Pereira] -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of claudio.buffara Sent: Tuesday, April 03, 2007 6:11 PM To: obm-l Subject: Re:[obm-l] tabuleiro De:[EMAIL PROTECTED] Para: obm-l@mat.puc-rio.br Cópia: Data: Mon, 2 Apr 2007 21:25:39 -0300 Assunto: [obm-l] tabuleiro Alguém poderia me ajudar com essa? Guilherme escreveu um número em cada casa de um tabuleiro 8 x8 (64 casas), de modo que a soma dos números das casas vizinhas de cada tabuleiro é igual a 1. Calcule a soma de todos os números escritos por Guilherme. Observação: duas casas são vizinhas se possuem um lado comum. Obrigado, Vanderlei Acho que o
Re: [obm-l] tabuleiro
Ola, ele é 8x8, entao, a soma de cada fila é 4.. para ver isso, basta pegarmos: (a11 + a12) + (a13 + a14) + (a15 + a16) + (a17 + a18) = 1 + 1 + 1 + 1 = 4 assim será em cada uma das linhas.. logo, a soma de todos os numeros é: 4x8 = 32 abracos, Salhab On 4/2/07, vandermath [EMAIL PROTECTED] wrote: Alguém poderia me ajudar com essa? Guilherme escreveu um número em cada casa de um tabuleiro 8 x8 (64 casas), de modo que a soma dos números das casas vizinhas de cada tabuleiro é igual a 1. Calcule a soma de todos os números escritos por Guilherme. Observação: duas casas são vizinhas se possuem um lado comum. Obrigado, Vanderlei = 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 =
Re: [obm-l] tabuleiro
Mas tem casa que tem mais de uma vizinha não é verdade? eu acho que a resposta não era essa, era 20. Obrigado! Em (22:12:01), obm-l@mat.puc-rio.br escreveu: Ola, ele é 8x8, entao, a soma de cada fila é 4.. para ver isso, basta pegarmos: (a11 + a12) + (a13 + a14) + (a15 + a16) + (a17 + a18) = 1 + 1 + 1 + 1 = 4 assim será em cada uma das linhas.. logo, a soma de todos os numeros é: 4x8 = 32 abracos, Salhab On 4/2/07, vandermath wrote: Alguém poderia me ajudar com essa? Guilherme escreveu um número em cada casa de um tabuleiro 8 x8 (64 casas), de modo que a soma dos números das casas vizinhas de cada tabuleiro é igual a 1. Calcule a soma de todos os números escritos por Guilherme. Observação: duas casas são vizinhas se possuem um lado comum. Obrigado, Vanderlei = 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 = --
Re: [obm-l] tabuleiro
Ola acredito que nao.. veja esta matriz q satisfaz o que ele diz: 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 cuja soma é 32.. veja ai abracos, Salhab On 4/2/07, vandermath [EMAIL PROTECTED] wrote: Mas tem casa que tem mais de uma vizinha não é verdade? eu acho que a resposta não era essa, era 20. Obrigado! Em (22:12:01), obm-l@mat.puc-rio.br escreveu: Ola, ele é 8x8, entao, a soma de cada fila é 4.. para ver isso, basta pegarmos: (a11 + a12) + (a13 + a14) + (a15 + a16) + (a17 + a18) = 1 + 1 + 1 + 1 = 4 assim será em cada uma das linhas.. logo, a soma de todos os numeros é: 4x8 = 32 abracos, Salhab On 4/2/07, vandermath wrote: Alguém poderia me ajudar com essa? Guilherme escreveu um número em cada casa de um tabuleiro 8 x8 (64 casas), de modo que a soma dos números das casas vizinhas de cada tabuleiro é igual a 1. Calcule a soma de todos os números escritos por Guilherme. Observação: duas casas são vizinhas se possuem um lado comum. Obrigado, Vanderlei = 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 =
Re: [obm-l] Tabuleiro 3 x 2n com dominos 2x1
Este problema ja caiu numa olimpiada bulgara.Depois eu confiro a resposta mas esta coisa de autovalores e melhor com algumas coisas que ninguem aprende sobre o poder da algebra linear...Claudio Buffara [EMAIL PROTECTED] wrote: Oi, Nicolau:Eu calculei o no. de maneiras de se cobrir um tabuleiro 3 x 2n com dominos2x1 e achei a recorrencia:f(n) = 3*f(n-1) + g(n-1)g(n) = 2*f(n-1) + g(n-1)f(1) = 3, g(1) = 2onde f(n) = no. desejado e g(n) = no. de maneiras de se chegar a casa 2n com2 dominos deitados.Eliminando g(n): f(n) = 4*f(n-1) - f(n-2); f(1) = 3; f(2) = 11.f(n) = 3, 11, 41, 153, 571, 2131, ...Resolvendo eu achei a formula explicita para f(n):f(n) = (1/6)*[(3+raiz(3))*(2+raiz(3))^n + (3-raiz(3))*(2-raiz(3))^n]Minha duvida: Existe alguma razao para os autovalores (2+ou-raiz(3)) seremos mesmos que no caso do pilar ou foi soh coincidencia? Qual o papel (ouinterpretacao) dos autovalores nesse tipo de problema?Um abraco,Claudio.on 05.10.03 23:12, Claudio Buffara at [EMAIL PROTECTED] wrote: on 04.10.03 11:44, Nicolau C. Saldanha at [EMAIL PROTECTED] wrote: On Thu, Oct 02, 2003 at 09:11:23PM -0300, [EMAIL PROTECTED] wrote: De quantas maneiras pode ser construído um pilar 2x2xn com tijolos 2x1x1? Calculei os primeiros termos desta seqüência: 1,2,9,32,121,450,1681,6272,23409,87362,326041,1216800,... e procurei na enciclopédia de seqüências de inteiros: http://www.research.att.com/~njas/sequences/Seis.html A enciclopédia conhece a seqüência, ela se chama A006253. A enciclopédia também indica que este problema está no Concrete Mathematics, de Graham, Knuth e Patashnik, página 360. A página também dá uma fórmula bem simples que eu não vou copiar (para que vocês possam tentar obter sozinhos e tb para que olhem as referências). Oi, Nicolau: Depois de umas 5 tentativas frustradas (onde eu invariavelmente esquecia de levar em conta alguma alternativa), finalmente consegui descobrir a relacao de recorrencia para esse problema. Sejam: f(n) = no. de maneiras de se construir um pilar de altura n; g(n) = no. de maneiras de se chegar ao n-esimo andar com 2 tijolos colocados verticalmente (apoiados no (n-2)-esimo andar) e lado a lado. Por enumeracao direta obtemos: f(1) = 2 e f(2) = 9 g(1) = 0 e g(2) = 4 As relacoes de recorrencia sao: g(n) = 4*f(n-2) + g(n-1) f(n) = 2*f(n-1) + f(n-2) + g(n) Justificativa: g(n): Se temos um plateau no (n-2)-esimo andar, entao podemos colocar 2 tijolos verticalmente e lado a lado para chegar ao n-esimo andar de 4 maneiras (em cada uma das 4 faces do pilar). Esse eh o termo 4*f(n-2) Se ja existem 2 tijolos verticais no (n-1)-esimo andar (portanto, apoiados no (n-3)-esimo andar), entao, soh teremos 1 maneira de apoiar tijolos verticais no (n-2)-esimo andar. Esse eh o termo g(n-1). f(n): Se temos um plateau no (n-1)-esimo andar, entao podemos colocar 2 tijolos horizontais de 2 maneiras para completar o n-esimo andar (norte-sul ou leste-oeste). Esse eh o termo 2*f(n-1). Se temos um plateau no (n-2)-esimo andar, entao podemos colocar 4 tijolos verticais e chegar ao n-esimo andar. Esse eh o termo f(n-2) Se temos dois tijolos verticais lado a lado no n-esimo andar (portanto, apoiados no (n-2)-esimo andar), soh teremos uma maneira de colocar o tijolo restante e completar o n-esimo andar. Esse eh o termo g(n). * Calculando, obtemos: n g(n) f(n) 1 0 2 2 4 9 3 12 32 4 48 121 5 176 450 6 660 1681 7 2460 6272 8 9184 23409 9 34272 87362 10 127908 326041 * Pondo X(n) = (g(n),f(n),f(n-1))^transposto, a recorrencia se torna: X(n) = P*X(n-1) onde P eh a matriz: 1 0 4 1 2 5 0 1 0 cujos autovalores sao -1, 2+raiz(3) e 2-raiz(3). Supondo uma solucao da forma: f(n) = a*(-1)^(n-1) + b*(2+raiz(3))^(n-1) + c*(2-raiz(3))^(n-1) e resolvendo o sistema resultante pela substituicao de n = 1, 2 e 3, eu achei a expressao: f(n) = (-1)^n/3 + [(2+raiz(3))^(n+1) + (2-raiz(3))^(n+1)]/6 * De fato, o problema acabou sendo mais sutil do que eu pensava inicialmente. Agora eu entendo o que voce disse sobre a dificuldade de se resolver o caso de um paralelepipedo m x n x p. Um abraco, Claudio. =Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=Yahoo! Mail - o melhor webmail do Brasil. Saiba mais!