No livro "A música dos Números Primos" (The Music Of The
Primes)Marcus Du Sautoy trata, usando linguagem narrativa, de uma das questões
mais investigadas da História da Matemática que vem desde meados do século XIX
ocupando as mentes ambiciosas e dando muito trabalho aos matemáticos de todas
as partes do planeta: A Hipótese de Riemann “é
possível uma harmonia entre esses números primos, à semelhança da harmonia
musical”, problema número 8 da lista contendo 23 problemas matemáticos propostos
pelo alemão David Hilbert (1862-1943) na Conferência Internacional de Matemáticos de Paris
em 1900 para anunciar o novo século.
A Música dos Números Primos é composto por 12 capítulos fascinantes
que vislumbram o universo dos Números Primos desde os dias de Euclides passando
pelos universos, através do espelho, de Euler, Gauss e Riemann, pelos desafios
de Hilbert, pela rigidez de Landau, pelas limitações do método matemático de Gödel,
pela mente milagrosa de Turing; até chegar a dificílima tarefa de implementar
um sistema eficiente que através da criptografia dê segurança ao mundo dos
negócios.
No capítulo 10 Decifrando Números
e Códigos, Du Sautoy aborda os conceitos matemáticos - introduzidos por Pierre
de Fermat (1601 - 1665) e por Carl Friedrich Gauss(1777 – 1855) - por trás da
criptografia utilizada atualmente em larga escala para proteger as vidas de
espiões como também o mundo público dos negócios. Aborda, também, o surgimento
da criptografia na internet inspirado pelo artigo “Novos Caminhos na Criptografia”, escrito pelos matemáticos Whit
Diffie e Martin Hellman ambos da Universidade de Stanford que motivou Ron
Rivest, cientista da computação do Instituto de Tecnologia de Massachusets –
MIT – a desenvolver, juntamente com os matemáticos Adi Shamir (israelense
visitante do MIT) e Leonard Adleman, também do MIT, sistemas de segurança com
intenção de despertar o interesse das grandes empresas.
No entanto, não foi muito fácil
ver o sonho de Diffie e Hellman realizado, pois havia um grande problema na
época, nos anos 1970, que era a fatoração de números de ordem muito grande,
isto é, por exemplo, desde o início da década de 1990, a técnica usada para se
proteger o número de um cartão de crédito durante uma compra pela internet
consiste em multiplicar dois números, com cerca de 60 algarismos, e encontrar
um terceiro número de até 120 algarismos. O interessante nisso é que os números
menores (que são dois números primos) são mantidos em segredo, sendo revelado
somente o número maior de difícil decomposição. Fatorar números muito grandes
não é tarefa trivial.
A maioria dos matemáticos não se interessava
pelo tema, pois o achavam de menor importância. À medida que o trio - Rivest, Shamir,
Adleman - se tornava comercialmente importante outros matemáticos começaram a
aceitar o desafio de decompor números cada vez maiores. O matemático Carl
Pomerance da Universidade da Georgia era fascinado, desde menino, por
decomposição de números e desenvolveu um método chamado de crivo quadrático
semelhante ao crivo de Erastótenes. O crivo quadrático foi utilíssimo no início
dos anos 1990. Com a chegada da internet os matemáticos Arjen Lenstra e Mark
Manasse perceberam que a internet aliada ao crivo quadrático seria a dupla
perfeita para derrubar o RSA 129 (número com 129 algarismos), que foi o desafio
proposto por Rivest, Shamir e Adleman, publicado no artigo de Martin Gardner da
Scientific American. Eis que em abril de 1994, Lenstra e Manasse anunciaram que
o RSA 129 havia sido derrubado utilizando-se centenas de computadores pessoais
ao longo de 24 países. Nisso consistia a beleza do crivo quadrático de
Pomerange, dividi a carga de trabalho, a procura de números primos, entre
muitos e diferentes computadores.
A diferença entre fazer compras pela
internet usando um computador pessoal veloz e com muita memória ou um telefone
celular ou um palmtop é justamente a potência entre o PC e o aparelho de
celular ou palmtop, pois estes últimos não são projetados para realizar grandes
cálculos. Uma vez que proteger um cartão de crédito, no momento de uma compra, é
necessário realizar cálculos com números muito grandes (multiplicar dois
números com cerca de 60 algarismos) e isso requer grande poder de processamento
e memória, o que os aparelhos de celular e os palmtops não possuem.
Recentemente, o RSA encontrou um
rival de peso, voltado para os desafios do mundo das comunicações sem fio e do
comércio portátil. Os novos códigos usados para proteger o mundo cibernético
não são baseados nos números primos, são baseados em algo revolucionário: as curvas elípticas que são definidas por
tipos especiais de equações, aquelas de Andrew Wiles d`O Ultimo Teorema de Fermat.
O método - desenvolvido por Neal
Koblitz, da Universidade de Washinton - baseado em curvas elípticas não precisa
de chaves numéricas muito grandes, desta forma esses códigos são perfeitos para
o comércio móvel. Enquanto o RSA multiplica as horas do relógio em
calculadoras-relógio para embaralhar os números de cartões de crédito para protegê-los,
Koblitz propõe que esses números de cartões de crédito se percam em alguma
curva elíptica numa multiplicação estranha definida por pontos dessa curva. Portanto,
o desafio, isto é, a proposta de Riemann recaiu agora na matemática criada por ele mesmo.
SABER MAIS:
DU SAUTOY, Marcus. A Música dos Números Primos – A
história de um problema não resolvido na matemática (The Music Of The Primes, 2003.
Tradução de Diego Alfaro). Jorge Zahar Editor Ltda, Rio de Janeiro - 2008.
Análise
Combinatória e Probabilidade. IMPA – Morgado, Pitombeira, Carvalho, Fernandez. Instituto de Matemática Pura e Aplicada,
1991.
“Não adie
dificuldades” Augusto César de Oliveira Morgado
TÉCNICAS DE CONTAGEM
A aula virtual de Combinatória do professor
Paulo Cezar do Instituto de Matemática Pura e Aplicada – IMPA - baseada no
livro Temas e Problemas - consiste em mostrar as diferenças existentes entre os
Corolários decorrentes do Princípio Fundamental da Contagem, e sobre tudo fazer
o aluno a raciocinar e não mecanizar o aprendizado através de fórmulas que não
satisfazem todos os casos que poderão ocorrer.
Antes de iniciar a aula, o professor
Paulo Cezar faz um pequeno discurso, defendendo que “... só faz sentido, no
Ensino Médio, um estudo fortemente baseado nos problemas.”. Visando orientar os alunos a não cometerem
erros tradicionais no aprendizado de Análise Combinatória, ele reforça dizendo
que “aprendemos Matemática usando pouco, a nossa capacidade para raciocinar”.
Aprendemos no automático, através de fórmulas, uma vez que os professores agem
deste modo. Ele encerra o discurso dizendo “... uma das coisas mais básicas
quando começa a nossa vida Matemática é contar e operar com as quatro
operações”.
Nos livros de Matemática do Ensino
Médio, de modo geral, o capítulo referente à Análise Combinatória refere-se às
Técnicas de Contagem como Permutações Simples, Combinações Simples e Arranjos
Simples, no entanto o professor Cezar, em sua aula defende que Permutações
Simples e Combinações Simples são os problemas necessários para a vida escolar;
todo o resto, arranjo e arranjo com repetição, são desnecessários.
Considerando que a pesquisa feita para
a realização deste trabalho, toma como referência três livros, citados na
bibliografia, decidimos definir Arranjos e mostrar um exemplo tal como aparece
nos livros.
Todos os exercícios, a partir da seção
de exercícios, apresentados neste trabalho, foram observados e retirados da
aula virtual do professor Paulo Cezar.
1.Introdução
AAnálise Combinatória é a parte da
Matemática que analisa estruturas e relações discretas, na qual estudamos as
técnicas de contagem de agrupamentos que podem ser feitos com elementos de um
dado conjunto. São basicamente dois tipos de agrupamentos que podemos formar:
um em que se leva em conta a ordem dos elementos dentro do agrupamento e outro
onde a ordem dos elementos é irrelevante.
Por exemplo, se desejarmos contar quantas
placas de licença de automóveis podem ser feitas, construídas por 3 letras
seguidas de 4 algarismos, devemos levar em conta a ordem das letras e dos algarismos:
ALO 1964 e LOA
1946 são placas diferentes.
Da necessidade que o homem teve em calcular
maneiras seguras de ganhar em certos jogos de azar, tais como: baralhos, dados
e moedas, o levou a desenvolver técnicas que, atualmente, são bases para muitos
ramos do conhecimento. Por exemplo, se o nosso problema for contar
quantas senas são possíveis de ser sorteadas na loteria de números, ou seja,
loto; observamos que a ordem dos números que compõem o jogo da sena não
importa:
01, 02, 03, 04, 05, 06 e 05, 03, 06,
01, 02, 04 são senas iguais.
Estes
exemplos servem para mostrar que é importante termos uma técnica de contagem
indireta, isto é, na qual não precisamos escrever um por um dos elementos e
depois contá-los. Isso, em geral, além de ser muito laborioso, pode nos levar a
erro por omissão ou por repetição de algum agrupamento.
A Análise
Combinatória é aplicada em diversos tópicos da Matemática. Particularmente, na
Matemática, aplicamos na Teoria das Probabilidades e no desenvolvimento do
Binômio de Newton (Sir Isaac Newton (1642-1727) físico e matemático inglês). É
também útil em outros campos do conhecimento, como a Economia, a Biologia
Molecular, a Programação de Computadores, A Geometria Combinatória, A Teoria
dos Grafos e em muitos outros campos do conhecimento.
Vamos
começar com o seguinte problema:
1.1. O Princípio
Fundamental da Contagem:
Imaginemos
que para ir de uma cidade α para uma cidade β existem três estradas: a, b e c,
e de β para γ existem duas: 1 e 2.
a
⟹ 1
α b β⟹ γ
⟹ 2
c ⟹
⟹
Para ir
de α a γ, passando por β, podemos optar por um entre 6 caminhos:
α a β 1 γ
⟹⟹
α a β 2 γ
⟹⟹
α b β 1 γ
⟹⟹
α b β 2 γ
⟹⟹
α c β 1 γ
⟹⟹
α c β 2 γ
⟹⟹
Podemos também representar esses
caminhos num esquema como o seguinte, que denominamos árvore de possibilidades:
α β γ
1
*
____________
a1
*
2
*
____________
a
a2
1
*
____________
b1
0
b
*
2
*
____________
b2
c
*
____________
1
c1
*
2
*
____________
c2
A ida de
α para γ consta de duas etapas: a primeira, de α para β, pode ser realizada de
3 modos, sendo que para cada um deles a segunda etapa, de β para γ, pode ser
realizada de 2 modos. A realização das duas etapas sucessivamente pode ser
feita de 3 . 2 modos, que correspondem aos 6 caminhos de α para γ.
Princípio
Fundamental da Contagem:
Se uma ação é composta de duas etapas
sucessivas, sendo que a primeira pode ser feita de m modos e, para cada um
destes, a segunda pode ser feita de n modos, então o número de modos de
realizar a ação é m. n.
Esse
princípio pode ser generalizado para ações compostas de mais de duas etapas.
Por exemplo: Quantos números naturais pares, de três algarismos distintos,
podemos formar com os algarismos 1, 2, 3, 4, 5, 6, 7 e 8.
Solução:
Formar um número par formado por três algarismos distintos é uma ação composta
de três etapas sucessivas, sendo que a primeira é escolher o algarismo das
unidades, que deve ser par (há 4 possibilidades: 2, 4, 6 ou 8). Eliminando o
algarismo escolhido, sobram 7 possibilidades para a escolha do 2º em seguida 6
possibilidades para a escolha do 3º algarismo.
7 x 6 x 4 = 168
1.2. Permutações Simples:
Com os
símbolos ∞, ♫ e Ώ podemos formar as seguintes secessões:
Cada uma
dessas sucessões é chamada permutação
dos três símbolos.
Denominamos permutação de n elementos dados
a toda sucessão de n termos formada com os n elementos dados.
Duas
permutações dos mesmos objetos são diferentes se a ordem dos objetos numa delas
é diferente da ordem em que os objetos estão colocados na outra.
As
permutações são representadas utilizando parênteses e separando os termos por
vírgula ou ponto e vírgula (em sequências). Por exemplo, formar os anagramas (anagramas
são ‘palavras’ formadas com as mesmas letras da palavra dada. Tais ‘palavras’
podem não ter significado em nenhum idioma) das palavras: SUE e PEPE.
Solução:
Para
a palavra SUE, os anagramas são:
SUE,
SEU, USE, UES, ESU, EUS;
e para a palavra PEPE, temos:
PEPE,
PEEP, PPEE, EPPE, EPEP, EEPP.
1.2.1. Quantidade
de Permutações:
Nas aplicações, geralmente
estamos interessados na quantidade
de permutações que podem ser feitas com determinados elementos. Para determinar
o número de permutações não é necessário que façamos uma por uma e depois as
contemos, pois esse procedimento, às vezes, pode ser inviável.
Permutações de Elementos Distintos:
Vejamos quantas permutações
podem ser formadas com as letras A, M,
P, S e T. Formar uma dessas permutações é uma ação composta de cinco
etapas sucessivas:
1ª etapa: escolher a primeira letra da permutação. Ela
pode ser A ou M ou P ou S ou T. Há, portanto, 5 possibilidades para cada etapa.
2ª etapa: escolher a segunda letra da permutação. Para
cada possibilidade da primeira etapa teremos 4 possibilidades nesta segunda
etapa, uma vez que uma das letras já terá sido eliminada. Por exemplo, se a
primeira letra escolhida foi S, então a segunda letra poderá ser A ou M ou P ou
T.
3ª etapa: escolher a terceira letra da permutação. Para
cada par de letras já escolhidas anteriormente teremos 3 possibilidades nesta
terceira etapa. Note que, se escolhermos S e A, a terceira letra poderá ser M
ou P ou T.
4ª etapa: escolher a quarta letra da permutação. Então há
2 possibilidades para cada escolha das três letras anteriores.
5ª etapa: colocar a quinta letra da permutação. Agora
temos única possibilidade para cada escolha das 4 primeiras letras.
possibilidades
à 5
x 4 x 3
x 2
x 1 = 120
Pelo
princípio fundamental da contagem, concluímos que podemos formar 5 x 4 x 3 x 2
x 1 permutações diferentes, isto é, existem 120 permutações das cinco letras A,
M, P, S e T, ou ainda de cinco objetos diferentes quaisquer.
Definimos fatorial de n como o
produto dos n números naturais consecutivos de 1 até n. Denotado por n!, isto
é, fatorial de n ou n fatorial.
Simbolicamente, escrevemos: n!
= 1 . 2 . 3 . ... . (n – 2) . (n – 1) . n, n ≥ 2, que é o modo de ordenar n objetos
distintos.
Desta forma, se fizermos
3! = 1. 2. 3= 6
4!
= 1. 2. 3. 4 = 24.
6! = 1. 2. 3. 4. 5. 6 = 720.
7! = 1. 2. 3. 4. 5. 6. 7 = 5040.
8! = 1. 2. 3. 4. 5. 6. 7. 8 = 40320
e assim por diante, note que
4! = 3!.4
5! = 4!.5
6! = 5!.6
7! = 6!.7
8! = 7!.8 Isso nos leva a escrever n! = (n – 1)! . n
Note ainda, que se n = 2, teremos 2!
= (2 – 1)! . 2 que implica 2 = 1! . 2,
logo, 1! = 1. Se tivermos n = 1, isso nos leva a 1! = (1 – 1)! . 1 que implica
1! = 0!. 1, portanto, 0! = 1.
Destas justificativas decorrem as
definições: 0! = 1 e 1! = 1.
Indicamos
o número de permutações de n elementos diferentes por Pn. Temos,
assim, que: Pn = n!
1.2.2. Permutações
com Elementos Repetidos:
Vejamos
agora quantas permutações podemos formar com elementos entre os quais há
repetições. Com as letras A, A e M há 3 permutações apenas:
(A,
A, M), (A, M, A) e (M, A, A)
se as letras A e A fossem distintas - por exemplo, A e A -,
cada uma dessas permutações geraria duas permutações distintas:
(A, A, M) (A, M, A) (M, A, A)
(A, A, M) (A, M, A)
(M, A, A)
(A, A, M) (A, M, A) (M, A, A)
Sabemos
que o número de permutações de 3 elementos distintos é P3 = 3! = 6.
Agora vemos que, se entre os 3 elementos tivermos 2 repetidos, esse número fica
dividido por 2!, que é o número de permutações dos 2 elementos se eles forem
considerados distintos. Indicamos o número de permutações de 3 elementos sendo
2 repetidos por 3P2 = 3!/2! = 3x2x1/2x1! = 3
Tomemos
agora um exemplo com 5 elementos, sendo 3 repetidos: ☼, ☼, ☼, ♀ e ♂. Cada
permutação desses símbolos geraria 3! permutações se os ícones ☼, ☼ e ☼ fossem
distintos:
(☼, ☼, ☼, ♀, ♂)
(☼, ☼, ☼, ♀, ♂)
(☼, ☼, ☼, ♀, ♂)
(☼,
☼, ☼, ♀, ♂)
(☼, ☼, ☼, ♀, ♂)
(☼, ☼, ☼, ♀, ♂)
(☼, ☼, ☼, ♀, ♂)
Assim, o número de permutações desses 5 elementos é igual
ao número de permutações obtidas se elas forem consideradas distintas divididos
por 3!, ou seja:
5P3
= 5!/3! = 5x4x3!/3! = 20
Possíveis
permutações
(☼, ☼, ☼, ♀, ♂)
(☼, ☼, ♂, ♀, ☼)
(☼, ♂, ☼, ♀, ☼)
(♂, ☼, ☼, ☼, ♀)
(♂, ☼, ♀, ☼, ☼)
(☼, ☼, ☼, ♀, ♀)
(☼, ☼, ♀, ♂, ☼)
(☼, ♀, ☼, ♂, ☼)
(♀, ☼, ☼, ☼, ♂)
(♀, ☼, ♂, ☼, ☼)
(☼, ☼, ♂, ☼, ♀)
(☼, ♂, ☼, ☼, ♀)
(☼, ♂, ♀, ☼, ☼)
(♂, ☼, ☼, ♀, ☼)
(♂, ♀, ☼, ☼, ☼)
(☼, ☼, ♀, ☼, ♂)
(☼, ♀, ☼, ☼, ♂)
(☼, ♀, ♂, ☼, ☼)
(♀, ☼, ☼, ♂, ☼)
(♀, ♂, ☼, ☼, ☼)
E se
substituímos o sinal ♀ pelo ♂, isto é, considerarmos os sinais ☼, ☼, ☼, ♂ e ♂,
as 20 permutações anteriores ficarão reduzidas a 10 apenas. Veja, por exemplo,
que (☼, ☼, ☼, ♀, ♂) e (☼, ☼, ☼, ♂, ♀) ficarão iguais a (☼, ☼, ☼, ♂, ♂).
Logo, o
número de permutações ficará dividido por 2!. Indicamos a quantidade de
permutações de 5 elementos, sendo 3 repetidos de um tipo e 2 repetidos de
outro, por 5P3,2 . Temos:
5P3,2
= 5!/3!2! = 5x4x3! / 3! 2! = 10
Quando
temos n elementos dos quais n1 são repetidos de um tipo, n2
são repetidos de outro tipo, n3 são repetidos de outro tipo, e assim
por diante, o número de permutações que podemos formar é dado por:
nPn1n2
... nk = n! / n1! n2! ... nk! (n1
+ n2 + ... + nk = n)
1.3. Combinações Simples
Suponhamos
que a professora Teresa dispõe de duas bolsas para o Mestrado em Estatística e
decide sorteá-las entre os alunos que acertarem um problema que irá propor,
premiando assim dois alunos. Imaginemos que quatro alunos acertem a pergunta:
Aloyana, Suelen, Pedro e Monik. Os alunos premiados poderão ser:
Aloyana e Suelen, ou Aloyana e Pedro, ou
Aloyana e Monik, ou Suelen e Pedro, ou Suelen e Monik, ou Pedro e Monik.
Cada uma
dessas possibilidades é um agrupamento
dos 4 alunos tomados 2 a 2. Em cada um desses agrupamentos, a ordem em
que citamos os elementos não importa. Note que dar as bolsas para Suelen e
Monik, ou dá-las para Monik e Suelen, é exatamente a mesma coisa. Quando
agrupamos elementos de modo que em cada agrupamento não importa a ordem dos elementos, esses agrupamentos são
chamados combinações. Na
linguagem matemática, as combinações são conjuntos cujos elementos são
escolhidos entre os elementos dados.
Denominamos combinações de n elementos
distintos tomados k a k aos conjuntos formados por k elementos distintos
escolhidos entre os n elementos dados.
Tomando o
exemplo acima, consideremos os elementos
Aloyana, Suelen,
Pedro e Monik
Vamos escrever as combinações desses 4 elementos tomados 2
a 2:
Isso
significa que a partir de uma combinação podemos obter k! arranjos dos n
elementos tomados k a k. Então, o número de combinações é igual ao número de
arranjos dividido por k!:
nCk = An,k / k!
logo,
Cn,k = n! / k!(n-k)!
1.4.Arranjos
Suponhamos
agora que a professora Teresa tenha duas bolsas para o mestrado: uma para o
Mestrado Acadêmico (Stricto Sensu) e a outra para o Mestrado Profissional (Lato
Sensu) e anuncie que o primeiro aluno sorteado irá receber a bolsa para Lato
Sensu e o segundo sorteado receberá a bolsa para Stricto Sensu. Nesse caso, se
os alunos sorteados fossem Aloyana e Pedro, nessa ordem, Aloyana receberia a
bolsa para Lato Sensu e Pedro a bolsa para Stricto Sensu. Mas, se os sorteados
fossem Pedro e Aloyana, nessa ordem, Pedro receberia a bolsa Lato Sensu e
Aloyana a bolsa Stricto Sensu.
Agora nós
temos uma situação em que os agrupamentos
Aloyana e Pedro e
Pedro e Aloyana
são considerados agrupamentos diferentes. Portanto, ao
citarmos o agrupamento, importa a ordem em que citamos os elementos.
Quando
agrupamos elementos de modo que em cada agrupamento importa a ordem dos elementos, esses agrupamentos são chamados arranjos. Na linguagem matemática, os
arranjos são sucessões cujos termos são escolhidos entre os elementos dados.
Denominamos arranjos de n elementos
distintos tomados k a k às sucessões formadas de k termos distintos escolhidos
entre os elementos dados.
No
exemplo citado, considere os elementos
Aloyana, Suelen,
Pedro e Monik
Vamos escrever os arranjos desses 4 elementos tomados 2 a
2:
Observe
que dois arranjos são diferentes se tiverem elementos diferentes, ou se tiverem
os mesmos elementos, porém em ordens diferentes. Os arranjos são representados
colocando os elementos entre parênteses.
1.4.1. Quantidade de Arranjos:
Representamos
pelo símbolo An,k , ou pelo símbolo nAk, o
número de arranjos de n elementos tomados k a k.
Para
determinar essa quantidade de arranjos, imagine que vamos formar um deles, isto
é, vamos formar uma sucessão de k termos escolhidos entre os n elementos dados:
(1º, 2º, 3º, ... ,
kº)
O
primeiro termo pode ser qualquer um dos n elementos dados; há, portanto, n
possibilidades para ele.
Para cada
uma dessas possibilidades, o segundo termo do arranjo poderá ser qualquer um
dos (n – 1) elementos restantes, excluindo aquele já escolhido. Há, portanto,
(n – 1) possibilidades para o segundo termo.
Para cada
par de elementos já escolhidos, o terceiro termo poderá ser qualquer um dos (n
– 2) elementos restantes. Há, portanto, (n – 2) possibilidades para o terceiro
termo.
E assim
sucessivamente.
arranjos: (1º, 2º, 3º, ... , kº)
possibilidadesn n-1 n-2 n – (k – 1)
Pelo
princípio fundamental da contagem, concluímos que a quantidade de arranjos que
podem ser formados é:
An,k= n . (n – 1) . (n – 2) . ...
. (n – (k – 1)) produto de k fatores
1.5.Exercícios
A primeira questão proposta por Paulo
Cezar diz: “Chapa com 4 pessoas. De quantos modos pode-se escolher um
presidente e um vice?” Esta é uma
questão de combinação simples. Note que no conjunto = {A, B, C, D}, que
representa as 4 pessoas, não importa
como os elementos são escolhidos; importa que eles são escolhidos dois a dois.
Como para presidente temos 4 possibilidades e para cada vez que escolhemos um
candidato nos restam 3 possibilidades para escolhermos um vice (AB, AC, AD, BA,
BC, BD, CA, CB, CD, DA, DB, DC), então pelo Princípio Fundamental da Contagem
temos 4 x 3 = 12 possibilidades. Observação feita pelo professor: “embora a
escolha do vice dependa do presidente, o número de possibilidades não depende”.
Na segunda questão temos: “Duas chapas
uma com 4 e a outra com 5 membros. Qual o número de modos para presidente e
vice?”. Neste caso, contaremos separadamente o número de candidatos e em cada
chapa temos escolhas distintas. Então somamos o número de possibilidades das
duas chapas que são conjuntos disjuntos:
Chapa
1: 4 x 3 = 12
Chapa 2: 5 x 4 =
20 → 12 + 20 = 32
Dando prosseguimento à aula, o
professor Paulo Cezar enuncia “Três
Regras de Ouro” - propostas pelo professor Augusto César de Oliveira Morgado (1944-2006)
- para resolver problemas de combinatória:
Regra
1: Postura (coloque-se na posição de quem tem que formar um grupamento qualquer
que queremos contar)
Regra
2: Divisão do Processo em Etapas
Regra
3: Princípio (não adiar dificuldades)
A terceira regra é ilustrada pelo
seguinte problema: “Quantos são os números de 3 algarismos distintos?”.
Colocando em prática as duas primeiras regras, vem: Analisando a questão, um
número é fixado na casa das centenas. Como não temos números naturais começados
por zero, então ele é descartado para esta, onde temos 9 possibilidades. Como
já usamos um algarismo para a casa das centenas, nos restam 9, uma vez que o
zero pode aparecer na casa das dezenas. Finalmente, para a casa das unidades
nos restam 8 algarismos. Portanto, 9 x 9 x 8 = 648.
O professor observou que este problema
não se enquadra nas fórmulas utilizadas para resolver problemas de contagem,
devido às restrições que o problema apresenta. É viável resolver este problema
a partir da casa das centenas e não a partir da casa das unidades, por que não
podemos usar o Princípio Fundamental de Contagem, uma vez que encontraremos
resultado incompatível e estaremos dificultando a solução.
Apresenta os problemas de Permutação
Simples e Combinação Simples e conclui que estes são os problemas importantes
que os alunos deveriam conhecer e que as escolas deveriam parar por aqui em
temos de técnica de ensino de Contagem. Todo o resto, arranjo e arranjo com
repetição, são desnecessários.
Propõe um problema de permutação
simples para ilustrar o raciocínio: “De quantos modos n pessoas podem ser
colocadas em fila?” Acrescenta ele, que este problema poderia ser proposto
perguntando quantos anagramas? ou quantas bijeções? Para solucionar o problema,
ele usa o mecanismo de preencher os espaços, chegando ao princípio da Fatorial:
____ ____
____ ... ____
n
n – 1 n – 2 ...
1 → Pn = n (n – 1) ... 1 = n!
Concluindo
que é um absurdo os livros apresentarem a Fatorial como primeiro assunto
apresentando exercícios não correspondentes com a realidade e mais adiante
reaparece para resolver questões mais difíceis.
Dando sequência, é apresentado um
problema de combinação simples que pergunta: “De quantos modos pode-se escolher
uma comissão formada por 3 algarismos numa turma de 20” Como não há cargos
fixos, mas para facilitar a solução vamos considerar que haja, então temos:
A / 20 .B / 19. C / 18
Mas
a comissão BAC é a mesma, então precisamos contar a mais e fazer uma correção
nesta contagem. Neste caso, a comissão é um conjunto de 3 pessoas e precisamos
ordenar as 3. Cada comissão é contada 3! = 6 vezes, então o número de comissão
é:
20 x 19 x 18 / 6
O professor, conclui que este tipo
de problema é extremamente difícil.
Para encerar a aula é proposto um
problema que apresenta certas dificuldades para solucioná-lo: “Com 4 homens e 3
mulheres. Queremos comissão de 3 pessoas, sendo pelo menos uma mulher”. Como se
pode ter ou 3 mulheres ou 2 mulheres ou 1 mulher e devemos ter 20C3
lê-se número de combinação de 20 elementos tomados 3 a 3. Expressões do tipo: pelo menos, no
mínimo, no máximo sempre indicam que quem está tentando resolver o problema vai
ter trabalho.
nCp = n(n-1) ... (n-p+1) / p!
se tivermos 1 mulher só teremos 2
homens
se tivermos 2 mulheres só teremos 1
homem
se tivermos 3 mulheres não teremos
nenhum homem
então para o 1º caso temos 3C1
. 4C2=
3 x 6 = 18
então para o 2º caso temos 3C2
. 3C2 . 4C1 = 3 x 4 = 12
então para o 3º caso temos 3C3
= 1
→ 18 + 12 + 1 = 31.
Segundo o professor, provavelmente
aparecerá alguém para resolver este problema de modo rápido e apresentará a
seguinte solução: Escolher a mulher e como temos 3 modos para escolher a
mulher, então fazemos
3
. 6C2. 15 = 45 que está errado.
Explique isso!
Explicação: O erro está em contar
3 mulheres tomadas 2 a 2 e contar, outra
vez, 2 mulheres mais 4 homens tomados 2 a 2. E finalmente multiplicar os dois
resultados. Como para solucionarmos problemas devemos dividi-lo em etapas,
neste caso as etapas foram misturadas excedendo em 14 pessoas.
Portanto, os problemas de contagem
apresentam particularidades muito sutis que exigem muita perícia de quem os
analisa.
Saber
Mais
MORGADO,
Augusto César de Oliveira. PITOMBEIRA, João Bosco de Carvalho. CARVALHO, Paulo
Cezar Pinto. FERNANDEZ, Pedro. Análise Combinatória e Probabilidade. IMPA –
Instituto de Matemática Pura e Aplicada, 1991.
FACCHINI,
Walter. Matemática, Volume Único, 2ª edição. Editora Saraiva, 1997.
HAZZAN, Samuel.
Fundamentos de Matemática Elementar volume 5 – Análise Combinatória, 6ª edição.
Editora Atual, 1995.
Fundamentos de Matemática Elementar volume 5 –
Análise Combinatória, 6ª edição. Samuel Hazzan. Editora Atual, 1995.
