De quantas formas podemos escolher um subconjunto de
elementos do conjunto
de forma que o módulo da diferença entre quaisquer dois elementos desse subconjunto seja sempre maior ou igual a 3 ?
Passo 1
O problema pede contar de quantas maneiras podemos escolher um subconjunto de
elementos do conjunto
de forma que, para quaisquer dois elementos distintos
desse subconjunto, valha
O tema aqui é contagem de combinações com espaçamento mínimo entre elementos. Vamos ordenar os elementos escolhidos e usar uma transformação que reduz o problema a escolher sem restrição em um conjunto menor.
Passo 2
Sejam
os elementos escolhidos em ordem crescente. A condição de espaçamento mínimo impõe
Queremos então traduzir esse requisito numa condição de diferença
, para aplicar a contagem usual de subconjuntos sem restrição de espaçamento.
Passo 3
Definimos novas variáveis
Cada vez que avançamos de
para
, subtraímos
unidades extras, de modo que
Logo, os
satisfazem
Passo 4
O problema em
é simplesmente: escolher
valores distintos dentre os inteiros de
até
, sem outra restrição de espaçamento. O número de maneiras de escolher
elementos de um conjunto de tamanho
sem outra condição é
. Aqui
.