(A) Sala de Estudo: Lemas de Kaplansky

Clique no botão abaixo para visualizar a Sala.

Lemas de Kaplansky


O matemático francês Édouard Lucas (1842-1891), criador do famoso jogo Torre de Hanói, formulou um problema desafiador pouco antes de sua morte, em 1891.

Édouard Lucas
Imagem extraída de Mancala World.

O problema possui o seguinte enunciado:

“De quantas maneiras [tex]n[/tex] casais ([tex]n \geq 3[/tex]) podem sentar em [tex]2n[/tex] cadeiras diferentes em torno de um círculo de modo que pessoas do mesmo sexo não se sentem juntas e que nenhum homem fique ao lado de sua respectiva mulher?”

O enunciado do problema é bem simples, não é mesmo? Já a sua solução…
Esse problema ficou conhecido como o Problema de Lucas, ou Ménage Pròbleme, e os matemáticos da época demoraram mais de meio século para resolvê-lo.
Particularmente, em 1943, o matemático canadense-americano Irving Kaplansky (1917-2006) apresentou uma solução para o Problema de Lucas em um artigo publicado no Bulletin of the American Mathematical Society. Nessa solução, Kaplansky desenvolveu dois métodos de contagem que são conhecidos hoje como “Lemas de Kaplansky”. (Na Matemática, lema é um resultado intermediário que é utilizado para provar um outro resultado mais importante.)

Irving Kaplansky
Imagem extraída de PeoplePill.

A solução do Problema de Lucas não é o nosso foco principal; os Lemas de Kaplansky são os objetos de estudo desta Sala!
Enunciaremos esses resultados e resolveremos alguns problemas de contagem com essas novas ferramentas. Apesar de não serem comumente abordados nas escolas durante o estudo da Análise Combinatória, veremos que as aplicações desses lemas são simples e nos ajudarão a solucionar exercícios bem interessantes. Com relação ao Problema de Lucas, devido à variedade de técnicas de contagem em sua resolução, deixaremos sua demonstração no final da Sala apenas como leitura para os interessados.

Alguns conceitos e princípios de contagem serão necessários para uma boa compreensão do tema: Combinação simples; Princípio Multiplicativo e Princípio Aditivo. Se você não se lembra deles é só clicar no botão abaixo.




O Primeiro Lema de Kaplansky

Para compreendermos a utilidade do Primeiro Lema de Kaplansky, vamos começar explorando a resolução de um problema, antes de apresentarmos o Lema.

Problema 1: Quantos subconjuntos de [tex]3[/tex] elementos podemos formar com os elementos do conjunto
[tex]\qquad \qquad A = \{1, 2, 3, 4, 5, 6, 7, 8\},[/tex]
de modo que em cada subconjunto não haja números consecutivos?
Solução:
Para que não haja a necessidade de enumerar exaustivamente todos os subconjuntos com a propriedade requerida, ao definir um subconjunto de [tex]A[/tex], iremos marcar com o sinal [tex]+[/tex] a posição dos elementos que farão parte do subconjunto e com o sinal [tex]−[/tex] a posição dos elementos que não farão parte, considerando a posição dos elementos na sequência [tex] 1, 2, 3, 4, 5, 6, 7, 8.[/tex] Assim, por exemplo:
[tex]\qquad \{3, 6, 8\}[/tex] seria representado por [tex]\,-\,-\,+\, \,-\,-\,\,+\,-\,+[/tex],
[tex]\qquad \{4, 5, 7\}[/tex] seria representado por [tex]\, -\,-\,-\,+\,+\,-\,+\,-[/tex].

Observe que, particularmente, o conjunto do primeiro exemplo representa uma possibilidade de escolha para este problema, mas o do segundo não, já que [tex]4[/tex] e [tex]5[/tex] são consecutivos.
Para formar um subconjunto com três elementos, sem dois números consecutivos, devemos distribuir três sinais [tex]+[/tex] e cinco sinais [tex]−~[/tex], sem que haja dois sinais [tex]+[/tex] consecutivos.
Para fazer isso:
colocamos os cinco sinais [tex]−[/tex] (o primeiro passo da escolha);
em seguida, distribuímos os três sinais [tex]+[/tex] nos seis espaços que ficaram definidos (representados abaixo pelos quadradinhos), com no máximo um sinal por espaço. Perceba que isso pode ser feito de [tex]C_{6}^{3}[/tex] maneiras diferentes.
Finalmente, utilizando o princípio Multiplicativo, temos [tex]\boxed{1 \cdot C_{6}^{3}=20}[/tex] subconjuntos.

