UFRPE-DM Os Lemas de Kaplansky

Seção 2.4 Os Lemas de Kaplansky

Subseção 2.4.1 Nota Histórica

Irving Kaplansky, matemático americano, nasceu em 22 de março de 1917 em Toronto e faleceu em 25 de junho de 2006. O talentoso matemático publicou o artigo "Solution of the problème des ménages" no Boletim da Sociedade Americana de Matemática em 1943, com uma solução para o afamado Problema de Lucas.

Kaplansky foi para a Universidade de Harvard e recebeu seu Ph.D. lá em 1941, trabalhando com Saunders MacLane. Ele foi instrutor de Benjamin Peirce em Harvard de 1941 a 1944 e, em seguida, ingressou no Grupo de Matemática Aplicada fazendo trabalhos de guerra na Universidade de Columbia de 1944 a 1945.

Seu trabalho foi bastante extenso na matemática, incluindo desde áreas da álgebra até grandes contribuições na Teoria dos Anéis, Teoria dos Grupos e Teoria dos Corpos. Publicou muitos artigos e trabalhou com diversos coautores.

Figura 2.4.1. Irving Kaplansky, fonte: www.ams.org

Subseção 2.4.2 O 1º Lema de Kaplansky

Para mostrar os benefícios dos Lemas de Kaplansky, iniciaremos a seção com o exemplo a seguir:

Exemplo 2.4.2.

De quantos maneiras podemos formar um subconjunto com 4 elementos, do conjunto

\begin{equation*} A=\{a,b,c,d,e,f,g,h\}, \end{equation*}

de modo que não possuam duas letras que ocupem posições consecutivas no alfabeto?

Solução.

Esse problema será resolvido criando uma forma alternativa de representar os subconjuntos onde marcaremos com o sinal \((+)\) os elementos pertencente ao subconjunto e com o sinal \((-)\) os elementos que não pertencentes ao subconjunto.

\begin{equation*} \{a,c,e,h\} \text{ será representado por } +-+-+--+ \end{equation*}

\begin{equation*} \{b,d,f,h\} \text{ será representado por } -+-+-+-+ \end{equation*}

\begin{equation*} \{b,e,g,h\} \text{ será representado por } -+--+-++ \end{equation*}

O terceiro caso não satisfaz as condições do enunciado, pois 2 \((+)\) juntos significa que teremos letras consecutivas (do alfabeto).

Assim, compreendendo o problema observa-se que para soluciona-lo devemos calcular o número de formas distintas de permutar 8 símbolos, onde \(4\) são \((-)\) e 4 são \((+)\) de modo que não tenha 2 símbolos \((+)\) juntos.

\begin{equation*} \LARGE \bigcirc-\bigcirc-\bigcirc-\bigcirc-\bigcirc \end{equation*}

Veja que de acordo com o esquema, de círculos e traços, podem-se colocar 4 símbolos \((+)\) em quaisquer dos cinco lugares, ou seja, é possível escolher 4 dos 5 lugares disponíveis (representados pelas circunferências) para por os símbolos \((+)\) o que pode ser realizado de

\begin{equation*} C_5^4=5 \text{ modos distintos}. \end{equation*}

Dessa forma 5 subconjuntos podem ser formados, os quais estão listados abaixo:

\begin{equation*} \{ a, c, e, g \}, \{ a, c, e, h \}, \{ a, c, f, h \}, \{ a, d, f, h \}, \{ b, d, f, h \} \end{equation*}

Teorema 2.4.3.

(1º Lema de Kaplansky) O número de subconjuntos com \(p\) elementos de \(A=\{1,2,3,\cdots,n\}\) nos quais não há números consecutivos é:

\begin{equation*} K(n,p)=C_{n-p+1}^p. \end{equation*}

Demonstração.

Deseja-se formar subconjuntos formados por \(p\) elementos não consecutivos de \(A\text{.}\) Da mesma forma que o Exemplo 2.4.2, os elementos de \(A\) que figuram nos subconjuntos serão representados com o símbolo \((+)\) e os elementos de \(A\) que não figuram nos subconjuntos são representados com o símbolo \((-)\text{.}\) Desta forma teremos \((n-p)\) elementos que serão representados com o símbolo \((-)\text{.}\) Entre os símbolos \((-)\) existirão \((n-p+1)\) espaços vazios disponíveis, pois o espaço antes do primeiro símbolo \((-)\text{,}\) assim como o espaço depois do último símbolo \((-)\) estão disponíveis, veja a Figura 2.4.4

