RE: [obm-l] tabuleiro

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

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  * 
*  a  *  b  *  t  *  e 
c  *  b  *  b  *  e  * 
*  c  *  b  *  h  *  e 
c  *  g  *  h  *  h  * 
*  g  *  g  *  h  *  p 
k  *  g  *  s  *  p  * 
*  k  *  s  *  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
=========================================================================