Os Lemas de Kaplansky

Olá pessoal, hoje estamos escrevendo sobre os lemas de Kaplansky.

Suponha que você se depare com o seguinte problema:

1- De quantas formas pode-se escolher subconjuntos de 3 elementos do conjunto {1,2,3,4,5,6,7} sendo que não pode haver números consecutivos?


 Para resolver o problema vamos associar cada possível escolha a uma sequência.

O subconjunto {1,4,6} será associado à sequência + - - + - + -
O subconjunto {1,3,7} será associado à sequência + - + - - - +

Observe que a sequência é construída da seguinte forma:

  • Se n pertence ao subconjunto escolhido, então o n-ésimo termo dessa sequência é um sinal "+"
  • Se n não pertence ao subconjunto escolhido, então o n-ésimo termo dessa sequência é um sinal "-" 
Assim, cada subconjunto possível está associado à uma sequência de 7 sinais, sendo 3  de "+" e 4 de "-" onde entre dois sinais de "+" há pelo menos 1 sinal de "-".

Observe que essa associação é uma bijeção pois cada sequência é associada a um único subconjunto e, cada subconjunto, a uma única sequência.Logo, contar o número de subconjuntos possíveis é o mesmo que contar o número de sequências possíveis.

Dessa forma o problema passou a ser: Quantas sequências contendo 3 sinais"+ e 4 sinais "-"existem se não há 2 sinais "+" consecutivos?

Primeiramente posicione os sinais de "+". Temos: +   +   +

Chame de o número de sinais de "-" que vem antes do 1º sinal de "+"

Chame de o número de sinais de "-" que vem entre o 1º e o 2º sinal de "+"

Chame de o número de sinais de "-" que vem entre o 2º e o 3º sinal de "+"

Chame de o número de sinais de "-" que vem depois do 3º sinal de "+"

 O problema, então, passa a ser: Quantas são as soluções   com e   (não pode haver sinais de "+" consecutivos). Para resolver, faça  e . Assim, temos  onde .

Para resolver esse problema, usamos a fórmula de combinação com repetição, obtida com uma bijeção simples (para ler mais sobre bijeções, clique aqui)

O número de soluções é, então, .
 
O caso geral desse tipo de problema é:

 De quantas formas pode-se escolher subconjuntos de k elementos do conjunto {1,2,3,4,...,(n-1),n} sendo que não pode haver números consecutivos?

Nesse caso, prosseguimos da mesma forma.

Associamos cada escolha a uma sequência de n sinais sendo k sinais "+" e (n-k) sinais "-" de forma que:


  • Se n pertence ao subconjunto escolhido, então o n-ésimo termo dessa sequência é um sinal "+"
  • Se n não pertence ao subconjunto escolhido, então o n-ésimo termo dessa sequência é um sinal "-" 

Se não podemos ter 2 números consecutivos no subconjunto, então não podemos ter 2 sinais "+" consecutivos.

Assim, contar o número de subconjuntos possíveis é o mesmo que contar o número de sequências possíveis.

Para isso, coloque os n sinais "+" em uma fila.

Chame de  o número de sinais "-" que vem antes do 1º sinal "+"

Chame de  o número de sinais "-" que vem entre o 1º e o 2º sinal "+"

Chame de  o número de sinais "-" que vem entre o 2º e o 3º sinal "+"

...

Chame de  o número de sinais "-" que vem entre o (n-1)-ésimo e o n-ésimo sinal "+"

Chame de  o número de sinais "-" que vem depois do n-ésimo sinal "+"

Assim, temos:

onde e  .
Resolvemos da mesma forma que antes.
Com  onde

Assim,  então

.
Logo,  
e por isso .

Nesse ponto devo chamar atenção para o fato de que devemos ter .

Assim suponha que lhe seja perguntado o seguinte: "De quantas formas podemos escolher um subconjunto de 10 elementos do conjunto {1,2,3,...,15} sem que sejam escolhidos dois números consecutivos?"

Nesse caso n=15 e k = 10, assim, n+1-2k= 15+1-20 = -4 . Como deve ser maior ou igual a 0, então não há nenhuma escolha possível que satisfaça o que foi pedido.

Voltando à questão...

Para saber o número de soluções de
 com 
Já sabemos como fazer. A resposta é, portanto, .


UM APELO DE UM AUTOR QUE PREZA PELA CRIATIVIDADE:

Bem... Eu tinha um professor que dizia que a matemática é feita de 3 etapas: Aprendeu, decorou e treinou.
É um jeito muito bom para quem só quer passar de ano na escola, mas para aprender matemática de verdade, deve-se focar na ideia. Por isso, cortem a parte do "decorou" e substituam por "entendeu a ideia". Se reparar bem, o que fizemos aqui nada mais é do que uma bijeção simples. Não vale a pena perder tempo decorando a fórmula geral, preocupe-se em entender o caminho que usamos para resolver o problema.

Esse foi o primeiro lema, vamos para o segundo...