Figura 2.4.4. Distribuição de símbolos \((-)\) e espaços para os símbolos \((+)\text{.}\)

Desta forma, resta escolher entre os \((n-p+1)\) espaços vazios aqueles que serão ocupados pelos símbolos \((+)\text{.}\) Logo,

\begin{equation*} K(n,p)=C_{n-p+1}^p. \end{equation*}

Tecnologia 2.4.5.

Calculando \(K(8, 4)\) no Sage:

Tecnologia 2.4.6.

Escolha uma lista de letras ou números e \(p\) para obter os subconjuntos da lista com \(p\) elementos, nos quais não há elementos, da lista, consecutivos.

Figura 2.4.7. Todos os subconjuntos com \(p\) elementos.

Exemplo 2.4.8.

Um exame vestibular se constitui de 10 questões distintas, 3 das quais da área de Matemática. Determine de quantas formas é possível programar a sequência das 10 questões, de maneira que duas questões da área de Matemática não se sucedam.

Solução.

São 3 questões de Matemática e 7 questões de outras áreas que serão denotadas por \(Q_1, Q_2,\cdots, Q_7\text{.}\) Inicialmente, iremos dispor as questões que não sofrem restrições:

\begin{equation*} \large\bigcirc \ Q_1\ \bigcirc \ Q_2 \ \bigcirc \ Q_3 \ \bigcirc \ Q_4 \ \bigcirc \ Q_5 \ \bigcirc \ Q_6 \ \bigcirc \ Q_7 \ \bigcirc \end{equation*}

Temos 8 lugares \(\bigcirc\) para colocar as 3 questões de Matemática e o número de formas de calcular isso, pode ser feito utilizando o 1º Lema de Kaplansky:

\begin{equation*} K(10,3) = C_8^3=56. \end{equation*}

Devemos, agora, contar o número de permutações das 3 questões de matemática e o número de permutações das 7 questões das outras áreas:

\begin{equation*} 3! \times 7!=30240. \end{equation*}

Assim, o total de formas de programar a sequência dessas 10 questões, satisfazendo as condições do enunciado é:

\begin{equation*} K(10, 3)\times 7! \times 3! = 56\times30240 = 1693440. \end{equation*}

Subseção 2.4.3 O 2º Lema de Kaplansky

Teorema 2.4.9.

(2º Lema de Kaplansky) O número de subconjuntos com \(p\) elementos de \(\{1,2,3,\cdots,n\}\) nos quais não há números consecutivos e, 1 e \(n\) são consecutivos, é :

\begin{equation*} KC(n,p)=\frac{n}{n-p}\times C_{n-p}^p. \end{equation*}

Demonstração.

O problema será dividido em dois casos:

1º caso: O elemento 1 pertencendo ao subconjunto composto por \(p\) elementos. Neste caso, será feito a análise de quantos formas poderá serão escolhidos os outros \(p-1\) elementos do conjunto \(\{3,4,5,\cdots,n-1\}\text{,}\) pois os elementos 1 e \(n\) não podem pertencer ao conjunto. Dessa forma, utilizando o 1º lema de Kaplansky, o número de maneiras que isso pode ocorrer é:

\begin{equation*} K(n-3,p-1)=C^{p-1}_{n-p-1}=\dfrac{(n-p-1)!}{(n-2p)!\cdot(p-1)!}. \end{equation*}

2º caso: O elemento 1 não pertencendo ao subconjunto composto por \(p\) elementos. Nesse caso a escolha de \(p\) elementos será realizado entre os elementos do conjunto \(\{2,3,4,...n\}\text{.}\) No entanto pelo primeiro lema de Kaplansky a escolha será determinada por

\begin{equation*} K(n-1,p)=C^p_{n-p}=\dfrac{(n-p)!}{(n-2p)!\cdot p!} \end{equation*}

Pelo Princípio Aditivo, somando os resultados do 1º e do 2º caso, a solução do problema será dado por:

