(Generalizando o segundo Lema de Kaplansky) Seja \Omega=\{1,2, \ldots, n\}. Quantos são os p subconjuntos de \Omega tais que o módulo da diferença entre quaisquer dois elementos é sempre maior ou igual a r(r \geq 2) ? Considere que os elementos 1 e n de \Omega são “consecutivos”.

Passo 1

O enunciado pede o número de subconjuntos de tamanho p em \Omega=\{1,2,\dots,n\}, dispostos em círculo (isto é, 1 e n são consecutivos), de modo que a diferença circular entre quaisquer dois elementos seja sempre \ge r, com r\ge2. Vamos traduzir isso num problema de dispersão de “gaps” ao redor do ciclo.

Passo 2

Ordene ciclicamente os elementos do subconjunto como \;a_1<a_2<\cdots<a_p\) no sentido crescente e defina as distâncias \[d_i = \begin{cases} a_{i+1}-a_i, & i=1,2,\dots,p-1,\\\ a_1+n-a_p, & i=p. \end{cases}
Cada d_i\] deve satisfazer \(d_i\ge r e
d_1+d_2+\cdots+d_p = n.
Para simplificar, coloque
x_i = d_i - (r-1),
de modo que x_i\ge1 e
\sum_{i=1}^p x_i = \sum_{i=1}^p\bigl(d_i-(r-1)\bigr) = n - p(r-1).
Denote N = n - p(r-1). O problema passa a contar soluções positivas de
x_1 + x_2 + \cdots + x_p = N.

Passo 3

O número de soluções em inteiros positivos desta equação é
\binom{N-1}{p-1}\,.
Cada sequência (x_1,\dots,x_p) e cada escolha de ponto inicial a_1\in\{1,\dots,n\} determina univocamente um subconjunto, mas cada subconjunto será gerado por exatamente p pares \bigl(a_1,(x_i)\bigr) (pois podemos começar a contar por qualquer um dos p elementos). Logo, o número de subconjuntos é
\frac{n}{p}\,\binom{N-1}{p-1}.

Passo 4

Agora use a identidade
\binom{N-1}{p-1} = \frac{p}{N}\,\binom{N}{p}
para obter
\frac{n}{p}\,\binom{N-1}{p-1} = \frac{n}{p}\,\frac{p}{N}\,\binom{N}{p} = \frac{n}{N}\,\binom{N}{p}.
Substituindo N=n - p(r-1), concluímos que o número desejado é
\frac{n}{\,n - p(r-1)\,}\;\binom{\,n - p(r-1)\,}{\,p\,}.

Resposta

\frac{n}{\,n - p(r-1)\,}\;\binom{\,n - p(r-1)\,}{\,p\,}.

Exercícios relacionados