Qual o menor número de elementos que é preciso selecionar do conjunto {1,...,n} para garantir que haja dois números consecutivos?

Resposta

Resposta: \(\lceil n/2\rceil+1\)

Raciocínio: no pior caso escolhemos o maior conjunto sem elementos consecutivos, que tem tamanho \(\lceil n/2\rceil\) (escolhendo números alternados). Ao adicionar mais um elemento, isto é \(\lceil n/2\rceil+1\), obrigatoriamente surgirá um par de números consecutivos.

Exemplo:
Para \(n=20\): \(\lceil 20/2\rceil+1 = 10+1 = 11\).
Um conjunto sem consecutivos com 10 elementos é {2,4,6,8,10,12,14,16,18,20}.
Ao selecionar o 11º número, qualquer escolha criará pelo menos um par de números consecutivos.