No caso geral, o número de subconjuntos com [tex]p[/tex] elementos de [tex]\{1,2,3,…,n\}[/tex], com [tex]p\leq n/2[/tex], nos quais não há números consecutivos é [tex]C_{n-p+1}^{p}[/tex].
Justificativa: Seguindo o mesmo raciocínio da resolução do Problema 1, devemos ter [tex]p[/tex] sinais [tex]+[/tex] e “[tex]n-p[/tex]” sinais [tex]-[/tex]. Ao distribuir os sinais [tex]-~[/tex], temos “[tex]n-p+1[/tex]” espaços para os [tex]p[/tex] sinais [tex]+[/tex]. Assim, teremos:
[tex]1[/tex] modo de posicionar os sinais [tex]–[/tex] e
[tex]C_{n-p+1}^{p}[/tex] maneiras de organizar os sinais [tex]+[/tex] nos espaços criados.
Assim, não haverá números consecutivos nos subconjuntos.

Este é exatamente o Primeiro Lema de Kaplansky:

Primeiro Lema de Kaplansky:
O número de subconjuntos com [tex]p[/tex] elementos de [tex]\{1,2,3,…,n\}[/tex], sendo [tex]p\leq n/2 [/tex] e nos quais não há números consecutivos, é:
[tex]\qquad \qquad \boxed{f(n,p)= C_{n-p+1}^{p}}.[/tex]

Mesmo sabendo de sua importância, o objetivo principal desta Sala não é a notação em si, mas sim resolver problemas de contagem utilizando essa nova técnica. Na verdade, a ideia central é repetir esse raciocínio, mas em problemas com “roupagens” diferentes.
Então, que tal resolver alguns problemas?

Problema 2: Ao refazer seu calendário escolar para o segundo semestre, uma escola decidiu repor algumas aulas em exatamente quatro dos nove sábados disponíveis nos meses de outubro e novembro, com a condição de que não fossem utilizados dois sábados consecutivos.
Quantas são as possibilidades distintas de se atender às condições dessa reposição?
Solução:
Vamos representar cada um dos nove sábados disponíveis para reposição, em sequência, por um elemento do conjunto
[tex]\qquad \qquad S=\{1,2,3,4,5 ,6,7,8,9\}[/tex].
Assim, para resolver este problema, vamos procurar subconjuntos do conjunto [tex]S[/tex] com quatro elementos que não sejam números consecutivos, já que as reposições não devem ser feitas em sábados consecutivos.
Para formar um subconjunto com quatro elementos, sem dois números consecutivos, devemos distribuir quatro sinais [tex]+[/tex] e cinco sinais [tex]−[/tex], sem que haja dois [tex]+[/tex] consecutivos.
Assim,

distribuímos os cinco sinais [tex]−[/tex] (o primeiro passo da escolha)
em seguida, nos seis espaços que ficaram definidos, colocamos os quatro sinais [tex]+[/tex], com no máximo um sinal por espaço. Perceba que isso pode ser feito de [tex]C_{6}^{4}=15[/tex] maneiras diferentes.
Em notação, teremos: [tex]f(9,4)= C_{9-4+1}^{4}=C_{6}^{4}[/tex].

Logo, pelo Princípio Multiplicativo, a escola tem [tex]\boxed{1\cdot C_{6}^{4}=1 \cdot 15=15}[/tex] maneiras diferentes de repor essas aulas.

Problema 3: As provas de Aritmética, Álgebra, Combinatória, Geometria e Trigonometria de um Clube de Matemática devem ocorrer nas primeiras duas semanas do mês de março. De quantos modos os professores podem realizar essas provas de modo que não haja provas em dias consecutivos?
Solução:
Vamos representar cada um dos quatorze dias possíveis por um elemento do conjunto
[tex]\qquad \qquad M=\{1,2,3,4,5,6,7,8,9,10,11,12,13,14\}.[/tex]
Assim, devemos contar quantos subconjuntos de [tex]S[/tex] com [tex]5[/tex] elementos existem de modo a não ter elementos consecutivos. Para realizar essa contagem,

colocamos os nove sinais [tex]−[/tex];
em seguida, distribuímos os cinco sinais [tex]+[/tex] nos dez espaços que ficaram definidos.

Perceba que isso pode ser feito de [tex]C_{10}^{5}=252[/tex] maneiras diferentes.
Usando a notação definida, teremos [tex]f(14,5)= C_{14-5+1}^{5}=C_{10}^{5}=252[/tex].

Esse número representa as maneiras de escolher os dias das provas. Mas, após escolher os dias, temos que organizar a ordem na qual as provas serão aplicadas e isso pode ser feito de [tex]5!=120[/tex] modos.
Portanto, pelo Princípio Multiplicativo, há [tex]\boxed{252\cdot 120=30240}[/tex] modos de aplicar essas provas.

