Matemática
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:
- 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.
- 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.
- 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.
-
Um Problema, Várias Soluções (continuação)
Nesta postagem apresentarei as três soluções prometidas para o problema proposto na postagem um problema, várias soluções. Além disso, acrescentarei a elas as soluções dos dois leitores que participaram com comentários, as quais enriqueceram...
-
Arranjo Simples
A Fórmula do Arranjo Simples em combinatória, denotado por An,k, onde arranjamos k objetos de n objetos dados, é uma fórmula muito importante dada por: É muito útil na solução de problemas de contagem onde a ordem é levada em consideração....
-
Combinações
Professor de Matemática e Biologia Antônio Carlos Carneiro BarrosoColégio Estadual Dinah Gonçalvesemail
[email protected] www.ensinodematemtica.blogspot.com.brwww.accbarrosogestar.blogspot.com.br WWW.profantoniocarneiro.com Quando...
-
Combinações
Professor de Matemática Antonio Carlos Carneiro BarrosoColégio Estadual Dinah Gonçalvesemail
[email protected] HTTP://ensinodematemtica.blogspot.comhttp://accbarrosogestar.blogspot.com.br WWW.profantoniocarneiro.comQuando formamos...
-
Combinações
Professor de Matemática e Biologia Antônio Carlos Carneiro BarrosoColégio Estadual Dinah Gonçalvesemail
[email protected] www.ensinodematemtica.blogspot.com.brwww.accbarrosogestar.blogspot.com.br WWW.profantoniocarneiro.com ...
Matemática