[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: RE: [obm-l] tabuleiro
---------- Cabeçalho original -----------
De: owner-obm-l@mat.puc-rio.br
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" 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
> >=========================================================================
> >
> >----------
>
=========================================================================
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
=========================================================================