Note que, até aqui, todos os problemas apresentavam, basicamente, sempre a mesma restrição: apenas não possuir números consecutivos.
E se, por exemplo, quiséssemos contar quantos subconjuntos, com [tex]3[/tex] elementos, do conjunto [tex]S=\{1,2,3,4,5,6,7,8,9,10\}[/tex] podemos formar de modo que entre dois elementos escolhidos para o subconjunto haja pelo menos [tex]2[/tex] elementos não escolhidos, como por exemplo o subconjunto [tex]\{2,6,9\}[/tex]?
Vamos lá!

Novamente, iremos marcar com o sinal [tex]+[/tex] a posição dos elementos que farão parte do subconjunto e com o sinal [tex]−[/tex] a posição dos elementos que não farão parte. Assim:
[tex]\qquad \{2, 6, 9\}[/tex] seria representado por [tex]\,-\, +\, -\, -\, -\, +\, -\, -\, +\, -\,,[/tex]
[tex]\qquad \{3, 5, 10\}[/tex] seria representado por [tex]\,- \,- \,+ \,- \,+ \,- \,- \,- \,- \,+\,.[/tex]
(Observe que, particularmente, o conjunto do primeiro exemplo representa uma possibilidade de escolha, mas o do segundo não, já que [tex]3[/tex] e [tex]5[/tex] não possuem dois elementos não escolhidos entre eles.)
Para fazer essa contagem, vamos, inicialmente, posicionar os [tex]3[/tex] sinais de [tex]+[/tex] formando uma fila e deixando [tex]4[/tex] espaços entre eles.Os sinais de [tex]–[/tex] serão colocados nesses espaços. Vamos chamar de [tex]x,\,y,\, z[/tex] e [tex]w[/tex] a quantidade de sinais [tex]–[/tex] que colocaremos no primeiro, segundo, terceiro e quarto espaços, respectivamente.Dessa forma, devemos ter a seguinte equação linear com soluções inteiras e não negativas:
[tex]\qquad x+y+z+w=7[/tex], com [tex]y \geq 2~[/tex] e [tex]~z \geq 2.[/tex]
Na Sala de Estudos sobre Combinações Completas aprendemos a contar quantas soluções tem uma equação desse tipo, com esse tipo de restrições.
Substituindo, [tex]y=a+2[/tex] e [tex]z=b+2[/tex], obtemos a equação [tex]x+a+b+w=3[/tex], que tem
[tex]\qquad CR_{4}^{3}=C_{4+3-1}^{3}=C_{6}^{3}= \dfrac {6!}{3! \cdot 3!}= 20[/tex] soluções.
Portanto, há [tex]20[/tex] subconjuntos com [tex]3[/tex] elementos de modo que entre dois elementos escolhidos para o subconjunto haja pelo menos [tex]2[/tex] elementos não escolhidos.
É dessa forma que iremos generalizar o Primeiro Lema de Kaplansky.

De quantos modos é possível formar um subconjunto, com [tex]p[/tex] elementos, do conjunto [tex]\{ 1,2,3,4,…,n \}[/tex] de modo que entre cada dois elementos escolhidos para o subconjunto haja, no conjunto, pelo menos [tex]r[/tex] elementos não escolhidos para o subconjunto?

Seguindo o mesmo raciocínio, vamos indicar pelo sinal [tex]+[/tex] os elementos selecionados e pelo sinal [tex]-[/tex] os não selecionados. Assim, arrumamos uma fila com [tex]p[/tex] sinais [tex]+[/tex] e [tex](n-p)[/tex] sinais [tex]-[/tex] de modo que entre dois sinais [tex]+[/tex] haja pelo menos [tex]r[/tex] sinais [tex]-[/tex].
Chamando de [tex]x_{1},\,x_{2},\,x_{3},\, \dots ,\,x_{p}[/tex] e [tex]x_{p+1}[/tex] a quantidade de sinais [tex]–[/tex] que serão colocados em cada um dos [tex]p+1[/tex] espaços existentes entre os sinais [tex]+[/tex], temos que
[tex]\qquad x_{1}+x_{2}+x_{3}+ \dots +x_{p}+x_{p+1}=n-p[/tex], com [tex]x_{1},~x_{p+1} \geq 0~[/tex] e [tex]~x_{2},~x_{3},~\dots~,~x_{p} \geq r[/tex].

