Re: [obm-l] Olimpiadas Russas ( 104 a 107 )

["Fabio Dias Moreira" <fabio@xxxxxxxxxxxxxxxxxxx>]

Paulo Santa Rita said:
> [...]
> 105 -  Os elementos de uma matriz 4x4 sao os sinais "+" e "-". ( veja
> abaixo  ). E permitido modificar simultaneamente todos os sinais de uma
> linha,  coluna ou diagonal pelos seus opostos, tantas vezes quanto
> desejarmos. A) Prove que com as operacoes acima definidas, nunca
> conseguiremos uma  matriz formada apenas com sinais positivos.
> B) Prove que se a matriz for 8x8 ( com as mesmas operacoes definidas ) ,
>  qualquer que seja o preenchimento, se nenhum canto ( A11, A18, A81 e
> A88 )  tiver um sinal negativo,"-", sera impossivel obtermos uma matriz
> formada  apenas com sinais positivos.
>
> Matirz 4x4 :
> A12 = "-"
> Aij = "+" se (i,j) # (1,2)
> OBS : "#" significa "e diferente de"
>
> IMPORTANTE : Neste problema, um "canto" e considerado uma diagonal
> formada  por um unico elemento. Logo, e permitido modificar apenas um
> canto.
> [...]

a) Considere as oito casas destacadas no diagrama (se possível, use uma
fonte de largura fixa):

.**.
*..*
*..*
.**.

Não é muito difícil ver que qualquer uma das operações afeta um número par
de casas destacadas. Portanto é impossível que todas as casas terminem com
um sinal de +, pois sempre haverá um número ímpar de sinais -, logo este
não pode ser zero.

b) Eu acho que a matriz

++++++++
++++++++
++++++++
++++++++
++++++++
++++++++
++++++++
++++++++

é um contra-exemplo.

[]s,

-- 
Fábio "ctg \pi" Dias Moreira


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