[obm-l] Problemas de Olimpiadas

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

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
=========================================================================