Re: [obm-l] Gavetas
Vamos repartir A em 9 conjuntos:
A1={1,10,19,28,...,91,100}
A2={2,11,20,29,...,92}
A3={3,12,21,30,...,93}
...
A9=(9,18,27,36,...,99}
Como sao 55 numeros escolhidos e 9 conjuntos, pelo menos um conjunto tem
pelo menos [55/9]+1=7 numeros escolhidos.
(Se cada um tivesse 6 ou menos, teriamos um total menor ou igual a 6*9=54
escolhas.)
Mas cada conjunto tem 11 elementos (bom, ok, A1 tem 12). Se voce escolher 7
elementos dentre uma fila de 11 (ou 12), voce vai ter que escolher dois
adjacentes!
(Se esta parte final necessita clarificacao: no conjunto de 12 elementos
A1={1,10,,...,100}, considere os 6 pares {1,10},{19,28},...{90,99}.
Escolhendo 7 elementos, voce vai ter que escolher 2 num mesmo par.
Raciocinio analogo vale nos outros Ai que tem menos elementos, basta deixar
o ultimo par com um elemento soh).
Abraco, Ralph.
P.S.: Alias, acabo de ver que tem uma solucao mais direta. Basta olhar para
os conjuntos
(01,10),(02,11),(03,12),(04,13),(05,14),(06,15),(07,16),(08,17),(09,18)
(19,28),(20,29),(21,30),(22,31),(23,32),.(27,36)
(37,46),(38,47),..(45,54)
(55,64),.(63,72)
(73,82),.(81,90)
(91,100),(92),(93),(94),(95),(96),(97),(98),(99)
Ah, droga, coloquei parenteses ao inves de chaves, mas ok. Bom, conte: sao
9*5 nas 5 primeiras linhas, mais 9 conjuntos na ultima, ou seja, um total
de 54 conjuntos. Como sao 55 numeros escolhidos, tem que ter 2 em algum
mesmo conjunto, acabou.
2015-05-10 15:37 GMT-03:00 marcone augusto araújo borges
marconeborge...@hotmail.com:
Do conjunto A = {1,2,...100} escolhemos 55 números.Mostrar que entre os
números escolhidos
existem 2 cuja diferença é 9
--
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
Re: [obm-l] Gavetas
Além disso, além de provar que existe 2 inteiros que diferem 9 podemos
provar que existem 2 inteiros que diferem 10 ou 12 ou 13 mas
surpreendentemente, não existe necessariamente inteiros que diferem 11.
Em domingo, 10 de maio de 2015, Ralph Teixeira ralp...@gmail.com escreveu:
Vamos repartir A em 9 conjuntos:
A1={1,10,19,28,...,91,100}
A2={2,11,20,29,...,92}
A3={3,12,21,30,...,93}
...
A9=(9,18,27,36,...,99}
Como sao 55 numeros escolhidos e 9 conjuntos, pelo menos um conjunto tem
pelo menos [55/9]+1=7 numeros escolhidos.
(Se cada um tivesse 6 ou menos, teriamos um total menor ou igual a 6*9=54
escolhas.)
Mas cada conjunto tem 11 elementos (bom, ok, A1 tem 12). Se voce escolher
7 elementos dentre uma fila de 11 (ou 12), voce vai ter que escolher dois
adjacentes!
(Se esta parte final necessita clarificacao: no conjunto de 12 elementos
A1={1,10,,...,100}, considere os 6 pares {1,10},{19,28},...{90,99}.
Escolhendo 7 elementos, voce vai ter que escolher 2 num mesmo par.
Raciocinio analogo vale nos outros Ai que tem menos elementos, basta deixar
o ultimo par com um elemento soh).
Abraco, Ralph.
P.S.: Alias, acabo de ver que tem uma solucao mais direta. Basta olhar
para os conjuntos
(01,10),(02,11),(03,12),(04,13),(05,14),(06,15),(07,16),(08,17),(09,18)
(19,28),(20,29),(21,30),(22,31),(23,32),.(27,36)
(37,46),(38,47),..(45,54)
(55,64),.(63,72)
(73,82),.(81,90)
(91,100),(92),(93),(94),(95),(96),(97),(98),(99)
Ah, droga, coloquei parenteses ao inves de chaves, mas ok. Bom, conte: sao
9*5 nas 5 primeiras linhas, mais 9 conjuntos na ultima, ou seja, um total
de 54 conjuntos. Como sao 55 numeros escolhidos, tem que ter 2 em algum
mesmo conjunto, acabou.
2015-05-10 15:37 GMT-03:00 marcone augusto araújo borges
marconeborge...@hotmail.com
javascript:_e(%7B%7D,'cvml','marconeborge...@hotmail.com');:
Do conjunto A = {1,2,...100} escolhemos 55 números.Mostrar que entre os
números escolhidos
existem 2 cuja diferença é 9
--
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
Re: [obm-l] Gavetas
Bom, vamos tentar montar primeiro o maior conjunto em que nenhum par de
elementos possui diferenca 9.
Para isso vamo ir pegando os elementos em ordem, comecando do 1. Vale
observar que se eu pego um numero x, eu nao posso pegar o numero x+9 (pela
ordem que estou olhando para os elementos, eu so preciso me preocupar com
os elementos a direta), vamos dizer que eu risquei o numero x+9 da lista.
Assim comecando no numero 1 eu escolho ele. Nunca vale a pena deixar de
escolher um numero que nao esta riscado, pois ele so risca um numero a
direita dele, logo deixar de escolher so me possiblitaria de escolher o
numero x+9 num momento a frente, o que nao eh bom, ja que eu posso escolher
no momento atual.
Logo eu escolho os numeros 1,2,3, ... , 9 e assim os numeros 10 ate 18 ja
estao riscados, logo nao escolho. Depois escolho os numeros de 19 ate 27 e
os numeros de 28 a 36 ja estao riscados continuando meu conjunto de
escolha fica:
X = {1,2,...,9} U {19,...,27} U {37,...,45} U {55,...,63} U {73,...,81} U
{91,...,99}
|X|=54
Nenhum par de numeros desse conjunto X possui diferenca 9. Colocando o 100
nesse conjunto, temos |X| = 55 e o unico par com diferenca 9 é {91,100} :)
Acho que tem algum problema no enunciado, talvez A = {1,2,...,99}, ai
qualquer escolha de numero riscado para se colocar no conjunto, afetaria os
numeros x-9 e x+9.
Atenciosamente,
Pedro.
Em 10 de maio de 2015 15:37, marcone augusto araújo borges
marconeborge...@hotmail.com escreveu:
Do conjunto A = {1,2,...100} escolhemos 55 números.Mostrar que entre os
números escolhidos
existem 2 cuja diferença é 9
--
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
Re: [obm-l] gavetas
Obrigado pela ajuda.Johann Peter Gustav Lejeune Dirichlet [EMAIL PROTECTED] wrote:
Traduza e divirta-se!
Problem B3
An international society has its members from six different countries. The list of members has 1978 names, numbered 1, 2, ... , 1978. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice the number of a member from his own country.
Solution
The trick is to use differences.
At least 6.329 = 1974, so at least 330 members come from the same country, call it C1. Let their numbers be a1 a2 ... a330. Now take the 329 differences a2 - a1, a3 - a1, ... , a330 - a1. If any of them are in C1, then we are home, so suppose they are all in the other five countries.
At least 66 must come from the same country, call it C2. Write the 66 as b1 b2 ... b66. Now form the 65 differences b2 - b1, b3 - b1, ... , b66 - b1. If any of them are in C2, then we are home. But each difference equals the difference of two of the original ais, so if it is in C1 we are also home.
So suppose they are all in the other four countries. At least 17 must come from the same country, call it C3. Write the 17 as c1 c2 ... c17. Now form the 16 differences c2 - c1, c3 - c1, ... , c17 - c1. If any of them are in C3, we are home. Each difference equals the difference of two bis, so if any of them are in C2 we are home. [For example, consider ci - c1. Suppose ci = bn - b1 and c1 = bm - b1, then ci - c1 = bn - bm, as claimed.]. Each difference also equals the difference of two ais, so if any of them are in C1, we are also home. [For example, consider ci - c1, as before. Suppose bn = aj - a1, bm = ak - a1, then
ci - c1 = bn - bm = aj - ak, as claimed.]
So suppose they are all in the other three countries. At least 6 must come from the same country, call it C4. We look at the 5 differences and conclude in the same way that at least 3 must come from C5. Now the 2 differences must both be in C6 and their difference must be in one of the C1, ... , C6 giving us the required sum.
Jesualdo [EMAIL PROTECTED] wrote:
Saudações,
Eu sou novo no grupo e gostaria de saber se alguém pode me ajudar a resolver o seguinte problema:
Prove que se o conjunto {1, 2, ... , 1978} é partido em 6 subconjuntos, em algum desses subconjuntos existe um elemento que é igual à soma de dois elementos, não necessariamente distintos, do mesmo subconjunto.
Não consegui resolver e já procurei em alguns livros e também na internet mas não encontrei nada.
Este problema se encontra no livro Análise Combinatória e probabiblidade da Coleção do professor de Matemática.
Atenciosamente
Jesualdo Gomes
__Do You Yahoo!?Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
TRANSIRE SVVM PECTVS MVNDOQVE POTIRI CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE Fields Medal(John Charles Fields)
N.F.C. (Ne Fronti Crede)
__Do You Yahoo!?Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com ___Jesualdo Gomes das ChagasUniversidade Federal de Campina Grande Departamento de Matemática e Estatística
Yahoo! Acesso Grátis - navegue de graça com conexão de qualidade!
Re: [obm-l] gavetas
eu já resolvi esse faz um tempo...
vc tem que quebrar o conjunto a partir do PCP obtendo um conjunto com k
elementos x_1 x_2 ... x_k, com k = 330
aí vc olha pra x_2 - x_1, ..., x_k - x_1 que são k-1 = 329 valores
diferentes que estão entre 1 e 1978 e não devem
estar em alguma das outras 5 partições, então repita o PCP para esse
conjunto de tamanho k-1 e continue o processo,
você verá que a última partição não poderá ter 2 elementos do conjunto e
aí você chega numa contradição.
[ ]'s
Saudações,
Eu sou novo no grupo e gostaria de saber se alguém pode me ajudar a
resolver o seguinte problema:
*Prove que se o conjunto {1, 2, ... , 1978} é partido em 6
subconjuntos, em algum desses subconjuntos existe um elemento que é
igual à soma de dois elementos, não necessariamente distintos, do
mesmo subconjunto.*
Não consegui resolver e já procurei em alguns livros e também na
internet mas não encontrei nada.
Este problema se encontra no livro /Análise Combinatória e
probabiblidade/ da /Coleção do professor de Matemática/.
=
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] gavetas
Traduza e divirta-se!
Problem B3
An international society has its members from six different countries. The list of members has 1978 names, numbered 1, 2, ... , 1978. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice the number of a member from his own country.
Solution
The trick is to use differences.
At least 6.329 = 1974, so at least 330 members come from the same country, call it C1. Let their numbers be a1 a2 ... a330. Now take the 329 differences a2 - a1, a3 - a1, ... , a330 - a1. If any of them are in C1, then we are home, so suppose they are all in the other five countries.
At least 66 must come from the same country, call it C2. Write the 66 as b1 b2 ... b66. Now form the 65 differences b2 - b1, b3 - b1, ... , b66 - b1. If any of them are in C2, then we are home. But each difference equals the difference of two of the original ais, so if it is in C1 we are also home.
So suppose they are all in the other four countries. At least 17 must come from the same country, call it C3. Write the 17 as c1 c2 ... c17. Now form the 16 differences c2 - c1, c3 - c1, ... , c17 - c1. If any of them are in C3, we are home. Each difference equals the difference of two bis, so if any of them are in C2 we are home. [For example, consider ci - c1. Suppose ci = bn - b1 and c1 = bm - b1, then ci - c1 = bn - bm, as claimed.]. Each difference also equals the difference of two ais, so if any of them are in C1, we are also home. [For example, consider ci - c1, as before. Suppose bn = aj - a1, bm = ak - a1, then
ci - c1 = bn - bm = aj - ak, as claimed.]
So suppose they are all in the other three countries. At least 6 must come from the same country, call it C4. We look at the 5 differences and conclude in the same way that at least 3 must come from C5. Now the 2 differences must both be in C6 and their difference must be in one of the C1, ... , C6 giving us the required sum.
Jesualdo [EMAIL PROTECTED] wrote:
Saudações,
Eu sou novo no grupo e gostaria de saber se alguém pode me ajudar a resolver o seguinte problema:
Prove que se o conjunto {1, 2, ... , 1978} é partido em 6 subconjuntos, em algum desses subconjuntos existe um elemento que é igual à soma de dois elementos, não necessariamente distintos, do mesmo subconjunto.
Não consegui resolver e já procurei em alguns livros e também na internet mas não encontrei nada.
Este problema se encontra no livro Análise Combinatória e probabiblidade da Coleção do professor de Matemática.
Atenciosamente
Jesualdo Gomes
__Do You Yahoo!?Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
TRANSIRE SVVM PECTVS MVNDOQVE POTIRI CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE Fields Medal(John Charles Fields)
N.F.C. (Ne Fronti Crede)__Do You Yahoo!?Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
Re: [obm-l] gavetas
Este exercicio esta em uma das Eureka!s, e e da IMO de 1978. Veja uma soluçao em www.kalva.demon.co.uk/imo.Jesualdo [EMAIL PROTECTED] wrote:
Saudações,
Eu sou novo no grupo e gostaria de saber se alguém pode me ajudar a resolver o seguinte problema:
Prove que se o conjunto {1, 2, ... , 1978} é partido em 6 subconjuntos, em algum desses subconjuntos existe um elemento que é igual à soma de dois elementos, não necessariamente distintos, do mesmo subconjunto.
Não consegui resolver e já procurei em alguns livros e também na internet mas não encontrei nada.
Este problema se encontra no livro Análise Combinatória e probabiblidade da Coleção do professor de Matemática.
Atenciosamente
Jesualdo Gomes
__Do You Yahoo!?Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
TRANSIRE SVVM PECTVS MVNDOQVE POTIRI CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE Fields Medal(John Charles Fields)
N.F.C. (Ne Fronti Crede)
Yahoo! Acesso Grátis - navegue de graça com conexão de qualidade!