2- Uma pessoa deseja escolher 3 dias da semana para ir à academia. De quantas formas ela pode montar o seu horário se ela não pode ir em 2 dias consecutivos?

Observe que como Sábado e Domingo são dias consecutivos não há um início nem um fim da semana. Assim, a fórmula anterior não se aplica a esse problema.

A ideia, porém, é bem parecida.

Vamos abrir em 2 casos:

I- A pessoa vai à academia na Quarta. Nesse caso, ela não pode ir nem na Terça nem na Quinta, mas pode ir Segunda e Sexta. Assim, devemos escolher mais dois dias, de Sexta à Segunda, de forma que não sejam escolhidos dois dias consecutivos. Observe que isso é um problema a ser resolvido com o primeiro lema.

Eu sei que eu tinha dito para não decorar fórmulas, mas aproveitando que eu deduzi uma fórmula geral logo acima (verás que com o tempo resolverá problemas desse tipo de cabeça) temos que escolher 2 dias dentre 4 sem que hajam 2 dias consecutivos. Logo, n= 4 e k=2.

Nesse caso, há  formas de fazer essa escolha.

II- A pessoa NÃO vai à academia na Quarta. Nesse caso, ela pode ir na Terça e na Quinta. Assim, devemos escolher 3 dias, de Quinta à Terça, de forma que não sejam escolhidos dois dias consecutivos. Observe que isso é também um problema a ser resolvido com o primeiro lema.

Nesse caso, n= 6 e k =3

Assim, há  formas de fazer essa escolha.

Assim, há 4+3 = 7 formas de escolher esses 3 dias da semana para ir à academia seguindo essa regra.

O caso geral desse tipo de problema pode ser enunciado assim:

De quantas formas pode-se escolher subconjuntos de k elementos do conjunto {1,2,3,4,...,(n-1),n} sendo que não pode haver números consecutivos e dado que n e 1 são considerados números "consecutivos"?

Para a solução geral prosseguimos como no exemplo acima...

Separamo em 2 casos:

