[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] 8ª Cone Sul - tabuleiro



ok, pensando um pouco eu achei algo que deve levar a resposta:
considere a soma dos elementos de uma linha módulo 3, chame tal soma de S.
o procedimento para obter a próxima linha é manter o valor de um 
elemento da linha anterior e alterar os demais.
suponha que tenhamos 0 <= x <= 3 elementos {0, 1} dentre os elementos da 
linha anterior sem incluir o elemento selecionado e há 3 - x elementos 2 
dentre esses mesmos caras.
fica claro que a soma da próxima linha é S' = S + x - 2(3 - x) = S - 6 + 
3x = S (mod 3).

como a primeira linha tem soma 0, provamos que todas as linhas desse seu 
tabuleiro tem soma múltipla de 3.

agora veja que as somas possíveis são 0, 3 e 6, sendo que 0 só pode ser 
obtido de uma maneira e é a primeira linha do tabuleiro.
3 pode ser obtido como um 0 e três 1's (há 4 maneiras de dispô-los), ou 
como um 1, um 2 e dois 0's (2*binomial(4, 2) = 12 maneiras).
6 pode ser obtido como um 0 e três 2's (4 maneiras), ou como dois 1's e 
dois 2's (binomial(4, 2) = 6 maneiras).

eu imagino que seja possível conseguir todas essas possibilidades e aí 
vc teria uma demonstração de que não é possível construir nada maior, 
mas é só um palpite.

[ ]'s

> É uma questão do Cone Sul também ... Ninguém quer tentar ?
>
>
>
> Em uma mensagem de 12/9/2004 18:26:33 Hora padrão leste da Am. Sul, 
> Faelccmm@aol.com escreveu:
>
>
>>
>> Olá pessoal,
>>
>> Considere um tabuleiro de /n/ linhas e 4 colunas.
>> Na 1a linha são escritos 4 zeros (um em cada casa). A seguir, cada 
>> linha é obtida a partir da linha anterior realizando a seguinte 
>> operação: uma das casas, a escolher, é mantida como na linha 
>> anterior; as outras três são trocadas: se na linha anterior havia um 
>> 0 se coloca 1, se havia 1 se coloca 2 e se havia 2 se coloca 0.
>> Construa o maior tabuleiro possível com todas as suas linhas 
>> distintas e demonstre que é impossível construir um maior.
>>
>
>

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