Oi, pessoal: Como fui eu quem deu a ideia de resolver, aqui na lista, problemas de olimpiadas ainda sem solucao no site do John Scholes, aqui vai a primeira contribuicao pro projeto. Eu adoraria ver mais gente participando.
Olimpiada da India - 1995: Problema 3) Mostre que o conjunto {1, 2, 3, ..., 63} possui mais subconjuntos de 3 elementos com soma superior a 95 do que subconjuntos de 3 elementos com soma inferior a 95. O conjunto de todos os subconjuntos de 3 elementos {1, 2, ..., 63} tem Binom(63,3) elementos e pode ser particionado da seguinte forma: 31 subconjuntos da forma {x,32,64-x} com 1 <= x <= 31 e (Binom(63,3) - 31)/2 = 19840 pares de subconjuntos da forma: { {a,b,c} , {64-c,64-b,64-a} } com 1 <= a < b < c <= 63 e b <> 32. Cada um dos 31 subconjuntos da forma {x,32,64-x} tem soma igual a 96 > 95. No caso dos pares de subconjuntos, se {a,b,c} tem soma inferior a 95, entao {64-c,64-b,64-a} tem soma igual a 192 - (a+b+c) > 192 - 95 = 97 > 95. De forma analoga, vemos que se {64-c,64-b,64-a} tem soma inferior a 95, entao {a,b,c} tem soma superior a 95. Assim, para cada subconjunto com soma inferior a 95, existe (pelo menos) um subconjunto com soma superior a 95 distinto de todos os demais conjuntos com soma superior a 95 e, de fato, levando em conta os 31 subconjuntos da forma {x,32,64-x}, concluimos que existem mais subconjuntos com soma superior a 95 do que subconjuntos com soma inferior a 95. []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 =========================================================================