I- O elemento 1 é escolhido. Nesse caso, 2 e n não podem mais serem escolhidos, mas 3 e (n-1) podem. Assim, devemos escolher mais um subconjunto de (k-1) elementos do conjunto {3, 4, 5,..., (n-2), (n-1). Note que isso é um problema a ser resolvido com o primeiro lema de Kaplansky.

Nesse caso N= (n-3) e K= (k-1).

Logo, há  formas de fazer essa escolha

II - O elemento 1 NÃO é escolhido. Nesse caso, 2 e n podem ser escolhidos. Assim, devemos escolher um subconjunto de k elementos do conjunto {2, 3, 4, ... , (n-1), n}. Note que isso é, também, um problema a ser resolvido com o primeiro lema de Kaplansky.

Nesse caso N= (n-1) e K = k.

Logo, há  formas de fazer essa escolha.

Logo, no total há  formas de fazer a escolha desejada.

Arrumando a fórmula temos:










Novamente, fiz o caso geral apenas para passar a ideia por trás desse lema. Esse segundo lema nada mais é do que aplicar o primeiro 2 vezes. Assim, também não recomendo que decorem a fórmula desse segundo lema.

Bem, por hoje fico por aqui. Se você gostou do blog curta nossa página no facebook e se inscreva por e-mail para receber nossas atualizações. Não se esqueça de avaliar a postagem logo abaixo, ajuda a monitorar a qualidade do que escrevemos. Sinta-se livre para comentar. Deixarei alguns exercícios. Os primeiros são bem repetitivos, para fixar a ideia, e os últimos mais elaborados.

Até mais.

1- De quantas formas podemos escolher um subconjunto de 4 elementos do conjunto {1,2,3,4, ... , 10} se nesse subconjunto não pode haver 2 números consecutivos.

2- Uma pessoa quer ir à academia 2 vezes por semana. Essa academia fica aberta de Segundo a Sábado. Ela pode malhar no período da manha e da tarde, mas não pode malhar em dois turnos consecutivos (se for à academia, por exemplo, na Segunda a tarde, não pode ir Terça de manha, mas pode ir Terça a tarde). De quantas formas ela pode montar o seu horário?

3- Um lado de uma rua possui 20 casas. Um ladrão planeja invadir 5 delas, mas não quer invadir duas casas vizinhas. De quantas formas ele pode escolher essas 5 casas?

4- De quantas formas podemos escolher um subconjunto de 8 elementos do conjunto {1, 2, 3, ... , 24, 25} se não pode haver 2 elementos consecutivos (consideramos nesse caso 25 e 1 como "números consecutivos")

5- (IME - 1986) 12 cavaleiros estão sentados em torno de uma mesa redonda. Cada um dos 12 cavaleiros considera seus dois vizinhos como rivais. Deseja-se formar um grupo de 5 cavaleiros para libertar uma princesa, nesse grupo não poderá haver cavaleiros rivais. Determine de quantas maneiras é possível escolher esse grupo.

6- De quantas formas podemos escolher um subconjunto de k elementos do conjunto {1,2,3,..., (n-1), n} de forma que a diferença entre quaisquer 2 elementos desse subconjunto seja sempre maior ou igual a 3? (Nesse caso, 1 e 3 , por exemplo, não podem estar no mesmo subconjunto, mas 1 e 4, 1 e 5 ... podem)

Desafio: Tente deduzir uma fórmula geral para o seguinte problema "De quantas formas podemos escolher um subconjunto de k elementos do conjunto {1,2,3,..., (n-1), n} de forma que a diferença entre quaisquer 2 elementos desse subconjunto seja sempre maior ou igual a x?"

7- 20 crianças estão formando uma roda de ciranda. Deseja-se distribuir doces para somente 5 das crianças sendo que entre 2 crianças que ganharam doce deve haver pelo menos 2 que não ganharam.

8- Temos 110 pessoas em fila, desejamos escolher 10 pessoas da seguinte forma:


  • Entre a primeira e a segunda pessoa escolhida deve haver 1 pessoa
  • Entre a segunda e a terceira pessoa escolhida deve haver 2 pessoas
  • Entre a terceira e a quarta, 3 pessoas
  • ...
  • Entre a nona e a décima, 9 pessoas.
De quantas formas essa escolha pode ser feita? 

Dicas

1 - Esse é um caso de aplicação direta do primeiro lema aproveitando que eu já deixei a fórmula nesse post... (tente faze-lo como se vc não soubesse a fórmula)
R : 


2- Se montarmos o conjunto {Seg M, Seg T, Ter M, Ter T, ... , Sab M, Sab T} vemos que esse é também um caso de aplicação direta do primeiro lema, com n = 12 e k = 2. 
R: 

3- As casas estão num mesmo lado da rua, então estão numa fila temos o conjunto {casa1, casa2, ... , casa 20}. Novamente, outro caso de aplicação direta do primeiro lema. com n = 20 e k = 5

R: 

4- Esse é um caso de aplicação direta do segundo lema. Aproveitando que também já deixei a fórmula geral aqui, temos: n= 25 e k = 8

R: 

5- Esse é também um caso de aplicação direta do segundo lema. Temos n= 12 e k = 5

R: 

6- Nesse caso, faça como no caso geral do primeiro lema. Sendo o número de sinais "menos" entre o (i-1)-ésimo e o i-ésimo sinal "+" então. Daí resolve tudo de forma análoga a feita anteriormente.

R: 

A resolução do desafio é análoga com atenção a um detalhe importante se a diferença entre quaisquer 2 elementos é maior ou igual a x, então entre 2 elementos escolhidos deve haver pelo menos x-1 não escolhidos.
Resposta do desafio:


7- Temos o conjunto das crianças na roda nessa ordem .

Divida em 3 casos:

  1.  recebe um doce. Nesse caso,  e  não podem receber, mas podem. Nessa situação o problema fica igual ao 6º problema com k=4 e n= 15.
  2.  não recebe doce, mas recebe. Nesse caso, e não podem receber, mas  podem. Assim, o problema fica análogo ao 6º com k = 4 e n= 15.
  3. Nem  nem recebem doce. Nesse caso,  podem receber. Assim, o problema fica análogo ao 6º com k = 5 e n=18.
Daí é só aplicar a fórmula que já foi encontrada no 6º problema pra cada caso e somar tudo.

8- Faça de forma análoga a como foi resolvido o 6º exercício. Sendo o número de sinais "menos" entre o (i-1)-ésimo e o i-ésimo sinal "+" então . E resolva de forma análoga a feita antes. 

Comentários

  1. Faz muito tempo que eu não via alguém abordar esse tema de um modo bastante simples e objetivo, parabéns, realmente as idéias desenvolvidas aqui são mais importantes do que decorar várias fórmulas, aliás, é assim que a Matemática é feita de idéias originais.

    ResponderExcluir
    Respostas
    1. Olá Diego. Muito obrigado pelo elogio. É dessa forma que tentamos ensinar aqui no blog.

      Abraços, Eduardo.

      Excluir
  2. Excelente conteúdo, fico feliz de ter encontrado esse site maravilhoso.

    ResponderExcluir
  3. Nossa, gostei muito dessa postagem. Isso aí poderia ser um artigo da RPM. Muito didático e o melhor, com problemas para exercitar depois. Parabéns!

    ResponderExcluir

Postar um comentário

Você pode comentar! A equipe do blog encoraja todos a comentar.

Porém, lembre-se que comentários que desrespeitem as regras abaixo serão excluídos:

-É proibido ofender qualquer pessoa ou grupo em seu comentário.
-Os comentários deverão ser minimamente relacionados com o tópico. Lembrem-se, estamos falando de um blog de matemática!
-Proibido flood.
-Proibido palavras de baixo calão.
-Proibido colocar qualquer tipo de conteúdo improprio para menores de 18 anos (há menores de idade que acessam o blog).

A equipe do blog agradece seu comentário, e tenha certeza que será muito enriquecedor. Tentaremos respondê-los o quanto antes possível.