Não creio que o objetivo do exercício fosse dar um exemplo de um tal conjunto mas sim mostrar que para QUALQUER subconjunto S de {1,2,3,4,5,6,7,8,9,10,11,12} com 7 elementos existe pelo menos dois subconjuntos de S cujas somas dos elementos coincidem.
Tal como outros problemas aqui postos (muitos deles por esta altura) trata-se de um exercício que se resolve fazendo um uso engenhoso do
princípio do pombal: se há mais pombos que gaiolas então alguma gaiola terá de ter mais de um pombo.
Neste caso, e como não é dito se os dois subconjuntos de S têm de ser disjuntos ou não ou quantos elementos têm de ter, vou considerar o nº de somas possíveis de subconjuntos de {1,2,3,4,5,6,7,8,9,10,11,12} (as nossas gaiolas). Estas variam entre 0 (para o subconjunto vazio) e 1+2+3+4+5+...+12=78 (para o subconjunto total*). Temos portanto 79 "gaiolas" no total. Mas um conjunto S com 7 elementos possui 2^7=128 subconjuntos (os nossos pombos) que excede as nossas 79 gaiolas. Logo haverá sempre subconjuntos distintos com a mesma soma.
*- Na verdade as somas para subconjuntos de S só vão até 12+11+10+9+8+7+6=57 (corresponde ao conjunto de 7 elementos com maior soma: {6,7,8,9,10,11,12}).
PS- Também é possível (e mais interessante) juntar as condições extra de que os subconjuntos de S tenham que ser disjuntos e com dois elementos cada. Isto é, mostrar que se \(S\subset \{1,2,\dots ,12\}\) e \(|S|=7\) então existem \(\{a,b\},\{c,d\}\subset S\) tais que \(a+b=c+d\).
Entrar
Registar
FAQ
Pesquisar
