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), [email protected] 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: [email protected] >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: [email protected] >> 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. >> >> >> > >========================================================================= >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 >========================================================================= > >----------