Como buscamos apenas soluções inteiras não negativas, podemos resolver a equação fazendo as seguintes substituições
[tex]\qquad \boxed{x_{2}=r+y_{2}}[/tex], [tex]~\boxed{x_{3}=r+y_{3}}, ~\dots~ ,\, \boxed{x_{p}=r+y_{p}}[/tex]
na equação
[tex]\qquad x_{1}+x_{2}+x_{3}+ \dots +x_{p}+x_{p+1}=n-p.[/tex]
Com isso, segue que:
[tex]\qquad x_{1}+(r+y_{2})+(r+y_{3})+ \dots + (r +y_{p})+x_{p+1}=n-p\\
\qquad x_1+y_2+y_3+⋯+y_p+x_{p+1}+(p-1)r=n-p\\
\qquad x_{1}+y_{2}+y_{3}+ \dots + y_{p} +x_{p+1}=n-p-(p-1)r.[/tex]

Como todas as incógnitas são números inteiros não negativos, aprendemos na Sala Combinação Completa que essa equação possui [tex]\boxed{CR\,_{p+1}^{n-p-(p-1)r}=C_{n-(p-1)r}^{p}= \dfrac {[n-(p-1)r]!}{p! \cdot [n-p-(p-1)r]!}}[/tex] soluções.

Assim, já podemos apresentar a generalização prometida do Primeiro Lema de Kaplansky:

Generalização do Primeiro Lema de Kaplansky:
Dado um conjunto [tex]\{1,2,3,4,…,n \}[/tex], o número de subconjuntos com [tex]p[/tex] elementos de modo que entre cada dois elementos escolhidos para o subconjunto haja pelo menos [tex]r[/tex] elementos não escolhidos é:
[tex]\qquad \qquad \boxed{f(n,p,r)=C_{n-(p-1)r}^{p}}.[/tex]

Observe que:
Para [tex]r=0[/tex], temos [tex]f(n,p,0)= C_{n}^{p}[/tex]; o que corresponde ao número de Combinações Simples de [tex]n[/tex] elementos tomados [tex]p[/tex] a [tex]p.[/tex]
Para [tex]r=1[/tex], temos [tex]f(n,p,1)=C_{n-p+1}^{p}[/tex]; o que corresponde ao Primeiro Lema de Kaplansky.




O Segundo Lema de Kaplansky

O Segundo Lema de Kaplansky apresenta a mesma ideia do Primeiro Lema; porém, impõe uma consideração extra de que [tex]1[/tex] e [tex]n[/tex] são números consecutivos.
Portanto, consideraremos nesta discussão que os números [tex]1,~2,~3,~…,~n [/tex] estão colocados em círculo, nesta ordem.

Considere que os números [tex]1,~2,~3,~…,~n [/tex] estão colocados em círculo, nesta ordem. De quantos modos podemos formar um subconjunto com [tex]p[/tex] elementos de maneira que não sejam escolhidos números consecutivos?
Por estarem em círculo, os números [tex]1[/tex] e [tex]n[/tex] agora são consecutivos. Para resolver este problema, vamos determinar:
(I) a “quantidade de subconjuntos que satisfazem as condições do problema e aos quais o elemento [tex]1[/tex] pertence” e
(II) a “quantidade de subconjuntos que satisfazem as condições do problema e aos quais o elemento [tex]1[/tex] não pertence”.

