[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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" jpere@vesper.com.br
>Para: obm-l@mat.puc-rio.br
>Cópia: claudio.buffara@terra.com.br
>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: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br]On
>Behalf Of claudio.buffara
>> Sent: Tuesday, April 03, 2007 6:11 PM
>> To: obm-l
>> Subject: Re:[obm-l] tabuleiro
>>
>>
>>
>>
>> De: owner-obm-l@mat.puc-rio.br
>> 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.
>>
>>
>>
>
>=========================================================================
>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
>=========================================================================
>
>----------