(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 .

Passo 1

O enunciado diz que há uma urna com fichas numeradas de 1 a 20 e pergunta o menor número n de retiradas que garante, independentemente de quais fichas saiam, que entre as n fichas exista um trio com números consecutivos. O conteúdo aqui é um problema de princípios extremais: vamos achar o maior subconjunto de \{1,\dots,20\} 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 A\subset\{1,\dots,20\} um conjunto que não tem três elementos consecutivos. Representamos A 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 \texttt{111}. Queremos maximizar o número de uns nessa sequência.

Passo 3

Um arranjo eficiente é repetir o bloco \texttt{110} quantas vezes couber e, nos dois últimos lugares, também usar “11”. Em termos de índices, escolher todos os i\equiv1,2\pmod3. Isso dá
6\text{ blocos }(110)\;\to\;6\cdot2=12\text{ uns em 18 posições},çõ
mais as posições 19 e 20 também iguais a 1, totalizando 12+2=14 uns.
Para ver que não dá para chegar a 15, note que se houvessem 15 uns, haveria apenas 5 zeros, mas para evitar três uns em sequência precisamos pelo menos \lfloor(15-1)/2\rfloor=7 zeros. Conclusão: o maior número de fichas que podemos retirar sem garantir um trio consecutivo é 14.

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,
n=14+1=15.

Resposta

Exercícios de Livros Relacionados