\begin{align*} KC(n,p) = \amp ~\dfrac{(n-p-1)!}{(n-2p)!\cdot(p-1)!}+\dfrac{(n-p)!}{(n-2p)!\cdot p!} \\ =\amp ~ \dfrac{p\cdot (n-p-1)!+(n-p)\cdot(n-p-1)!}{{(n-2p)!\cdot p!}} \\ =\amp ~ \dfrac{(n-p-1)!n}{{(n-2p)!\cdot p!}} \\ =\amp ~ \dfrac{n-p}{n-p}\cdot\dfrac{(n-p-1)!n}{(n-2p)!\cdot p!} \\ =\amp ~ \dfrac{n}{n-p}\cdot\dfrac{(n-p)!}{(n-2p)!\cdot p!}. \end{align*}

Finalmente,

\begin{equation*} KC(n,p)=\dfrac{n}{n-p}\cdot C^p_{n-p}. \end{equation*}

Exemplo 2.4.10.

Débora deseja correr 3 vezes por semana durante esse bimestre. De quantas formas ela poderá escolher os dias da corrida, se Débora não deseja correr em dias consecutivos?

Solução.

Nesta questão observa-se que a disposição dos dias da semana geram um sistema cíclico, ou seja, o início de uma semana dá continuação ao fim da semana anterior a ela e assim sucessivamente, como pode ser verificado na figura abaixo:

Desta forma, Débora deve escolher 3 dias entre: domingo, segunda, terça, quarta, quinta, sexta e sábado de maneira que não apareçam dois dias consecutivos. O número de maneiras que Débora pode escolher os 3 dias é:

\begin{equation*} KC(7, 3) = \frac{7}{4}\cdot C_4^3 =7. \end{equation*}

Exemplo 2.4.12.

Dado um decágono, quantos são os triângulos cujos vértices são vértices não consecutivos do decágono?

Solução.

O resultado esperado corresponde a escolha de 3 elementos não consecutivos de um conjunto de 10 elementos (vértices), como eles estão organizados de forma circular, tem-se:

\begin{equation*} KC(10, 3) = \frac{10}{7}\cdot C_7^3 =50. \end{equation*}

Tecnologia 2.4.13.

Calculando \(KC(7, 3)\) no Sage:

Tecnologia 2.4.14. Faça você mesmo.

Escolha uma lista de letras ou números e \(p\) para obter os subconjuntos da lista com \(p\) elementos, nos quais não há elementos, da lista, consecutivos, considerando o primeiro e o último consecutivos.

Figura 2.4.15. Todos os subconjuntos com \(p\) elementos.

Subseção 2.4.4 Generalizações dos Lemas de Kaplansky

Os Lemas de Kaplansky podem ser generalizado, de modo que entre dois elementos escolhidos para o subconjunto, haja pelo menos \(r\) elementos do conjunto não escolhidos. No caso do 1º e do 2º Lemas de Kaplansky o valor de \(r\) é exatamente 1.

Teorema 2.4.16.

(Generalização do 1º Lema de Kaplansky) O número de subconjuntos com \(p\) elementos de \(\{1,2,3,\cdots,n\}\) de modo que entre cada dois elementos escolhidos para o subconjunto haja, no conjunto, pelo menos \(r\) elementos não escolhidos para o subconjunto é:

\begin{equation*} gK(n,p,r)=C_{n-(p-1)r}^p. \end{equation*}

Demonstração.

Representamos com o símbolo \((+)\) os \(p\) elementos que figuram nos subconjuntos e com o símbolo \((-)\) os \(n-p\) elementos que não figuram. Os símbolos \((+)\) e \((-)\) serão organizados de forma que entre dois símbolos \((+)\) haja pelo menos \(r\) símbolos \((-)\) e antes do primeiro símbolo \((+)\text{,}\) assim como depois do último símbolo \((+)\text{,}\) podem figurar qualquer quantidade de símbolos \((-)\text{.}\) Formando uma fila com os símbolos \((+)\) ficamos com \(p+1\) espaços para colocar os símbolos \((-)\text{,}\) veja a Figura 2.4.17.

Figura 2.4.17. Distribuição de símbolos \((+)\) e espaços para os símbolos \((-)\text{.}\)

Observando que a quantidade de símbolos \((-)\) disponíveis é \(n-p\text{,}\) o número de soluções desse problema é exatamente o número de soluções (em números inteiros) da equação:

\begin{equation*} x_1+x_2+\cdots+x_{p+1} = n-p, \end{equation*}

\begin{equation*} \text{ com } x_1\geq 0, x_{p+1}\geq 0 \text{ e } x_2\geq r, \ldots, x_p\geq r. \end{equation*}

