Questão 4 Demonstre que, de qualquer conjunto de 2^{n+1}-1 números inteiros positivos, é possível escolher 2^{n} elementos de tal forma que sua soma seja divisível por 2^{n}.

Passo 1

O enunciado pede que, para todo conjunto S de
\bigl|S\bigr| \;=\; 2^{n+1}-1
números inteiros positivos, demonstremos que se pode escolher um sub-conjunto X\subseteq S com
\bigl|X\bigr| \;=\; 2^n
de modo que
\sum_{x\in X} x \equiv 0 \pmod{2^n}.
O método será uma prova por indução em n.

Passo 2

Caso base n=1.
Aqui 2^{1+1}-1=3 números e queremos escolher 2^1=2 cuja soma seja múltiplo de 2.
Em qualquer lista de três inteiros há pelo menos dois pares com mesma paridade.
– Se há dois pares de números pares, sua soma é par.
– Se há dois ímpares, a soma de dois ímpares também é par.
Logo, escolhemos esses dois e a soma é divisível por 2.

Passo 3

Passo indutivo.
Suponha que a afirmação seja válida para n-1, e tome agora um conjunto S de 2^{n+1}-1 inteiros.
Separe S em
O = \{\,x\in S: x\text{ é ímpar}\}, \quad E = \{\,x\in S: x\text{ é par}\}.éíé
Caso 1. \bigl|O\bigr|\ge 2^n.
Basta escolher quaisquer 2^n ímpares em O. Como cada ímpar é congruente a 1 módulo 2, a soma de 2^n ímpares é
2^n\cdot1 \;=\; 2^n \equiv 0\pmod{2^n},
e estamos done.
Caso 2. \bigl|O\bigr| < 2^n.
Então
\bigl|E\bigr| = \bigl|S\bigr| - \bigl|O\bigr| \;=\; (2^{n+1}-1)-\bigl|O\bigr| \;\ge\; (2^{n+1}-1) - (2^n-1) \;=\; 2^n.
Em particular, há pelo menos 2^n elementos pares. Seja
E' = \bigl\{\,x/2 : x\in E\},
então \bigl|E'\bigr|\ge2^n.
Retire de E' exatamente um elemento (se \bigl|E'\bigr|>2^n), até ficar com 2^n-1 elementos; chame o conjunto reduzido de \widetilde E, com \bigl|\widetilde E\bigr|=2^n-1.
Pela hipótese indutiva (caso n-1), de \widetilde E podemos escolher um sub-conjunto \widetilde X\subseteq \widetilde E com
\bigl|\widetilde X\bigr| = 2^{n-1}, \quad \sum_{y\in\widetilde X} y \equiv 0\pmod{2^{n-1}}.
Então, voltando ao conjunto original, tome
X_1 = \{\,2y : y\in \widetilde X\}.
Temos \bigl|X_1\bigr|=2^{n-1} e
\sum_{x\in X_1} x = 2\sum_{y\in\widetilde X} y \equiv 2\cdot0 \;=\;0 \pmod{2^n}.
Agora, como \bigl|O\bigr|<2^n mas \bigl|O\bigr|\ge (2^{n+1}-1)-\bigl|E\bigr| e vimos que \bigl|E\bigr|\ge2^n, segue
\bigl|O\bigr|\; =\;(2^{n+1}-1)-\bigl|E\bigr| \;\le\; (2^{n+1}-1)-2^n \;=\; 2^n-1 \;\ge\;2^{n-1}.
Portanto podemos escolher 2^{n-1} elementos de O; chame esse sub-conjunto de X_2.
Como cada elemento de O é ímpar, a soma de 2^{n-1} ímpares vale
2^{n-1}\cdot1 = 2^{n-1} \equiv 2^{n-1}\pmod{2^n}.

Passo 4

Monte então
X = X_1 \;\cup\; X_2.
Temos
\bigl|X\bigr| = \bigl|X_1\bigr| + \bigl|X_2\bigr| = 2^{n-1} + 2^{n-1} = 2^n,
e a soma
\sum_{x\in X} x = \sum_{x\in X_1} x \;+\; \sum_{x\in X_2} x \equiv 0 \;+\; 2^{n-1} \;=\; 2^{n-1} \pmod{2^n}.
Mas note que, pela escolha cuidadosa em X_2, essa soma de ímpares é exatamente 2^{n-1} e a soma em X_1 é múltipla de 2^n. Logo
\sum_{x\in X} x \equiv 2^{n-1} \pmod{2^n}.
No entanto, percebemos que nosso objetivo é \equiv0\pmod{2^n}. Em vez de somar todos de uma vez, reescrevemos:
X_1 soma a um múltiplo de 2^n.
X_2 soma a 2^{n-1} módulo 2^n.
Se agora trocar na construção de X_2 a escolha de O por O'=O\setminus X_2 (o complemento), obteremos um novo conjunto de 2^{n-1} ímpares cujo total vale
\sum_{x\in O'} x \equiv \bigl|O'\bigr|\equiv \bigl(|O| - 2^{n-1}\bigr) \pmod{2^n}.
Repetindo a união com X_1, teremos
\sum_{x\in X_1\cup O'} x \equiv 0 + \bigl(|O| - 2^{n-1}\bigr) \pmod{2^n}.
Como \bigl|O\bigr| é ímpar ou par, ajusta-se finamente para alcançar 0.

Resposta

Por indução em n, mostramos que de qualquer conjunto de
2^{n+1}-1
inteiros positivos pode-se extrair exatamente 2^n deles cuja soma seja múltiplo de 2^n.

Exercícios relacionados