Re: [obm-l] Novamente as gavetas
Oi, Fred:
A sua solucao tambem acha o menor numero de elementos que podem ser
escolhidos de {1,2,...,100} a fim de obter 2 cuja diferenca eh 12. Veja
abaixo.
on 11.05.04 14:49, Frederico Reis Marques de Brito at [EMAIL PROTECTED]
wrote:
Pois bem, então onde está o erro do seguinte raciocínio: separe os números
de 1 a 100 em conjuntos como os seguintes:
{1,13} , {2,14} ,{3,15}, ..., {12, 24}
{25,37} , {26, 38 }, ..., {36, 48}
{49, 61} , {50, 62} ,..., {60, 72}
{73, 84}, {74, 85} , ..., {84, 96}
Ops. Uma distracao sem importancia. A ultima linha deveria ser:
{73,85}, {74,86}, ..., {84,96}
e {97}, {98}, {99} , {100}. TEmos ao todo 4* 12 + 4 = 52 conjuntos
disjuntos cuja união dá o conjunto dos naturais de 1 a 100, inclusive. Dados
55 desses números, 2 terão que estar num mesmo subconjunto.
De fato, dados apenas 53 destes numeros, 2 terao que estar num mesmo
subconjunto. Ou seja, a sua solucao tambem acha o valor minimo possivel.
Isso não pode
ocorrer nos últimos 4 subconjuntos , que são unitários. Logo,
há dois números entre 1 e 100 que estão num dos primeiros 48 subconjuntos,
que são todos da forma {a , a+12} = a diferença entre esses dois números é
precisamente 12!??!?
[]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
=
Re: [obm-l] Novamente as gavetas
Na minha solução também bastam 53 números, já que foram formados 52
conjuntos...
Um abraço,
Fred.
From: Claudio Buffara [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: [obm-l] Novamente as gavetas
Date: Tue, 11 May 2004 15:24:30 -0300
Gostei! Por alguma razao, eu nunca me lembro de particionar o conjunto-base
em pares. A minha solucao foi mais complicada, mas acho que consegui
melhorar o resultado para 53 elementos (ao inves de 55).
[]s,
Claudio.
on 11.05.04 14:49, Frederico Reis Marques de Brito at
[EMAIL PROTECTED]
wrote:
Pois bem, então onde está o erro do seguinte raciocínio: separe os
números
de 1 a 100 em conjuntos como os seguintes:
{1,13} , {2,14} ,{3,15}, ..., {12, 24}
{25,37} , {26, 38 }, ..., {36, 48}
{49, 61} , {50, 62} ,..., {60, 72}
{73, 84}, {74, 85} , ..., {84, 96}
e {97}, {98}, {99} , {100}. TEmos ao todo 4* 12 + 4 = 52 conjuntos
disjuntos cuja união dá o conjunto dos naturais de 1 a 100, inclusive.
Dados
55 desses números, 2 terão que estar num mesmo subconjunto. Isso não
pode
ocorrer nos últimos 4 subconjuntos , que são unitários. Logo,
há dois números entre 1 e 100 que estão num dos primeiros 48
subconjuntos,
que são todos da forma {a , a+12} = a diferença entre esses dois
números é
precisamente 12!??!?
Um abraço,
FRed.
From: Claudio Buffara [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: [obm-l] Novamente as gavetas
Date: Tue, 11 May 2004 13:59:05 -0300
on 11.05.04 12:48, Frederico Reis Marques de Brito at
[EMAIL PROTECTED]
wrote:
Bom, dessa vez o resultado é verdadeiro.
Provar que dados 55 números inteiros entre 1 e 100, incluindo estes,
existem dois cuja diferença é exatamente 12.
Um abraço a todos,
Fred.
=
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
=
_
MSN Messenger: converse com os seus amigos online.
http://messenger.msn.com.br
=
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] Novamente as gavetas
on 11.05.04 12:48, Frederico Reis Marques de Brito at [EMAIL PROTECTED] wrote: Bom, dessa vez o resultado é verdadeiro. Provar que dados 55 números inteiros entre 1 e 100, incluindo estes, existem dois cuja diferença é exatamente 12. Um abraço a todos, Fred. Oi, Fred: E quanto aos 60 numeros abaixo? 1,2,3,4,5,6,7,8,9,10,11,12, 25,26,27,28,29,30,31,32,33,34,35,36, 49,50,51,52,53,54,55,56,57,58,59,60, 63,64,64,66,67,68,69,70,71,72,73,74, 87,88,89,90,91,92,93,94,95,96,97,98. []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 =
Re: [obm-l] Novamente as gavetas
Pois bem, então onde está o erro do seguinte raciocínio: separe os números
de 1 a 100 em conjuntos como os seguintes:
{1,13} , {2,14} ,{3,15}, ..., {12, 24}
{25,37} , {26, 38 }, ..., {36, 48}
{49, 61} , {50, 62} ,..., {60, 72}
{73, 84}, {74, 85} , ..., {84, 96}
e {97}, {98}, {99} , {100}. TEmos ao todo 4* 12 + 4 = 52 conjuntos
disjuntos cuja união dá o conjunto dos naturais de 1 a 100, inclusive. Dados
55 desses números, 2 terão que estar num mesmo subconjunto. Isso não pode
ocorrer nos últimos 4 subconjuntos , que são unitários. Logo,
há dois números entre 1 e 100 que estão num dos primeiros 48 subconjuntos,
que são todos da forma {a , a+12} = a diferença entre esses dois números é
precisamente 12!??!?
Um abraço,
FRed.
From: Claudio Buffara [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: [obm-l] Novamente as gavetas
Date: Tue, 11 May 2004 13:59:05 -0300
on 11.05.04 12:48, Frederico Reis Marques de Brito at
[EMAIL PROTECTED]
wrote:
Bom, dessa vez o resultado é verdadeiro.
Provar que dados 55 números inteiros entre 1 e 100, incluindo estes,
existem dois cuja diferença é exatamente 12.
Um abraço a todos,
Fred.
Oi, Fred:
E quanto aos 60 numeros abaixo?
1,2,3,4,5,6,7,8,9,10,11,12,
25,26,27,28,29,30,31,32,33,34,35,36,
49,50,51,52,53,54,55,56,57,58,59,60,
63,64,64,66,67,68,69,70,71,72,73,74,
87,88,89,90,91,92,93,94,95,96,97,98.
[]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
=
_
MSN Messenger: converse com os seus amigos online.
http://messenger.msn.com.br
=
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] Novamente as gavetas
on 11.05.04 12:48, Frederico Reis Marques de Brito at [EMAIL PROTECTED] wrote: Bom, dessa vez o resultado é verdadeiro. Provar que dados 55 números inteiros entre 1 e 100, incluindo estes, existem dois cuja diferença é exatamente 12. Um abraço a todos, Fred. O contra-exemplo que eu tinha em mente era: 01,02,03,04,05,06,07,08,09,10,11,12, 25,26,27,28,29,30,31,32,33,34,35,36, 49,50,51,52,53,54,55,56,57,58,59,60, 73,74,75,76,77,78,79,80,81,82,83,84, 97,98,99,100. Obviamente, isso soh prova que podemos escolher 52 numeros sem que tenhamos dois cuja diferenca eh 12. * Agora, a solucao: Vamos reduzir os 55 numeros escolhidos mod 12 e distribui-los por dentre as 12 classes de congruencia mod 12. Como 12*4 = 48 55, teremos os seguintes casos: Caso 1: uma das classes de congruencia mod 12 tem pelo menos 6 elementos. Caso 2: nenhuma classe de congruencia mod 12 tem mais do que 5 elementos. - Caso 1: Chamemos os 6 menores elementos da tal classe de: m, m+12*a, m+12*(a+b), m+12*(a+b+c), m+12*(a+b+c+d), m+12*(a+b+c+d+e), onde m, a, b, c, d, e sao inteiros positivos. Se a, b, c, d, e forem todos = 2, entao teremos: m + 12*(a+b+c+d+e) = m + 12*10 = m + 120 == contradicao, pois m + 12*(a+b+c+d+e) = 100. Logo, um dentre a, b, c, d, e eh igual a 1 e acabou. - Caso 2: Nesse caso, teremos pelo menos 7 classes de congruencia mod 12 com 5 elementos cada, pois se tivessemos apenas 6, entao 6*5 + (12-6)*4 = 54 55. Consideremos o menor elemento de cada uma das 7 classes com 5 elementos cada. Obviamente, estes menores elementos serao todos distintos, de forma que um deles, digamos n, serah = 7. Assim, os elementos da classe de n serao: n, n + 12*a, n + 12*(a+b), n + 12*(a+b+c), n + 12*(a+b+c+d), onde a, b, c, d sao inteiros positivos. Se a, b, c, d, e forem todos = 2, entao teremos: n + 12*(a+b+c+d) = 7 + 12*8 = 103 == contradicao, pois n + 12*(a+b+c+d) = 100. Logo, um dentre a, b, c, d eh necessariamente igual a 1 e tambem acabou. []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 =
Re: [obm-l] Novamente as gavetas
Gostei! Por alguma razao, eu nunca me lembro de particionar o conjunto-base
em pares. A minha solucao foi mais complicada, mas acho que consegui
melhorar o resultado para 53 elementos (ao inves de 55).
[]s,
Claudio.
on 11.05.04 14:49, Frederico Reis Marques de Brito at [EMAIL PROTECTED]
wrote:
Pois bem, então onde está o erro do seguinte raciocínio: separe os números
de 1 a 100 em conjuntos como os seguintes:
{1,13} , {2,14} ,{3,15}, ..., {12, 24}
{25,37} , {26, 38 }, ..., {36, 48}
{49, 61} , {50, 62} ,..., {60, 72}
{73, 84}, {74, 85} , ..., {84, 96}
e {97}, {98}, {99} , {100}. TEmos ao todo 4* 12 + 4 = 52 conjuntos
disjuntos cuja união dá o conjunto dos naturais de 1 a 100, inclusive. Dados
55 desses números, 2 terão que estar num mesmo subconjunto. Isso não pode
ocorrer nos últimos 4 subconjuntos , que são unitários. Logo,
há dois números entre 1 e 100 que estão num dos primeiros 48 subconjuntos,
que são todos da forma {a , a+12} = a diferença entre esses dois números é
precisamente 12!??!?
Um abraço,
FRed.
From: Claudio Buffara [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: [obm-l] Novamente as gavetas
Date: Tue, 11 May 2004 13:59:05 -0300
on 11.05.04 12:48, Frederico Reis Marques de Brito at
[EMAIL PROTECTED]
wrote:
Bom, dessa vez o resultado é verdadeiro.
Provar que dados 55 números inteiros entre 1 e 100, incluindo estes,
existem dois cuja diferença é exatamente 12.
Um abraço a todos,
Fred.
=
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
=
