Questão 22. Escrevemos todos os números de 1 a 30 inclusive de modo que na lista final não haja nenhum número que seja o dobro do outro da mesma lista. Qual o número máximo de inteiros que pode ter a lista final?
a) 15
b) 18
c) 19
d) 20

Passo 1

O enunciado pede: escolher o maior número possível de inteiros distintos da lista \{1,2,\dots,30\} de modo que, na lista final, não exista nenhum par em que um seja o dobro do outro. Queremos achar esse número máximo de inteiros.
Informações relevantes dadas:
  • Temos todos os inteiros de 1 a 30 disponíveis.
  • Não é permitido que na lista final tenham dois números a e b tais que a=2b (ou b=2a).
  • Precisamos encontrar a quantidade máxima de números que podemos colocar na lista final, respeitando essa proibição.

Passo 2

Organizar os números por “cadeias de dobramento”. Para qualquer inteiro n podemos escrever n = 2^{t} m com m ímpar (essa escrita é única: m é o “núcleo ímpar” de n). Todos os números que têm o mesmo núcleo ímpar m formam uma cadeia
m,\;2m,\;4m,\;8m,\;\dots
até que 2^{t}m>30. Vou usar essa partição porque a relação “é o dobro de” só ocorre entre elementos consecutivos dessa cadeia: 2^{k}m é o dobro de 2^{k-1}m. Portanto, as cadeias com núcleos ímpares distintos são independentes entre si (nenhum número de uma cadeia pode ser dobro de um número de outra cadeia). Logo o problema separa-se em resolver cada cadeia e somar as escolhas ótimas.

Passo 3

Justifico que cadeias com núcleos ímpares diferentes não têm relações de dobramento entre si. Se 2^{a}m = 2^{b}n com m e n ímpares e m\neq n, então, dividindo por 2^{\min(a,b)}, obteríamos igualdade entre dois números ímpares distintos, o que é impossível. Assim, dobra só ocorre dentro da mesma cadeia m,2m,4m,\dots.

Passo 4

Redução para problema clássico em cada cadeia: numa cadeia linear de comprimento \ell (vértices conectados em linha, arestas entre números que são dobra um do outro) queremos selecionar o máximo de vértices sem escolher dois adjacentes. Esse é o problema do conjunto independente máximo em um caminho (path). Fato útil e simples de provar:
  • O máximo que dá para escolher numa cadeia de \ell elementos é \left\lceil \dfrac{\ell}{2} \right\rceil.
    Prova rápida e intuitiva: agrupe a cadeia em pares consecutivos (1,2),(3,4),\dots; de cada par podemos escolher no máximo um elemento, então obtemos no máximo \left\lceil \dfrac{\ell}{2} \right\rceil. Esse valor é atingível escolhendo os elementos de posições 1,3,5,\dots (ou 2,4,6,\dots dependendo do \ell), logo é ótimo.

Passo 5

Agora vamos listar as cadeias geradas pelos núcleos ímpares m=1,3,5,\dots,29 e determinar seus comprimentos \ell.
  • Para m=1: a cadeia é 1,2,4,8,16 (pois 32>30). Logo \ell=5.
  • Para m=3: a cadeia é 3,6,12,24. Logo \ell=4.
  • Para m=5: 5,10,20. Logo \ell=3.
  • Para m=7: 7,14,28. Logo \ell=3.
  • Para m=9: 9,18. Logo \ell=2.
  • Para m=11: 11,22. Logo \ell=2.
  • Para m=13: 13,26. Logo \ell=2.
  • Para m=15: 15,30. Logo \ell=2.
  • Para m=17,19,21,23,25,27,29: cada um só aparece sozinho (pois 2m>30), logo \ell=1 para cada um desses sete m.
Resumo dos comprimentos:
\ell para m=1 é 5; para m=3 é 4; para m=5,7 é 3 cada; para m=9,11,13,15 é 2 cada; para m=17,19,21,23,25,27,29 é 1 cada.

Passo 6

Aplicando a fórmula \left\lceil \dfrac{\ell}{2} \right\rceil a cada cadeia e somando:
  • Para \ell=5 (caso m=1): \left\lceil \dfrac{5}{2} \right\rceil = 3.
  • Para \ell=4 (caso m=3): \left\lceil \dfrac{4}{2} \right\rceil = 2.
  • Para cada \ell=3 (casos m=5,7): \left\lceil \dfrac{3}{2} \right\rceil = 2 (duas cadeias assim).
  • Para cada \ell=2 (casos m=9,11,13,15): \left\lceil \dfrac{2}{2} \right\rceil = 1 (quatro cadeias assim).
  • Para cada \ell=1 (sete casos m\ge 17): \left\lceil \dfrac{1}{2} \right\rceil = 1.
Somando todos os máximos:
3 \;+\; 2 \;+\; 2 \;+\; 2 \;+\; (1+1+1+1) \;+\; (1+1+1+1+1+1+1).
Calcule:
3+2+2+2 = 9,
1+1+1+1 = 4,
\text{sete }1\text{s} = 7.
Assim 9+4+7 = 20. Logo o máximo total possível é 20.

Passo 7

Mostro uma construção explícita que atinge 20 (para ver que o valor é realizável). Escolhendo, por cadeia, as posições ímpares na sequência m,2m,4m,\dots quando apropriado, obtemos, por exemplo, a lista:
1,\;4,\;16,\;3,\;12,\;5,\;20,\;7,\;28,\;9,\;11,\;13,\;15,\;17,\;19,\;21,\;23,\;25,\;27,\;29.
Verifique rapidamente: não há nenhum par nessa lista em que um seja o dobro do outro (por construção escolhemos elementos não adjacentes nas cadeias), e ela tem exatamente 20 elementos. Portanto 20 é atingível.

Resposta

20

Exercícios relacionados