[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: RE: [obm-l] tabuleiro
O criterio foi a observacao de que eu nao preciso saber o valor de cada casa preta, mas simplesmente a soma desses valores.
No caso, eu simplesmente achei 10 casas brancas tais que as casas pretas vizinhas a cada uma delas nao sao vizinhas de
nenhuma das outras 9 e tomei as equacoes relativas aquelas casas brancas.
Pra fazer isso eu desenhei um tabuleiro e, apos algumas tentativas, consegui uma particao das casas pretas nas condicoes acima.
No caso 8x8, a particao consiste de exatamente 10 subconjuntos disjuntos cuja uniao eh o conjunto das 32 casas pretas.
Eu nao conhecia este problema e duvido que seja conhecido como um teorema de combinatoria, ou um caso particular de um tal
teorema, ateh porque esta area da matematica eh bem pouco estruturada, ou seja, nao existe uma grande teoria organizada de
combinatoria, da mesma maneira que existe uma teoria bem organizada de equacoes diferenciais ou de geometria algebrica.
Combinatoria ainda estah na fase em que os problemas sao, em grande parte, resolvidos caso a caso, sem se apelar para uma
teoria geral (que nao existe ainda!).
[]s,
Claudio.
---------- 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
=========================================================================