.Sala de Estudo: Lemas de Kaplansky

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.

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.

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.

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]

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.

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]

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]

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?