(I) Se o elemento [tex]1[/tex] pertence ao subconjunto, então devemos escolher [tex](p-1)[/tex] elementos do conjunto [tex]\{3,4,5,…,n-1\}[/tex] (como o [tex]1[/tex] figura no conjunto, não podemos ter os elementos [tex]2[/tex] e [tex]n[/tex]) tomando o cuidado de não escolhermos elementos consecutivos.
Ora, como vimos no Primeiro Lema de Kaplansky, o número de maneiras de escolhermos [tex](p-1)[/tex] elementos (sinais [tex]+[/tex]) em um conjunto que possui [tex](n-3)[/tex] elementos (portanto, [tex](n-3)-(p-1)[/tex] sinais [tex]-[/tex]) sem que haja elementos consecutivos é dado por:
[tex]\qquad \qquad f(n-3,p-1)=C_{n-3-(p-1)+1}^{p-1}=C_{n-p-1}^{p-1}\,.\qquad \textcolor{#8B5A2B}{(i)}[/tex]

(II) Se o elemento [tex]1[/tex] não pertence ao subconjunto, então devemos escolher [tex]p[/tex] elementos do conjunto [tex]\{2,3,4,…,n\}[/tex] (como o [tex]1[/tex] não figura no conjunto, podemos ter os elementos [tex]2[/tex] e [tex]n[/tex]) tomando o cuidado de não escolhermos elementos consecutivos.
Novamente, pelo Primeiro Lema de Kaplansky, o número de maneiras de escolhermos [tex]p[/tex] elementos (sinais [tex]+[/tex]) em um conjunto que possui [tex](n-1)[/tex] elementos (portanto, [tex](n-1-p)[/tex] sinais [tex]-[/tex]) sem que haja elementos consecutivos é dado por:
[tex]\qquad \qquad f(n-1,p)=C_{n-1-p+1}^{p}=C_{n-p}^{p}\,.\qquad \textcolor{#8B5A2B}{(ii)}[/tex]

Pelo Princípio Aditivo, por [tex]\textcolor{#8B5A2B}{(i)}[/tex] e por [tex]\textcolor{#8B5A2B}{(ii)}[/tex], a quantidade [tex]Q[/tex] de subconjuntos em questão é dada por:
[tex]\qquad Q=C_{n-p-1}^{p-1}~+~C_{n-p}^{p}~.[/tex]
Utilizando agora a definição de combinação simples, temos:
[tex]\qquad Q=C_{n-p-1}^{p-1}~+~C_{n-p}^{p}\\
\qquad Q=\dfrac {(n-p-1)!}{(p-1)!\cdot (n-2p)!} + \dfrac{(n-p)!}{p! \cdot (n-2p)!}\\
\qquad Q=\dfrac{(n-p-1)! \cdot p+(n-p)!}{p! \cdot (n-2p)!}\\
\qquad Q=\dfrac {(n-p-1)! \cdot[p+(n-p)]}{p! \cdot (n-2p)!}\\
\qquad Q=\dfrac {n \cdot (n-p-1)!}{p! \cdot (n-2p)!}\\
\qquad Q= \dfrac {n}{(n-p)} \cdot \dfrac{(n-p)!}{p! \cdot (n-2p)!}\\
\qquad Q= \dfrac {n}{(n-p)} \cdot C_{n-p}^{p}\,.[/tex]

Assim, podemos apresentar o Segundo Lema de Kaplansky:

Segundo Lema de Kaplansky:
O número de subconjuntos com [tex]p[/tex] elementos do conjunto [tex]\{1,2,3,…,n \}[/tex] nos quais não há números consecutivos, considerando [tex]1[/tex] e [tex]n[/tex] como consecutivos, é igual a
[tex]\qquad \qquad \boxed{g(n,p)=\dfrac {n}{n-p} \cdot C_{n-p}^{p}}.[/tex]

Não estamos interessados que você apenas utilize e memorize as fórmulas apresentadas; mas que, principalmente, você pratique e entenda as técnicas de contagem. Assim, note que ao resolvermos um problema com o Segundo Lema, utilizamos duas vezes o Primeiro Lema e o Princípio Aditivo.
Vejamos mais dois problemas…

Problema 4: A professora Sonia planejou ter três encontros semanais com seus alunos do Clube de Matemática durante um ano. Quantos são os modos de ela fixar os três dias das aulas, se os alunos não podem ter aulas em dias consecutivos?
Solução:
Vamos representar cada um dos sete dias da semana (segunda, terça, quarta, quinta, sexta, sábado e domingo) por um elemento do conjunto [tex]S=\{1,2,3,4,5 ,6,7 \}[/tex]. Perceba que no nosso problema os números [tex]1[/tex] e [tex]7[/tex] são consecutivos.

Então, vamos abrir o problema em dois casos:
(I) O dia [tex]1[/tex] foi escolhido; e
(II) O dia [tex]1[/tex] não foi escolhido.

    (I) No primeiro caso, com o [tex]1[/tex] no conjunto, temos apenas três situações a considerar: [tex]\{1,3,5 \}[/tex], [tex]\{1,3,6 \}[/tex] e [tex]\{1,4,6 \}[/tex]. Poderíamos ter conseguido esse resultado sem a necessidade de escrever todas as soluções:
    Utilizando o Primeiro Lema de Kaplansky, como o [tex]1[/tex] já foi escolhido, temos que escolher dois elementos do conjunto [tex]\{3, 4, 5, 6 \}[/tex] sem que haja dois consecutivos. Daí, temos dois sinais [tex]–[/tex] e dois sinais [tex]+[/tex]:
    [tex]\qquad \qquad \quad \quad\textcolor{#4B240B}{ \Box~-~\Box~-~\Box} [/tex]
    Ao formar uma fila com os sinais [tex]-[/tex], há [tex]C_{3}^{2}=3[/tex] modos de posicionar os sinais [tex]+[/tex].
    (II) Já no segundo caso, temos que escolher três elementos [tex]\{ 2,3,4,5,6,7 \}[/tex] sem que haja números consecutivos. Aqui devemos ter três sinais [tex]–[/tex] e três sinais [tex]+[/tex], sem que haja dois sinais [tex]+[/tex] consecutivos.
    [tex]\qquad \qquad \quad \quad\textcolor{#4B240B}{ \Box~-~\Box~-~\Box~-~\Box} [/tex]
    Ao formar uma fila com os sinais [tex]-[/tex], há [tex]C_{4}^{3}=4[/tex] modos de posicionar os sinais [tex]+[/tex].

Logo, pelo Princípio Aditivo, há [tex]\boxed{3+4=7}[/tex] maneiras para a escolha dos dias de aula.
Observe que, utilizando a fórmula do Segundo Lema de Kaplansky, temos:
[tex]\qquad \qquad g(7,3)= \dfrac{7}{7-3} \cdot C_{7-3}^{3}= \dfrac{7}{4} \cdot 4=\boxed{~7~}.[/tex]

Problema 5: Quatro amigos, Alex, Bruno, Carlos e Daniel, devem se sentar em [tex]15[/tex] cadeiras colocadas em torno de uma mesa circular. De quantos modos esses quatro amigos podem se sentar de modo que não haja ocupação de cadeiras adjacentes?
Solução:
(1) O número de maneiras de escolhermos as [tex]4[/tex] cadeiras das [tex]15[/tex] possíveis em círculo, sem que haja cadeiras adjacentes, pode ser calculada pelo Segundo Lema de Kaplansky:
[tex]\quad \begin{align}g(15,4)&=\dfrac{15}{15-4} \cdot C_{15-4}^{4}= \dfrac{15}{11} \cdot C_{11}^{4}\\
&= \dfrac {15}{11} \cdot \dfrac {11!}{4! \cdot (11-4)!}\\
&=450.\end{align}[/tex]
Portanto, existem [tex]450[/tex] modos de escolher as cadeiras que serão ocupadas.
(2) Após escolher as cadeiras, devemos posicionar os amigos; o que pode ser feito de [tex]4!=24[/tex] maneiras.

Finalizando, pelo Princípio Multiplicativo há [tex]\boxed{450 \cdot 24=10800}[/tex] soluções para o problema.

Podemos generalizar o Segundo Lema, assim como fizemos para o Primeiro.
Para ajudar na generalização, considere o problema a seguir e acompanhe atentamente a sua solução.

Problema 6: Entre [tex]12[/tex] cadeiras desocupadas e arrumadas em círculo, de quantos modos podemos escolher [tex]3[/tex] delas de modo que haja pelo menos duas cadeiras vazias entre as escolhidas?

Solução:
Observe que o que queremos calcular é a quantidade de subconjuntos, com [tex]3[/tex] elementos, do conjunto
[tex]\qquad \qquad \quad \quad S= \{1,2,3,4,5,6,7,8,9,10,11,12 \}[/tex], sendo [tex]1[/tex] e [tex]12[/tex] consecutivos,
de modo que entre dois elementos escolhidos para o subconjunto haja pelo menos [tex]2[/tex] elementos não escolhidos; como, por exemplo, os subconjuntos [tex]\{1,4,10 \}[/tex], [tex]\{2,7,11 \}[/tex] e [tex]\{3,6,12 \}[/tex].
Para resolver este problema, vamos dividi-lo em dois casos:
1º) Os subconjuntos que contêm algum dos elementos [tex]\{ 1, 2 \}[/tex]; e
2º) Os subconjuntos que não contêm nenhum dos elementos [tex]\{ 1, 2 \}[/tex].

    1º) Para a contagem do primeiro caso, como o [tex]1[/tex] já figura no conjunto, não podemos ter os elementos [tex]2[/tex], [tex]3[/tex], [tex]11[/tex] e [tex]12[/tex]. Assim, devemos escolher dois elementos do conjunto [tex]\{4,5,6,7,8,9,10 \}[/tex] de modo que haja pelo menos duas cadeiras vazias entre os escolhidos.
    Ora, como vimos na generalização do Primeiro Lema de Kaplansky, o número de maneiras de escolhermos dois elementos em um conjunto que possui sete elementos de modo que não haja pelo menos dois elementos consecutivos é dado por:
    [tex]\qquad f(7,2,2)=C_{7-(2-1)2}^{2}=C_{5}^{2}=10.[/tex]
    De modo análogo, também temos [tex]10[/tex] subconjuntos, satisfazendo a restrição, em que o elemento [tex]2[/tex] está contido.
    Assim, temos [tex]2 \cdot 10=20[/tex] subconjuntos que contêm algum dos elementos do conjunto [tex]\{1, 2 \}[/tex].

    2º) Para a contagem do segundo caso, como os elementos [tex]1[/tex] e [tex]2[/tex] não pertencem ao subconjunto, então devemos escolher três cadeiras do conjunto [tex]\{ 3,4,5,6,7,8,9,10,11,12 \}[/tex] de modo que haja pelo menos duas cadeiras vazias entre os escolhidos.
    Novamente, pela generalização do Primeiro Lema de Kaplansky, o número de maneiras de escolhermos [tex]3[/tex] elementos em um conjunto que possui [tex]10[/tex] elementos de modo que entre cada dois elementos escolhidos haja, no conjunto, pelo menos [tex]2[/tex] não escolhidos é:
    [tex]\qquad f(10,3,2)=C_{10-(3-1) \cdot 2}^{3}=C_{6}^{3}=20.[/tex]

Portanto, pelo Princípio Aditivo, a solução deste problema é dada pela soma das quantidades encontradas nos casos, ou seja, [tex]20 + 20 = \boxed{40 \text{ subconjuntos}}.[/tex]

Assim, já podemos generalizar o Segundo Lema de Kaplansky. Essa generalização é a resposta à seguinte pergunta:

Quantos são os subconjuntos do conjunto [tex]\{1,2,3,4, \cdots , n \}[/tex] com [tex]p[/tex] elementos tais que entre cada dois elementos quaisquer haja pelo menos [tex]r[/tex] elementos não escolhidos, se considerarmos [tex]1[/tex] e [tex]n[/tex] elementos consecutivos?
Essa quantidade de subconjuntos pode ser calculada pela soma do “número de subconjuntos satisfazem as exigências e não contêm um dos elementos [tex]\{1,2,3,4, \cdots , r \}[/tex]” com “o número de subconjuntos que satisfazem as exigências e contêm um desses elementos”.
Então, vamos calcular essa soma.
Observe que:
O número de subconjuntos que satisfazem as exigências e não contêm um dos elementos [tex]\{1,2,3,4, \cdots , r \}[/tex] é igual a [tex]f(n-r,p,r).[/tex]
O número de subconjuntos que satisfazem as exigências e contêm um desses elementos é igual a [tex]r \cdot f(n-2r-1,p-1,r).[/tex]
Calculando a soma [tex]S=f(n-r,p,r)+rf(n-2r-1,p-1,r)[/tex], temos:
[tex]\qquad S=C_{n-r-(p-1) \cdot r}^{p} + r\cdot C_{n-2r-1-(p-1-1) \cdot r}^{p-1}\\
\qquad S=C_{n-p \cdot r}^{p} + r \cdot C_{n-p \cdot r-1}^{p-1}\\
\qquad S=C_{n-p \cdot r}^{p}+r \cdot \dfrac {(n-p \cdot r-1)!}{(p-1)! \cdot (n-p \cdot r-p)!}\\
\qquad S=C_{n- p \cdot r}^{p}+ r \cdot \dfrac {(n-p \cdot r-1)!}{(p-1)!\cdot (n-p \cdot r-p)!} \cdot \dfrac {(n-p \cdot r)}{(n-p \cdot r)} \cdot \dfrac {p}{p}\\
\qquad S=C_{n-p \cdot r}^{p}+ \dfrac {p \cdot r} {n-p \cdot r} \cdot C_{n-p\cdot r}^{p}\\
\qquad S=C_{n-p \cdot r}^{p} \cdot \left(1+ \dfrac {p \cdot r}{n-p \cdot r}\right)\\
\qquad S=\dfrac {n} {n-p \cdot r} \cdot C_{n-p \cdot r}^{p}\,.[/tex]
A notação dessa generalização é [tex]\boxed{g(n,p,r)= \dfrac {n} {n-p \cdot r} \cdot C_{n-p \cdot r}^{p}}.[/tex]

Aqui está a generalização prometida do Segundo Lema de Kaplansky:

Generalização do Segundo Lema de Kaplansky:
O número de subconjuntos com [tex]p[/tex] elementos do conjunto [tex]\{1,2,3,4, \cdots , n \}[/tex], considerando [tex]1[/tex] e [tex]n[/tex] consecutivos, de modo que entre cada dois elementos escolhidos para o subconjunto haja pelo menos [tex]r[/tex] elementos não escolhidos é dado por:
[tex]\qquad \qquad \boxed{g(n,p,r)= \dfrac {n} {n-p \cdot r} \cdot C_{n-p \cdot r}^{p}}.[/tex]
Note que:
Para [tex]r=0[/tex], temos [tex]g(n,p,0)= C_{n}^{p}[/tex]; o que corresponde ao número de Combinações Simples de [tex]n[/tex] elementos tomados [tex]p[/tex] a [tex]p.[/tex]
Para [tex]r=1[/tex], temos [tex]g(n,p,1)= \dfrac {n} {n-p} \cdot C_{n-p}^{p}[/tex]; o que corresponde ao Segundo Lema de Kaplansky.

Que tal você resolver alguns exercícios?




Exercícios

Exercício 1: Cinco candidatos estão concorrendo às vagas em um clube de matemática. Para isso devem realizar uma prova feita pelo professor orientador. Eles farão essa avaliação em uma sala onde há [tex]15[/tex] cadeiras enfileiradas. Para que não haja cola o professor precisa escolher cadeiras que não sejam consecutivas. De quantas formas o professor pode escolher as cadeiras?

Exercício 2: Quantos são os anagramas da palavra MISSISSIPI nos quais não há duas letras S consecutivas?

Exercício 3: Idem ao exercício anterior, quantos são os anagramas de ARARAQUARA que não possuem duas letras A consecutivas?

Exercício 4: (Enem PPL de 2020 – Adaptado) O governador de um estado propõe a ampliação de investimentos em segurança no transporte realizado por meio de trens. Um estudo para um projeto de lei prevê que se tenha a presença de três agentes mulheres, distribuídas entre os [tex]6[/tex] vagões de uma composição, de forma que duas dessas agentes não estejam em vagões adjacentes, garantindo assim maior segurança aos usuários.

A expressão que representa a quantidade de maneiras distintas das três agentes serem distribuídas nos vagões é

a) [tex]C_{4}^{3}+3![/tex]
b) [tex]C_{6}^{3}[/tex]
c) [tex]C_{4}^{3} \cdot 3![/tex]
d) [tex]P_{6}^{3}[/tex]
e) [tex]P_{4}^{3} \cdot 3![/tex]

