Lemas de Kaplansky

Prévia do material em texto

Lemas de Kaplansky
Segundo Lema de Kaplansky
O Segundo Lema de Kaplansky diz que o 
número de subconjuntos com p elementos do 
conjunto {1, 2, 3, …, n}, em que 1 e n são 
considerados consecutivos, é igual a:
Exemplo: O professor Marcos decidiu praticar 
Crossfit 3 vezes por semana. De quantas 
maneiras Paulo pode escolher os dias de 
treino, se ele não quer praticar Crossfit em dias 
consecutivos?
Como a atividade será feita periodicamente, sábado e domingo 
(último dia e primeiro dia da semana) são consecutivos.
Vamos considerar que Domingo = 1, Segunda-feira = 2, …, 
Sábado = 7. Assim, temos o conjunto {1, 2, 3, 4, 5, 6, 7}.
Na situação, 1 e 7 são consecutivos. Paulo precisa escolher 3 
números não consecutivos. Pelo Segundo Lema de Kaplansky, 
isso pode ser feito de:
O segundo lema de Kaplansky é, na verdade, o primeiro lema 
aplicado duas vezes.
Raciocinando sem usar a fórmula:
• Vamos separar em dois casos: o elemento 1 foi escolhido e 
o elemento 1 não foi escolhido.
• Subconjuntos nos quais figura o elemento 1.
• Se o elemento 1 foi escolhido, não podemos escolher os 
elementos 2 e 7, porque são elementos vizinhos ao número 
1. Assim, devemos escolher 2 elementos não consecutivos 
no conjunto {3, 4, 5, 6}.
Aplicando o primeiro lema de Kaplansky.
Para escolher 2 elementos dentre os 4, devemos ter 
dois sinais “–“ e dois sinais “+”. Os sinais “+” não podem 
ficar juntos porque os números escolhidos não são 
consecutivos. Começamos fixando os sinais de “–“.
Assim, temos 3 espaços vazios e devemos escolher 
2 deles para colocar os sinais de “+”. Isso pode ser 
feito de
*Subconjuntos nos quais não figura o elemento 1.
Nesse caso, precisamos escolher 3 elementos não 
consecutivos no conjunto {2, 3, 4, 5, 6, 7}. Vamos aplicar 
novamente o primeiro lema de Kaplansky.
Para escolher 3 elementos dentre os 6, devemos ter três sinais 
“–“ e três sinais “+”. Os sinais “+” não podem ficar juntos porque 
os números não são consecutivos. Começamos fixando os 
sinais de “–“.
Assim, temos 4 espaços vazios e devemos escolher 3 deles 
para colocar os sinais de “+”. Isso pode ser feito de:
O total de maneiras é 3 + 4 = 7 maneiras.
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?