---------- Cabeçalho original ----------- De: [EMAIL PROTECTED] Para: [email protected] 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), [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 > >========================================================================= > > > >---------- > ========================================================================= 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 =========================================================================
