[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
=========================================================================