Mathematics">
O Problema de Lucas
O Problema de Lucas
O Problema de Lucas
O PROBLEMA DE LUCAS
Luiz Gustavo Martins dos Santos
Belo Horizonte
2011
Luiz Gustavo Martins dos Santos
O PROBLEMA DE LUCAS
Belo Horizonte
2011
2
Agradecimentos
À minha família, minha mãe Maria, meu pai Luiz e minha irmã Aline, obrigado por
todo apoio a mim dispensado.
3
Índice
Introdução ........................................................................................................ 05
4
Introdução
5
O texto termina com algumas considerações finais nas quais fazemos um breve
resumo das questões mais importantes abordadas neste trabalho, relatando a
importância deste para o aprendizado e ensino de combinatória.
6
1. O Princípio da Inclusão e Exclusão e algumas aplicações
Exemplo 1.1.1 Numa pesquisa com jovens, foram feitas as seguintes perguntas
para que respondessem sim ou não: Gosta de música? Gosta de esportes?
Responderam sim à primeira pergunta jovens; responderam sim à segunda;
responderam sim a ambas. Supondo que todos eles tenham respondido sim a
pelo menos uma das opções, quantos jovens foram entrevistados?
Solução:
: conjunto dos que gostam de música. Sua cardinalidade será dada por:
Desta forma,
.
7
Teorema 1.1.2 (Princípio da Inclusão e Exclusão): O número de elementos na
união de conjuntos finitos é dado por:
.
.
.
1
O número de maneiras de escolher elementos de um conjunto com elementos será aqui denotado por
8
Queremos provar que a soma acima é igual a um. Para tanto vamos demonstrar
primeiramente a seguinte igualdade:
Desta forma,
Definimos:
o conjunto de todos os anagramas da palavra PERDÃO tendo o P como a
primeira letra.
o conjunto de todos os anagramas da palavra PERDÃO tendo o R como a
segunda letra.
o conjunto de todos os anagramas da palavra PERDÃO tendo o D como a
sexta letra.
2
Em geral, o Binômio de Newton é escrito da seguinte forma: .
9
.
= = 5! =120.
Exemplo 1.1.4 Suponha que n cavalheiros foram a uma festa e deixaram seus
chapéus com o porteiro. Como o porteiro estava muito distraído, trocou alguns
chapéus de lugar.
10
a) Estratégia: Definir conjuntos apropriados e aplicar o Princípio da Inclusão e
Exclusão para determinar o número de elementos da união.
Solução:
Sejam o conjunto de todas as permutações em que o chapéu do primeiro
cavalheiro esteja na posição correta e o conjunto de todas as permutações onde
o chapéu do segundo cavalheiro esteja na posição correta.
Assim temos:
Desta forma:
Solução:
O total de maneiras em que os chapéus estão dispostos é dado por assim a
solução procurada será:
11
complementar da união. O item b acima é um exemplo de problema no qual
podemos utilizar a forma alternativa do Princípio da Inclusão e Exclusão que
discutiremos a seguir.
12
Exemplo 1.2.2 Dado um número inteiro e sendo números menores ou
iguais a e primos entre si, encontrar a quantidade de inteiros positivos menores ou
iguais a que não são divisíveis por nenhum dos números .
Estratégia: Dos números inteiros de até vamos retirar todos aqueles que são
divisíveis por e assim teremos todos aqueles que não são
divisíveis por nenhum destes números.
Definimos:
é divisível por
é divisível por
é divisível por
.
.
.
é divisível por
.
.
.
.
13
Sendo assim:
Estratégia: Pelo que foi mencionado acima temos que os números compostos não
excedentes a 100 devem ter um fator primo não excedente a 10. Desta forma,
precisamos encontrar a quantidade de números inteiros positivos menores ou iguais
a 100 e que não são divisíveis por nenhum dos primos e somar três a está
quantidade (uma vez que o número 1 não é primo e também são primos).
Solução:
Pelo exemplo anterior, a quantidade de números que inteiros positivos menores
ou iguais a 100 e que não são divisíveis por nenhum dos primos :
14
Erastóstenes criado pelo matemático grego de mesmo nome. O algoritmo consiste
em listar todos os números naturais de até , em seguida eliminam-se todos os
inteiros compostos que são múltiplos dos primos tais que . Assim os
números que sobrarem na lista são todos os primos entre e . Pelo exemplo
acima, se desenvolvermos este algoritmo, teremos números primos os quais
aparecem destacados na tabela abaixo.
15
Denotando por o número de permutações caóticas a serem calculadas,
temos:
Claramente,
, para
, para
, para
= .
E, como existem,
.
.
.
concluímos
Fazendo as simplificações,
16
Finalmente colocando em evidência obtemos que o número de permutações
caóticas de elementos é dado por
Solução:
Devemos determinar o número de permutações de quatro objetos onde nenhum
deles ocupe a posição original.
Assim:
17
0125 2015 5012
0512 2105 5021
0521 2501 5102
Exemplo 1.3.3 Uma professora distribui nove livros diferentes para nove crianças.
Um mês depois recolhe os livros e, novamente, distribui um livro para cada criança.
De quantas maneiras os livros podem ser distribuídos de modo que somente três
crianças recebam o mesmo livro desta vez?
Solução:
maneiras para escolher os alunos que vão ficar com o mesmo livro.
18
2. Os Lemas de Kaplansky
Solução:
Neste problema podemos ter apenas subconjuntos de dois algarismos não
consecutivos. Como o exemplo tem poucas possibilidades podemos enumerar os
casos:
Assim
Entretanto, desejamos uma solução combinatória para este caso. Para isto,
vamos marcar com o sinal os elementos que farão parte do subconjunto e com o
sinal os números que não estarão no subconjunto em questão. Podemos assim
representar cada subconjunto de dois elementos como uma sequência de cinco
símbolos sendo . No nosso exemplo teremos as seguintes sequências:
19
O nosso objetivo é escolher dois números não consecutivos que constituirão o
subconjunto, então, na notação de sequência os sinais correspondem a estes
números. Desta forma, basta fixar os sinais e colocar entre eles ou após os
mesmos os dois sinais de . Nesta configuração existem quatro posições entre os
sinais onde os sinais podem ser colocados:
Portanto,
20
Exemplo 2.1.3 João e Maria vão sentar-se na mesma fila de cinema. A fila tem
cadeiras, todas vazias. Como não querem sentar-se em cadeiras vizinhas, de
quantas maneiras poderão sentar-se?
Solução:
Exemplo 2.1.4 (OBM 2010) 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.
Solução:
Note que Diamantino pode jogar futebol no máximo 5 vezes; caso contrário ele
necessariamente joga dois dias seguidos. Vamos supor que Diamantino joga futebol
em dias. Então os dias em que ele joga devem ser imediatamente seguidos por
dias em que ele não joga. Desta forma basta de um conjunto de dez dias possíveis
formar subconjunto de elementos não consecutivos, ou seja:
21
Como Diamantino pode jogar no máximo apenas 5 vezes temos que .
Assim teremos as seguintes possibilidades:
Demonstração:
Suponhamos agora que os elementos de estejam arrumados em um
círculo como mostra a figura abaixo:
22
Estratégia: A quantidade total de subconjuntos será a soma da quantidade de
subconjuntos nos quais o ‘1’ figura somada com a quantidade de subconjuntos nos
quais o ‘1’ não figura.
Caso 1: Subconjuntos nos quais o elemento ‘1’ figura. Para fazê-lo, devemos
escolher elementos em (pois o 1 já está presente e o ‘2’ e o ‘n’
não podem ser escolhidos pois são consecutivos de ), portanto, pelo Primeiro Lema
de Kaplansky, o número de modos que isso pode ser feito é
Caso 2: Subconjuntos nos quais o ‘1’ não figura. Para fazê-lo devemos escolher
elementos de não podendo ser escolhidos elementos consecutivos. Pelo
Primeiro Lema de Kaplansky, o número de maneiras que isto pode ser feito é
Assim
23
Exemplo 2.2.2 João pretende jogar futebol três vezes por semana, mas para
melhorar seu desempenho ele não pretende praticar o esporte em dias
consecutivos. De quantas maneiras João pode escolher os dias de aula, sendo
sábado e domingo considerados dias consecutivos?
Solução:
Exemplo 2.2.3 Pedro levou alunos para uma excursão. Na hora do lanche os
alunos devem se sentar em uma mesa circular contendo cadeiras. De quantos
modos isso pode ser feito de modo que não haja ocupação simultânea de duas
cadeiras vizinhas?
Solução:
24
3. Resolvendo o Problema de Lucas
25
Nota-se, que tanto na primeira linha como na segunda, qualquer uma das três
figuras pode ser obtida a partir da outra por uma simples rotação. Contudo nenhuma
das três primeiras podem ser obtidas, por rotação, a partir de nenhuma das três
últimas, logo existem apenas duas permutações circulares de três objetos. Observe
que nas três primeiras figuras considerando o sentido horário, precede o que
precede o que procede o . Nas outras três figuras temos que precede o que
precede o que procede o Assim podemos dizer que nas permutações circulares
o que importa é apenas a posição relativa dos objetos entre si.
Demonstração Como foi visto no exemplo acima o que importa é a posição relativa
dos objetos, se dispomos de objetos para colocá-los em torno de um círculo em
exatamente lugares, temos que:
Exemplo 3.2.1 De quantos modos 3 casais podem se sentar ao redor de uma mesa
circular de tal forma que o marido e a mulher não fiquem juntos?
26
Estratégia: Vamos contar todas as possibilidades na qual podemos permutar as seis
pessoas em um círculo, e utilizando a Forma Alternativa para o Princípio da Inclusão
e Exclusão, vamos excluir todas aquelas permutações onde exista algum dos casais
juntos.
Solução:
27
Finalmente consideramos, para as 2! permutações dos
componentes do casal entre si. Desta forma:
dos demais casais. Note que isto pode ser feito de maneiras.
28
Finalmente consideramos as possíveis permutações de cada um dos componentes
do casal entre si, para Desta forma:
Exemplo 3.2.3 De quantos modos casais podem se sentar ao redor de uma mesa
circular de tal forma que o marido e a mulher não fiquem juntos?
Solução:
para
29
3.3 Problema de Lucas
Solução:
Vamos numerar os lugares de até :
Como pessoas do mesmo sexo não podem se sentar juntas devemos colocar as
mulheres nas posições pares e os homens nas posições ímpares ou vice versa.
Desta forma podemos seguir a seguinte sequência:
Escolhe-se a posição par ou ímpar para os homens, isso será feito de modos.
Uma vez determinado a posição para cada sexo devemos colocar os homens nos
lugares a eles reservados, isso será feito de modos.
Basta agora colocar as mulheres nos lugares restantes com a restrição de que
nenhuma delas se sente ao lado do seu marido. Vamos denotar como o número
de maneiras de colocar mulheres nos lugares vazios, não permitindo a
colocação de nenhuma mulher ao lado de seu marido.
30
Para obtermos , consideramos os espaços vazios e os homens
com a seguinte notação:
32
Precisamos agora obter a cardinalidade da interseção dos conjuntos envolvidos
(tomados dois a dois, três a três,...). Para facilitar o entendimento, vamos discriminar
os conjuntos e para na seguinte tabela:
Como a mesma mulher não pode ocupar duas posições diferentes ao mesmo
tempo, então:
Note que se dois conjuntos não são consecutivos, então teremos em sua
interseção dois elementos fixos e assim a cardinalidade de sua interseção será
Em outras palavras, temos que:
33
Observe que a quantidade dos conjuntos listados acima poderia ter sido
calculada pelo Segundo Lema de Kaplansky, já que consiste na quantidade de 2-
subconjuntos de (estabelecendo a bijeção
nos quais não há números consecutivos (considerando e
como consecutivos
interseções
.
34
Finalmente, se consideramos as interseções de mais que três conjuntos
escolhidos dentre , então teremos obviamente que a
cardinalidade da interseção é nula, já que teremos necessariamente pelo menos
dois conjuntos consecutivos. Portanto, utilizando a Forma Alternativa do Princípio da
Inclusão e Exclusão, temos:
é a única permutação em que cada mulher não está sentada junto com seu marido.
Assim temos:
35
já que a cardinalidade de cada um destes conjuntos é o número de permutações de
elementos tendo um deles fixo.
Desta forma,
De maneira análoga ao exemplo anterior, uma vez que precisamos agora obter a
cardinalidade da interseção dos conjuntos envolvidos (tomados dois a dois, três a
três,...), vamos montar uma tabela relacionando os conjuntos e para ,
a mulher cuja posição está definida e sua respectiva posição.
. . .
. . .
. . .
36
dentre (considerando também e consecutivos) é
sempre vazia, pois:
A mesma mulher não pode ocupar duas posições diferentes ao mesmo tempo
e assim:
37
Utilizando a Forma Alternativa do Princípio da Inclusão e Exclusão temos:
E assim:
Para :
Para
Para :
38
Note que o resultado já era esperado, uma vez que ao exigir que pessoas do mesmo
sexo não se sentem juntas, teremos necessariamente que o marido estará ao lado
de sua esposa.
Vamos então aplicar o resultado para . Como vimos e assim a
resposta para o problema de Lucas será:
39
Considerações finais
40
Referências Bibliográficas
[1] ENEM 2009 faça download da prova. Educação. Brasília, 29 de Agosto de 1999.
Disponível em: http://portal.inep.gov.br. Acesso em 23/10/2011.
[4] ROSEN, Kenneth H. Matemática discreta e suas aplicações. Sexta edição. São
Paulo: Mc-Graw-Hill, 2009.
[5] SANTOS, José Plínio Oliveira; MELLO, Margarida P.; MURARI, Idani T. C..
Introdução à Análise Combinatória. Rio de Janeiro: Editora Ciência Moderna Ltda.
2007.
[6] VIDIGAL, Ângela; AVRITZER, Dan; SOARES, Eliana Farias; BUENO, Hamilton
Prado; FERREIRA, Maria Cristina Costa; FARIA, Marília Costa. Fundamentos de
Álgebra, 1ª edição atualizada. Editora UFMG, 2009.
41