Questão 9

Para todo subconjunto $S\subset\{n\in\mathbb{N}: 1\le n\le 60\}$ com $9$ elementos, considere as seguintes afirmações:

I. Existe um subconjunto de $S$ com $4$ elementos cuja soma é menor ou igual a $220$.

II. Existe um subconjunto $A$ de $S$, com $A\neq\emptyset$ e $A\neq S$, tal que a soma dos elementos de $A$ é igual à soma dos elementos de $S\setminus A$.

III. Existem subconjuntos $A$ e $B$ de $S$, distintos e não vazios, tais que a soma dos elementos de $A$ é igual à soma dos elementos de $B$.

É (São) VERDADEIRA(S):

O enunciado começa com “para todo subconjunto $S$”: cada afirmação só é verdadeira se valer para qualquer escolha de nove números entre $1$ e $60$. Para derrubar uma delas basta um contraexemplo; para confirmar, é preciso um argumento geral. As ferramentas são o caso extremo e o princípio da casa dos pombos.

Analisando a afirmação I: escrevendo os elementos de $S$ em ordem crescente,
$$a_1<a_2<\dots<a_9$$
o subconjunto natural a testar é o dos quatro menores, pois é ele que minimiza a soma. Precisamos majorar $a_1+a_2+a_3+a_4$ no pior caso possível. Como os nove elementos são distintos e não passam de $60$, temos $a_9\le 60$, $a_8\le 59$ e, em geral,
$$a_k\le 60-(9-k)=51+k$$
Em particular $a_1\le 52$, $a_2\le 53$, $a_3\le 54$ e $a_4\le 55$, de modo que
$$a_1+a_2+a_3+a_4\le 52+53+54+55=214$$
O valor $214$ é atingido no caso extremo $S=\{52,53,\dots,60\}$, e $214\le 220$. Logo a soma dos quatro menores sempre cumpre a exigência, e a afirmação I é verdadeira.

Analisando a afirmação II: exigir que $A$ e $S\setminus A$ tenham somas iguais é exigir que a soma total de $S$ seja o dobro de um inteiro, ou seja, que ela seja par. Basta então tomar um conjunto de soma ímpar para destruir a afirmação. Com
$$S=\{1,2,3,4,5,6,7,8,9\}$$
a soma total vale
$$1+2+\dots+9=\frac{9\cdot 10}{2}=45$$
que é ímpar. Nenhuma partição em duas partes de somas iguais é possível, pois isso daria soma total $2k$, par. A afirmação II é falsa.

Analisando a afirmação III: agora $A$ e $B$ não precisam ser complementares, nem sequer disjuntos — só precisam ser diferentes entre si. Isso muda completamente o jogo e abre espaço para a contagem. Contemos duas coisas.

Os pombos são os subconjuntos não vazios de $S$. Como $S$ tem $9$ elementos,
$$2^{9}-1=511$$
subconjuntos não vazios.

As casas são os valores possíveis da soma dos elementos. A menor soma possível é $1$ (o menor elemento sozinho, no melhor dos casos), e a maior soma possível ocorre quando somamos todos os nove elementos, sendo limitada pelo caso extremo $S=\{52,53,\dots,60\}$:
$$52+53+\dots+60=\frac{(52+60)\cdot 9}{2}=\frac{112\cdot 9}{2}=504$$
Portanto toda soma é um inteiro entre $1$ e $504$: há, no máximo, $504$ casas.

Como $511>504$, o princípio da casa dos pombos garante que dois subconjuntos não vazios distintos têm a mesma soma. A afirmação III é verdadeira.

São verdadeiras apenas as afirmações I e III.