ITA 2024 — 1ª Fase — Questão 40 — Princípio das Gavetas
Considere o conjunto
\[
A=\{1,2,4,8,16,32,64,128,256\}.
\]
Qual o menor \(n \in \mathbb{N}\) tal que todo subconjunto de \(A\) com \(n\) elementos contenha pelo menos um par cujo produto seja \(256\)?
a) \(n=5\). b) \(n=6\). c) \(n=7\). d) \(n=8\). e) \(n=9\).
a) \(n=5\). b) \(n=6\). c) \(n=7\). d) \(n=8\). e) \(n=9\).
👀 Solução Passo a Passo
Observe que os pares de elementos distintos de \(A\) cujo produto é \(256\) são:
\[
(1,256),\ (2,128),\ (4,64),\ (8,32).
\]
(O produto \(16\cdot16=256\) exigiria dois \(16\), mas há apenas um \(16\) em \(A\).)
1) Contraexemplo para \(n=5\).
É possível escolher um subconjunto com 5 elementos sem formar nenhum desses pares, por exemplo \[ \{1,2,4,8,16\}\quad\text{(um de cada par + o 16)}. \] Logo, \(n=5\) não garante a presença do par.
2) Garantia para \(n=6\).
O conjunto pode ser organizado em 5 “gavetas” independentes: \[ \{1,256\},\ \{2,128\},\ \{4,64\},\ \{8,32\},\ \{16\}. \] Escolhendo 6 elementos (pelo Princípio das Gavetas), ou escolhemos os 5 elementos “seguros” (um de cada par e o \(16\)) e o 6º forçará pegar o segundo elemento de algum par, ou já formaremos um par antes. Portanto, com \(n=6\) sempre haverá pelo menos um par cujo produto seja \(256\).
1) Contraexemplo para \(n=5\).
É possível escolher um subconjunto com 5 elementos sem formar nenhum desses pares, por exemplo \[ \{1,2,4,8,16\}\quad\text{(um de cada par + o 16)}. \] Logo, \(n=5\) não garante a presença do par.
2) Garantia para \(n=6\).
O conjunto pode ser organizado em 5 “gavetas” independentes: \[ \{1,256\},\ \{2,128\},\ \{4,64\},\ \{8,32\},\ \{16\}. \] Escolhendo 6 elementos (pelo Princípio das Gavetas), ou escolhemos os 5 elementos “seguros” (um de cada par e o \(16\)) e o 6º forçará pegar o segundo elemento de algum par, ou já formaremos um par antes. Portanto, com \(n=6\) sempre haverá pelo menos um par cujo produto seja \(256\).
Resposta: b) \(n=6\)
