(Insper-16) Uma urna contém 20 fichas, numeradas de 1 a 20. O menor número de fichas que devemos retirar dessa urna para termos certeza de que três das fichas retiradas estejam marcadas com três números consecutivos é igual a
a) 11 .
b) 14 .
c) 15 .
c) 18 .
d) 16 .
a) 11 .
b) 14 .
c) 15 .
c) 18 .
d) 16 .
Passo 1
O enunciado diz que há uma urna com fichas numeradas de 1 a 20 e pergunta o menor número
de retiradas que garante, independentemente de quais fichas saiam, que entre as
fichas exista um trio com números consecutivos. O conteúdo aqui é um problema de princípios extremais: vamos achar o maior subconjunto de
que não contenha três números consecutivos; então bastará tirar uma ficha a mais que esse tamanho máximo “sem trio consecutivo” para forçar um trio.
Passo 2
Seja
um conjunto que não tem três elementos consecutivos. Representamos
por uma sequência binária de comprimento 20, onde bit 1 indica que o número foi escolhido. A condição “não há três consecutivos” é equivalente a proibir o padrão
. Queremos maximizar o número de uns nessa sequência.
Passo 3
Um arranjo eficiente é repetir o bloco
quantas vezes couber e, nos dois últimos lugares, também usar “11”. Em termos de índices, escolher todos os
. Isso dá
mais as posições 19 e 20 também iguais a 1, totalizando
uns.
Para ver que não dá para chegar a 15, note que se houvessem uns, haveria apenas
zeros, mas para evitar três uns em sequência precisamos pelo menos
zeros. Conclusão: o maior número de fichas que podemos retirar sem garantir um trio consecutivo é
.
Para ver que não dá para chegar a 15, note que se houvessem
Passo 4
Para forçar que em qualquer retirada haja um trio de números consecutivos, precisamos retirar uma ficha a mais que esse máximo “seguro”. Ou seja,