Exercício 5: (OBMEP-2019) As [tex]6[/tex] cadeiras de uma fila são numeradas de [tex]1[/tex] a [tex]6[/tex] e devem ser ocupadas uma de cada vez de modo que, sempre que possível, é escolhida uma cadeira sem vizinhas ocupadas. Por exemplo, é válida a ordem de ocupação [tex]1 6 3 2 4 5[/tex], em que a primeira pessoa ocupa a cadeira [tex]1[/tex], a segunda, a cadeira [tex]6[/tex], a terceira, a cadeira [tex]3[/tex], a quarta, a cadeira [tex]2[/tex], a quinta, a cadeira [tex]4[/tex] e a última, a cadeira [tex]5[/tex]. Já a ordem [tex]1 5 2 3 6 4[/tex] não é válida, pois a terceira pessoa sentou-se ao lado da primeira quando poderia ter se sentado em uma cadeira sem vizinhas ocupadas. Quantas ordens de ocupação válidas existem?

a) [tex]72[/tex]
b) [tex]108[/tex]
c) [tex]144[/tex]
d) [tex]192[/tex]
e) [tex]216[/tex]

Exercício 6: (IME) Doze cavaleiros estão sentados em torno de uma mesa redonda. Cada um dos doze cavaleiros considera seus dois vizinhos como rivais. Deseja-se formar um grupo de [tex]5[/tex] cavaleiros para libertar uma princesa. Nesse grupo não poderá haver cavaleiros rivais. Determine de quantas maneiras é possível escolher esse grupo.

