Re: [obm-l] RE: [obm-l] 8ª Cone Sul - tabuleiro
Boa resolução também ! São 3 entradas para 3 opções em cada entrada {0,1,2}, logo 3^3 = 27.
Em uma mensagem de 20/9/2004 13:59:38 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu:
Estava pensando... O movimento descrito (altera 3 e mantém 1) não seria o
equivalente ao oposto (mantém 3 e altera 1?)
Tentei isso e deu certo. Seria mais ou menos em trabalhar com algarismos na
base 3. o resultado inicial seria:
1000
2000
0100
1100
...
Traduzindo para o movimento normal, teríamos:
0111
0222
1200
1011
...
Logo, fica fácil ver que poderíamos obter as 27 combinações sem repetição.
Só para dar a resposta completa:
0111
0222
1200
1011
1122
2100
2211
2022
0120
0201
0012
1020
1101
1212
2220
2001
2112
0210
0021
0102
1110
1221
1002
2010
2121
2202
SDS
JG
-Original Message-
From: Domingos Jr. [mailto:[EMAIL PROTECTED]
Sent: Sunday, September 19, 2004 10:06 AM
To: [EMAIL PROTECTED]
Subject: Re: [obm-l] 8ª Cone Sul - tabuleiro
[EMAIL PROTECTED] wrote:
> 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 ...)
>
a linha anterior (a inicial, por exemplo) tem 4 elementos, sendo que um
deles será mantido na linha seguinte.
desconsiderando esse cara que está fixo, sobram 3 elementos: sendo que x
deles são entradas 0 ou 1 e os outros 3 - x são entradas 2.
acho que agora fica claro por que a soma da linha seguinte é S' = S + x
- 2(3 - x), certo?
sinceramente, eu acho que 27 é um número grandinho, eu não teria saco
para 'escrever' a solução de um problema desses.
[ ]'s
[obm-l] RE: [obm-l] 8ª Cone Sul - tabuleiro
Estava pensando... O movimento descrito (altera 3 e mantém 1) não seria o
equivalente ao oposto (mantém 3 e altera 1?)
Tentei isso e deu certo. Seria mais ou menos em trabalhar com algarismos na
base 3. o resultado inicial seria:
1000
2000
0100
1100
...
Traduzindo para o movimento normal, teríamos:
0111
0222
1200
1011
...
Logo, fica fácil ver que poderíamos obter as 27 combinações sem repetição.
Só para dar a resposta completa:
0111
0222
1200
1011
1122
2100
2211
2022
0120
0201
0012
1020
1101
1212
2220
2001
2112
0210
0021
0102
1110
1221
1002
2010
2121
2202
SDS
JG
-Original Message-
From: Domingos Jr. [mailto:[EMAIL PROTECTED]
Sent: Sunday, September 19, 2004 10:06 AM
To: [EMAIL PROTECTED]
Subject: Re: [obm-l] 8ª Cone Sul - tabuleiro
[EMAIL PROTECTED] wrote:
> 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 ...)
>
a linha anterior (a inicial, por exemplo) tem 4 elementos, sendo que um
deles será mantido na linha seguinte.
desconsiderando esse cara que está fixo, sobram 3 elementos: sendo que x
deles são entradas 0 ou 1 e os outros 3 - x são entradas 2.
acho que agora fica claro por que a soma da linha seguinte é S' = S + x
- 2(3 - x), certo?
sinceramente, eu acho que 27 é um número grandinho, eu não teria saco
para 'escrever' a solução de um problema desses.
[ ]'s
=
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
=
Re: [obm-l] 8ª Cone Sul - tabuleiro
[EMAIL PROTECTED] wrote:
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 ...)
a linha anterior (a inicial, por exemplo) tem 4 elementos, sendo que um
deles será mantido na linha seguinte.
desconsiderando esse cara que está fixo, sobram 3 elementos: sendo que x
deles são entradas 0 ou 1 e os outros 3 - x são entradas 2.
acho que agora fica claro por que a soma da linha seguinte é S' = S + x
- 2(3 - x), certo?
sinceramente, eu acho que 27 é um número grandinho, eu não teria saco
para 'escrever' a solução de um problema desses.
[ ]'s
=
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
=
Re: [obm-l] Re: [obm-l] 8ª Cone Sul - tabuleiro
Valeu Paulo, Gostei da solução. Eu até sabia que eram 27 "4-uplas", mas não estava conseguindo provar. Veja como cheguei nas 27 "4-uplas": Tentei ordenar os números em ordem crescente, mas como há apenas 3 dígitos, haverá períodos, ou seja, 3 números da forma 0xyz, 3 números da forma 1xyz, 3 números da forma 2xyz, 3 números da forma 0x`y`z`, 3 números da forma 1x`y`z`, etc... Fui fazendo isso até chegar um momento em que não ocorrem repetições: 0111 0222 1002 1110 1221 2001 2112 2220 0021 0102 0210 1011 1122 1200 2010 2121 2202 0012 0120 0201 1212 1020 1101 2211 2022 2100 Temos, pois, 9*3 = 27 "4-uplas". Em uma mensagem de 18/9/2004 21:30:53 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu: Coloquei uma solução completa para este problema em http://www.teorema.mat.br/phpBB2/viewtopic.php?p=167#167 - Original Message - From: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 18, 2004 7:21 PM Subject: Re: [obm-l] 8ª Cone Sul - tabuleiro Ninguém sabe ? Em uma mensagem de 13/9/2004 22:40:55 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu: É 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, [EMAIL PROTECTED] 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.
Re: [obm-l] 8ª Cone Sul - tabuleiro
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, [EMAIL PROTECTED] 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,
> [EMAIL PROTECTED] 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.
>>
[obm-l] Re: [obm-l] 8ª Cone Sul - tabuleiro
Coloquei uma solução completa para este problema em http://www.teorema.mat.br/phpBB2/viewtopic.php?p=167#167 - Original Message - From: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Saturday, September 18, 2004 7:21 PM Subject: Re: [obm-l] 8ª Cone Sul - tabuleiro Ninguém sabe ? Em uma mensagem de 13/9/2004 22:40:55 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu: É 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, [EMAIL PROTECTED] 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. ---Outgoing mail is certified Virus Free.Checked by AVG anti-virus system (http://www.grisoft.com).Version: 6.0.766 / Virus Database: 513 - Release Date: 17/9/2004
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,
[EMAIL PROTECTED] 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
=
Re: [obm-l] 8ª Cone Sul - tabuleiro
Ninguém sabe ? Em uma mensagem de 13/9/2004 22:40:55 Hora padrão leste da Am. Sul, [EMAIL PROTECTED] escreveu: É 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, [EMAIL PROTECTED] 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.
Re: [obm-l] 8ª Cone Sul - tabuleiro
É 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, [EMAIL PROTECTED] 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.
[obm-l] 8ª Cone Sul - tabuleiro
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.
