Traduza e divirta-se!Problem B3An 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 <jgchagas@yahoo.com.br> 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.AtenciosamenteJesualdo 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