Definindo \(x_2 = r+y_2, \ldots, x_p = r+y_p\) e substituindo na equação anterior, ficamos com

\begin{equation*} x_1 + \underbrace{(r+y_2)}_{1º} + \underbrace{(r+y_3)}_{2º} + \cdots + \underbrace{(r+y_p)}_{(p-1)º} + x_{p+1} = n-p. \end{equation*}

Ou seja,

\begin{equation*} x_1 + y_2 + y_3 + \cdots + y_p + x_{p+1} = n-p - (p-1)\times r. \end{equation*}

O número de soluções dessa equação, com cada variável inteira e não negativa é

\begin{equation*} CR_{p+1}^{n-p-(p-1)r}=PR_{n-(p-1)r}^{p, n-p-(p-1)r} = C_{n-(p-1)r}^p. \end{equation*}

Tecnologia 2.4.18.

Calculando \(gK(15, 5, 2)\) no Sage:

Exemplo 2.4.19.

Um estudante precisa realizar quatro provas referentes à recuperação final em 4 disciplinas. A escola deu um prazo 20 dias (incluindo sábados e domingos) para a realização de tais provas. Sabendo que o aluno pode escolher as datas que irá realizar cada prova e que ele deseja fazer uma prova por dia com um intervalo de três dias entre uma prova e outra (ou seja, 3 dias sem fazer provas), para poder estudar, responda: de quantas formas esse aluno pode escolher os dias para a realização das quatro provas?

Solução.

Utilizando a Generalização do 1º Lema de Kaplansky, onde \(n = 20, p = 4\) e \(r = 3\text{,}\) o número de maneiras de escolher os quatro dias para a realização das provas será dado por

\begin{equation*} 4!\times gK(20, 4, 3)= 4!C_{11}^4 = 7920. \end{equation*}

Teorema 2.4.20.

(Generalização do 2º Lema de Kaplansky) O número de subconjuntos com \(p\) elementos de \(\{1,2,3,\cdots,n\}\) onde \(1\) e \(n\) são "adjacentes" e de modo que entre cada dois elementos escolhidos para o subconjunto haja, no conjunto, pelo menos \(r\) elementos não escolhidos para o subconjunto é:

\begin{equation*} gKC(n,p,r)=\frac{n}{n-pr}\cdot C_{n-pr}^p. \end{equation*}

Demonstração.

Vamos separar em dois casos. Observe que um subconjunto satisfazendo as condições do enunciado vai possuir ou não algum dos elementos: \(1, 2, \ldots, r\text{.}\)

1º caso: O número de subconjuntos que não possui quais quer dos elementos supracitados é

\begin{equation*} gK(n-r, p, r), \end{equation*}

pois, restam \(n-r\) elementos, tais que, o primeiro e o último não são adjacentes e os subconjuntos serão formados por \(p\) elementos satisfazendo as mesmas condição da Generalização do 1º Lema de Kaplansky.

2º caso: O número de subconjuntos que possui um dos elementos supracitados é

\begin{equation*} r\cdot gK(n-2r-1, p-1, r), \end{equation*}

para justificar este caso, considere o elemento \(i\in \{1, 2, \ldots, r\}\text{,}\) no subconjunto. O seguinte procedimento deve ser feito:

Como o elemento \(i\) já está no subconjunto, então \(r\) elementos antes do \(i\) e \(r\) elementos depois do \(i\) não podem figurar. Portanto, do total de \(n\) elementos, \(2r+1\) elementos precisam ser subtraidos, restando \(n-2r-1\text{.}\) Agora, \(p-1\) elementos precisam ser escolhidos, satisfazendo as mesmas condição da Generalização do 1º Lema de Kaplansky, ou seja, no total são \(gK(n-2r-1, p-1, r)\) maneiras para cada \(i\) fixado. Como são \(r\) opções para o valor de \(i\text{,}\) ficamos com \(r\) vezes este valor.

Ainda precisamos calcular o valor da seguinte soma:

\begin{equation*} gK(n-r, p, r)+r\cdot gK(n-2r-1, p-1, r). \end{equation*}

Assim,

