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.