(Generalizando o segundo Lema de Kaplansky) Seja
. Quantos são os
subconjuntos de
tais que o módulo da diferença entre quaisquer dois elementos é sempre maior ou igual a
? Considere que os elementos 1 e
de
são “consecutivos”.
Passo 1
O enunciado pede o número de subconjuntos de tamanho
em
, dispostos em círculo (isto é,
e
são consecutivos), de modo que a diferença circular entre quaisquer dois elementos seja sempre
, com
. Vamos traduzir isso num problema de dispersão de “gaps” ao redor do ciclo.
Passo 2
Ordene ciclicamente os elementos do subconjunto como
Cada
e
Para simplificar, coloque
de modo que
e
Denote
. O problema passa a contar soluções positivas de
Passo 3
O número de soluções em inteiros positivos desta equação é
Cada sequência
e cada escolha de ponto inicial
determina univocamente um subconjunto, mas cada subconjunto será gerado por exatamente
pares
(pois podemos começar a contar por qualquer um dos
elementos). Logo, o número de subconjuntos é
Passo 4
Agora use a identidade
para obter
Substituindo
, concluímos que o número desejado é