Exercício 7: Um estacionamento circular possui [tex]14[/tex] vagas, uma ao lado da outra, inicialmente todas livres. Um carro preto, um azul, um vermelho e um verde chegam a esse estacionamento. De quantas maneiras diferentes esses carros podem ocupar quatro vagas de forma que haja pelo menos uma vaga livre entre eles?

Imagem adaptada do site iStock. (Acesso em 24/01/2024.)

Exercício 8: De quantos modos podemos acomodar [tex]4[/tex] homens e [tex]8[/tex] mulheres em uma mesa circular sem que haja dois homens em posições adjacentes?




Para encerrar, caso queira ver a Solução de Kaplansky para o Problema de Lucas, clique AQUI.
A versão apresentada foi extraída da referência [3] e pode trazer alguma dificuldade para quem não está habituado com a leitura de textos de Matemática.



Equipe COM – OBMEP

Referências:
[1] A Matemática do Ensino Médio (volume 2): Coleção do Professor de Matemática – Elon Lages Lima; Paulo Cesar Pinto Carvalho; Eduardo Wagner e Augusto César Morgado.
[2] A Matemática do Ensino Médio (volume 2): Coleção do Professor de Matemática – Elon Lages Lima; Paulo Cesar Pinto Carvalho; Eduardo Wagner e Augusto César Morgado.
[3] Análise Combinatória e Probabilidade – Augusto César Morgado; João Bosco Pitombeira de Carvalho; Paulo Cesar Pinto Carvalho e Pedro Fernandez.
[4] Matemática Discreta: Coleção Profmat – Augusto César Morgado; Paulo Cesar Pinto Carvalho.
[5] O Problema de Lucas (Ménage Pròbleme) – Francisco Carpegiani Medeiros Borges. Online Encyclopedia Riordanica

Link permanente para este artigo: http://clubes.obmep.org.br/blog/a-sala-de-estudo-lemas-de-kaplansky/