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

[Faelccmm@xxxxxxx]

Valeu Domingos,

A única passagem que não entendi de sua solução foi:

(... 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 ...)



Em uma mensagem de 18/9/2004 20:22:18 Hora padrão leste da Am. Sul, dopikas@uol.com.br escreveu:


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