De quantas formas podemos escolher um subconjunto de p elementos do conjunto \{1,2,3, \ldots, n\} 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 p elementos do conjunto \{1,2,3,\dots,n\} de forma que, para quaisquer dois elementos distintos x_i,x_j desse subconjunto, valha
|x_i - x_j|\;\ge3.
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 x_1<x_2<\cdots<x_p os elementos escolhidos em ordem crescente. A condição de espaçamento mínimo impõe
x_{i+1}-x_i \;\ge\;3, \quad i=1,2,\dots,p-1.
Queremos então traduzir esse requisito numa condição de diferença \ge1, para aplicar a contagem usual de subconjuntos sem restrição de espaçamento.

Passo 3

Definimos novas variáveis
y_i = x_i \;-\;2\,(i-1), \quad i=1,2,\dots,p.
Cada vez que avançamos de x_i para x_{i+1}, subtraímos 2 unidades extras, de modo que
y_{i+1} - y_i = \bigl(x_{i+1}-2i\bigr)-\bigl(x_i-2(i-1)\bigr) = \bigl(x_{i+1}-x_i\bigr)-2 \;\ge\;3-2=1.
Logo, os y_i satisfazem
1 \le y_1 < y_2 < \cdots < y_p \quad\text{e}\quad y_p \le n - 2(p-1).

Passo 4

O problema em y é simplesmente: escolher p valores distintos dentre os inteiros de 1 até n-2(p-1), sem outra restrição de espaçamento. O número de maneiras de escolher p elementos de um conjunto de tamanho N sem outra condição é \binom{N}{p}. Aqui N = n-2(p-1).

Resposta

\boxed{ \binom{\,n-2(p-1)\,}{p} } \quad\text{ou equivalentemente}\quad \binom{\,n-2p+2\,}{p}.

Exercícios relacionados