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
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
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
a disponíveis. - Não é permitido que na lista final tenham dois números
e tais que (ou ). - 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
podemos escrever
com
ímpar (essa escrita é única:
é o “núcleo ímpar” de
). Todos os números que têm o mesmo núcleo ímpar
formam uma cadeia
até que
. Vou usar essa partição porque a relação “é o dobro de” só ocorre entre elementos consecutivos dessa cadeia:
é o dobro de
. 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
com
e
ímpares e
, então, dividindo por
, obteríamos igualdade entre dois números ímpares distintos, o que é impossível. Assim, dobra só ocorre dentro da mesma cadeia
.
Passo 4
Redução para problema clássico em cada cadeia: numa cadeia linear de comprimento
(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
elementos é .
Prova rápida e intuitiva: agrupe a cadeia em pares consecutivos; de cada par podemos escolher no máximo um elemento, então obtemos no máximo . Esse valor é atingível escolhendo os elementos de posições (ou dependendo do ), logo é ótimo.
Passo 5
Agora vamos listar as cadeias geradas pelos núcleos ímpares
e determinar seus comprimentos
.
- Para
: a cadeia é (pois ). Logo . - Para
: a cadeia é . Logo . - Para
: . Logo . - Para
: . Logo . - Para
: . Logo . - Para
: . Logo . - Para
: . Logo . - Para
: . Logo . - Para
: cada um só aparece sozinho (pois ), logo para cada um desses sete .
Resumo dos comprimentos:
para
é
; para
é
; para
é
cada; para
é
cada; para
é
cada.
Passo 6
Aplicando a fórmula
a cada cadeia e somando:
- Para
(caso ): . - Para
(caso ): . - Para cada
(casos ): (duas cadeias assim). - Para cada
(casos ): (quatro cadeias assim). - Para cada
(sete casos ): .
Somando todos os máximos:
Calcule:
Assim
. Logo o máximo total possível é
.
Passo 7
Mostro uma construção explícita que atinge
(para ver que o valor é realizável). Escolhendo, por cadeia, as posições ímpares na sequência
quando apropriado, obtemos, por exemplo, a lista:
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
elementos. Portanto
é atingível.