\begin{align*} gKC(n,p) = \amp ~\dfrac{(n-pr)!}{p!\cdot(n-pr-p)!}+r\cdot\dfrac{(n-pr-1)!}{(p-1)!\cdot (n-pr-p)!} \\ =\amp ~ \dfrac{(n-pr)(n-pr-1)! + p\cdot r\cdot(n-pr-1)!}{p!(n-pr-p)!} \\ =\amp ~ \dfrac{(n-pr+pr)(n-pr-1)!}{{p!\cdot (n-pr-p)!}} \\ =\amp ~ \dfrac{n}{n-pr}\cdot \dfrac{(n-pr)(n-pr-1)!}{p!(n-pr-p)!} \\ =\amp ~ \dfrac{n}{n-pr}\cdot C_{n-pr}^p \end{align*}

Tecnologia 2.4.21.

Calculando \(gKC(15, 5, 2)\) no Sage:

Exemplo 2.4.22.

Diamantino gosta de jogar futebol, mas se jogar dois dias seguidos ele fica com dores musculares. De quantas maneiras Diamantino pode escolher em quais de dez dias seguidos ele vai jogar bola sem ter dores musculares? Uma maneira é não jogar futebol em nenhum dos dias.

Resposta.

144

Solução.

Diamantino pode escolher qualquer valor entre \(0\) e \(5\) inclusive, para ser a quantidade de vezes que ele vai jogar, pois \(K(10, 6)=0\) e \(gK(10, 5)\neq 0\text{.}\)

O número de maneiras de Diamantino escolher os dias que quer jogar futebol, sem ter dores musculares é

\begin{align*} \sum_{i=0}^{5} K(10, i) =\amp~ K(10,0)+K(10,1)+\cdots+K(10,4)+K(10,5) \\ =\amp~1+10+36+56+35+6\\ =\amp~144. \end{align*}

6.

Irving gosta de jogar futebol, mas precisa ficar dois dias consecutivos sem jogar para evitar dores musculares. De quantas maneiras Irving pode escolher em quais de 20 dias seguidos ele vai jogar bola sem ter dores musculares? Uma maneira é não jogar futebol em nenhum dos dias.

Resposta.

2745

Solução.

Irving pode escolher qualquer valor entre \(0\) e \(7\) inclusive, para ser a quantidade de vezes que ele vai jogar, pois \(gK(20, 8, 2)=0\) e \(gK(20, 7, 2)\neq 0\text{.}\)

Assim, o número de formas de Irving jogar futebol sem ter dores musculares é

\begin{align*} \sum_{i=0}^{7}gK(20, i, 2)=\amp~1+20+153+560+1001+792+210+8\\ =\amp~ 2745. \end{align*}

7.

Um determinado atleta quer fazer treinos HIIT para se preparar fisicamente para um campeonato. Sabendo que faltam 28 dias para o campeonato, que ele quer pelo menos 3 dias de intervalo entre dois treinos HIIT e que ele pode escolher 3 tipos desses treinos. De quantas maneiras esse atleta pode escolher fazer os treinos HIIT, se ele quer treinar pelo menos 5 vezes?

Resposta.

\(2574828\)

Solução.

O atleta pode escolher treinar \(5, 6\) ou \(7\) vezes, pois \(gK(28, 8, 3)=0\text{.}\) Em cada dia que ele resolve treinar, ele têm três opções. Portanto a resposta é

\begin{align*} {\small\sum_{k=5}^7 3^k\times gK(28, k, 3)=}\amp~{\small 3^5\times gK(28, 5, 3)+3^6\times gK(28, 6, 3)+3^7\times gK(28, 7, 3)}\\ =\amp~ 3^5\times 4368+3^6\times 1716 + 3^7 \times 120\\ =\amp~2574828. \end{align*}

No Sage o cálculo pode ser feito da seguinte maneira:

8.

Seis pessoas devem se sentar em vinte cadeiras colocadas em torno de uma mesa circular. De quantos modos isso pode ser feito se para cada cadeira ocupada devemos ter duas cadeiras livres de cada lado?

Resposta.

\(50400\)

Solução.

Primeiro, contamos o número de maneiras de escolher as 6 cadeiras que serão usadas, dentre as 20 disponíveis em disposição circular. Depois, contanos a quantidade de maneiras de ordenas as 6 pessoas que irão sentar nas cadeiras. Isto pode ser feito de

\begin{equation*} gKC(20, 6, 2)\times P_6 = 50400 \end{equation*}

maneiras.

Anterior Top Próximo