Métodos Finitos em Matemática - arquivoescolar.org · maneiras distintas é ... quadrados do tabuleiro original tiverem alternadamente as cores ... Suponhamos que num determinado

Metodos Finitos em Matematica

Mestrado em Matematica para Professores

Samuel A. Lopes

16 de Novembro de 2009

2

Conteudo

1 Introducao 3

2 Metodos elementares de contagem 62.1 As leis da soma e do produto . . . . . . . . . . . . . . . . . . . . . . . 62.2 Bijeccoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3 Convencoes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4 Alguns exercıcios de aquecimento . . . . . . . . . . . . . . . . . . . . . 112.5 Um trilema: tres visoes de um problema . . . . . . . . . . . . . . . . . 122.6 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.7 Permutacoes, arranjos, combinacoes . . . . . . . . . . . . . . . . . . . . 192.8 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.9 Os teoremas binomial e multinomial . . . . . . . . . . . . . . . . . . . . 282.10 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.11 O princıpio do pombal . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.12 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3 Introducao a Teoria de Grafos 383.1 Definicoes e exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.2 O primeiro resultado . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.3 Passeios em grafos e conexao . . . . . . . . . . . . . . . . . . . . . . . . 473.4 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.5 Grafos Eulerianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543.6 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623.7 Grafos Hamiltonianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.8 O Problema do Caixeiro Viajante . . . . . . . . . . . . . . . . . . . . . 723.9 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803.10 Arvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873.11 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 963.12 Formula de Euler e coloracao de mapas . . . . . . . . . . . . . . . . . . 1023.13 Exercıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

1

CONTEUDO 2

Bibliografia 114

Capıtulo 1

Introducao

Estas notas foram compiladas como texto de apoio a disciplina “Metodos Finitos emMatematica” da Pos-Graduacao em Matematica para Professores (actualmente Mes-trado em Matematica para Professores) no ano lectivo de 2007/2008. Uma das razoesque me levaram a escreve-las foi permitir que os alunos se puessem concentrar mais naaula em si e menos em anotar tudo o que era dito e escrito no quadro, especialmentepor a disciplina funcionar em horario pos-laboral. Penso que desta forma e – e foi –possıvel fomentar uma maior intervencao e discussao entre os alunos durante as au-las bem como a sua participacao activa no desenvolvimento dos resultados e das suasprovas.

Procurei que os topicos escolhidos e a forma como foram abordados fossem espe-cialmente adequados as necessidades de um professor de matematica do 3o ciclo doEnsino Basico ou do Ensino Secundario. A primeira parte das notas cobre aspectosbasicos de combinatoria enumerativa enquanto a segunda constitui uma introducao ateoria de grafos. Topicos mais especıficos, como sejam a teoria das funcoes geradoras,numeros de Catalan, Bell e Stirling, particoes de um inteiro, emparelhamentos, redese fluxos, coloracao (de vertices, arestas e de mapas em superfıcies), teoria de Ramsey,etc. foram deixados como temas para os trabalhos dos alunos, a apresentar oralmentee por escrito para avaliacao.

A combinatoria, em particular a teoria de grafos, e uma das areas da matematicacujo desenvolvimento foi, pelo menos parcialmente, motivado por problemas de natu-reza recreativa. Com o decorrer do tempo, o numero de aplicacoes desta teoria foicrescendo e e actualmente uma das areas da matematica com mais aplicacoes, queincluem a programacao e ciencia de computdores, ciencias sociais, biologia, quımica,desenho de redes e optimizac ao industrial.

A combinatoria ocupa-se da analise de estruturas discretas, como o estudo dospossıveis arranjos de objectos de um conjunto em determinados padroes. Frequente-mente, estamos interessados em saber se determinada configuracao de objectos e suasrelacoes e ou nao possıvel ou se podemos passar de um configuracao a outra seguindo

3

CAPITULO 1. INTRODUCAO 4

determinadas regras. Um exemplo deste tipo de problema e o conhecido Jogo dos 15,em que quinze pecas numeradas de 1 a 15 deslizam horizontalmente e verticalmentenum tabuleiro 4!4 com uma casa vazia, como ilustra a figura abaixo.

O objectivo do jogo e passar desta configuracao inicial para uma outra configuracaofinal dada, digamos por exemplo a seguinte:

Vejamos um outro exemplo simples. Temos um tabuleiro de xadrez de formato8!8 que queremos cobrir completamente com 32 pecas de domino, cada peca cobrindoexactamente dois quadrados adjacentes do tabuleiro sem que haja sobreposicao depecas. Uma tal cobertura e claramente possıvel, portanto perguntamos: De quantasmaneiras distintas e possıvel cobrir o tabulerio de xadrez desta forma? Para respondera esta questao devemos primeiro estabelecer outra: O que e que consideramos formasdistintas de cobrir o tabulerio? Cada resposta distinta a esta ultima pergunta da origema uma nova resposta a primeira pergunta. Podemos agora variar o problema criandoquadrados proibidos no tabuleiro, ou seja, quadrados que no podem ser cobertos pornenhuma peca de domino. Por exemplo, podemos tornar proibidos os quadrados dedois cantos diametralmente opostos do tabuleiro, como na figura abaixo. Sera queainda e possıvel cobrir este tabuleiro?

Apos algumas tentativas podemos comecar a intuir que a reposta a esta ultima per-gunta e negativa, mas sera que podemos estar seguros desta resposta sem analizarmosexaustivamente todas as possibilidades?

CAPITULO 1. INTRODUCAO 5

E de facto impossıvel cobrir com pecas de domino o tabuleiro recortado acima,e podemos prova-lo de uma forma muito simples e clara. Se, como e habitual, osquadrados do tabuleiro original tiverem alternadamente as cores branco e preto, entaono tabuleiro recortado havera 30 quadrados de uma das cores e 32 da outra, uma vez queforam retirados ao tabuleiro original dois quadrados da mesma cor. Se observarmosque cada peca de domino cobre exactamente um quadrado de cada cor, concluimosimediatamente que uma tal cobertura e impossıvel pois para tal teriam de existir notabuleiro tantos quadrados de uma cor como da outra.

Outro problema envolvendo tabuleiros rectangulares com posicoes proibidas con-siste em colocar num dos quadrados do tabuleiro dado um cavalo do jogo de xadrez.O objectivo e que o cavalo percorra todos os quadrados nao interditos do tabuleiroexactamente uma vez, voltando possivelmente a posic cao inicial. Como no jogo dexadrez, o cavalo so se pode movimentar de um quadrado a outro por um movimentoem formato de “L”, isto e, efectuando uma deslocacao horizontal ou vertical de duasposicoes seguida de uma desloccao de uma posicao na direccao perpendicular. Esteproblema pode ser estudado no contexto dos grafos hamiltonianos.

Capıtulo 2

Metodos elementares de contagem

2.1 As leis da soma e do produto

Entenda-se por um evento, algo que e passıvel de ocorrer. Por exemplo, escolher oporta-voz de um grupo de pessoas, atribuir uma cor a uma face de um solido, colocaruma bola numa caixa, atribuir uma turma a um professor ou uma sala a uma turma.Um evento pode ocorrer de uma ou mais formas distintas. Assim, num grupo de 20pessoas, ha 20 possibilidades para a escolha de um porta-voz se todas as pessoas dogrupo forem elegıveis, etc.

Na presenca de varios eventos, cada um podendo ocorrer de uma forma indepen-dente dos restantes, usaremos os dois princıpios seguintes:

Princıpio da multiplicacao. Se um evento pode ocorrer de m formas distin-tas e outro, independente do primeiro, pode ocorrer de n formas distintas, entao acombinacao dos dois eventos pode ocorrer de mn formas distintas.

Exemplo. Ao atirar ao ar uma moeda e lancar um dado, o numero de resultadosdistintos que e possıvel obter e 2! 6 = 12, ja que ha dois resultados possıveis ao atirara moeda ao ar e seis resultados possıveis quando lancamos o dado.

Princıpio da adicao. Se um evento pode ocorrer de m formas distintas e outro,independente do primeiro, pode ocorrer de n formas distintas, entao existem m + nformas de um dos dois eventos ocorrer.

Exemplo. De entre as cinco letras romanas a, b, c, d, e, e as tres letras gregas !, ",#, ha 5 + 3 formas de escolher uma letra e 5! 3 formas de escolher uma letra de cadaalfabeto.

Exemplo. Suponhamos que num determinado ano academico sao oferecidas sete disci-plinas de manha e cinco disciplinas a tarde. Um estudante que se quer inscrever numa

6

CAPITULO 2. METODOS ELEMENTARES DE CONTAGEM 7

disciplina de manha e noutra de tarde tem 7 ! 5 = 35 escolhas possıveis, ao passoque um estudante que se tenha de inscrever em apenas uma disciplina a sua escolha,independentemente de ser de manha ou de tarde, tem 7 + 5 = 12 escolhas possıveis.

Exemplo. Quantos inteiros entre 5000 e 10000 e que tem todos os seus algarismos (nabase 10) distintos?

Os inteiros pretendidos tem precisamente quatro algarismos. O algarismo dos mi-lhares tera de ser 5, 6, 7, 8 ou 9. Escolhido este, ha nove possibilidades para o algarismodas centenas. De forma analoga, existem oito possibilidades para o algarismo das de-zenas e sete para o das unidades. No total, ha 5 ! 9 ! 8 ! 7 = 2520 numeros nascondicoes pretendidas.

Note-se que a resolucao deste problema se tornaria mais difıcil de comecassemospor discutir um algarismo que nao fosse o dos milhares.

Exemplo. Quantos pares distintos de inteiros a, b entre 1 e n e que existem com a " b?Neste problema, os eventos “escolher a” e “escolher b” nao sao independentes,

portanto a resposta nao e n2 nem n(n# 1).


2.2 Bijeccoes

Para cada inteiro positivo n, seja {1, 2, . . . , n} o conjunto dos inteiros entre 1 e n. Dadoum conjunto A, dizemos que A tem cardinalidade n e escrevemos |A| = n se existiruma bijeccao entre os conjuntos A e {1, 2, . . . , n}. Dizemos ainda que o conjunto A efinito se |A| = n para algum n.

Os princıpios da adicao e da multiplicacao podem ser justificados a luz da seguinteproposicao:

Proposicao 2.1. Sejam A e B conjuntos finitos. Entao:

(a) |A $B| = |A| + |B|, se A %B = &;

(b) |A!B| = |A||B|.

Exemplo. Quando sao lancados dois dados diferentes, de quantas formas pode serobtido um sete ou um oito?

A cada lancamento dos dados associamos um par ordenado (a, b), onde a e o resul-tado do lancamento do primeiro dado e b o resultado do lancamento do segundo dado.Sejam A e B os conjuntos dos pares ordenados que correspondem a um resultado desete e oito, respectivamente. Entao:

A = {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)},B = {(2, 6), (3, 5), (4, 4), (5, 3), (6, 2)}.

Como A % B = &, temos que |A $ B| = |A| + |B| = 6 + 5 = 11. Sendo assim, umresultado de sete ou de oito pode ser obtido de 11 formas distintas.

Exemplo. Ao lancar uma moeda ao ar tres vezes, de quantas formas se pode obteruma, duas ou tres caras?

Representemos um resultado de caras por C e um de coroas por M . Sejam A1, A2

e A3 os conjuntos formados pelos resultados “uma cara”, “duas caras” e “tres caras”,respectivamente. Temos:

A1 = {(C, M, M), (M, C, M), (M, M,C)},A2 = {(C, C,M), (C, M, C), (M, C, C)},A3 = {(C, C,C)}.

Como estes conjuntos sao dois-a-dois disjuntos,

|A1 $ A2 $ A3| = |A1| + |A2| + |A3| = 3 + 3 + 1 = 7.


Exemplo. Suponhamos que as matrıculas dos veıculos num determinado paıs consis-tem em sequencias de duas letras seguidas de quatro algarismos, como acontece emPortugal. Quantas placas de matrıcula distintas e que podemos formar seguindo esteprocedimento?

Seja A = {A, B, . . . , Z} o conjunto das letras do alfabeto (excluindo K, Y e W ) eB = {0, . . . , 9} o conjunto dos algarismos possıveis. O conjunto de todas as matrıculaspossıveis e A! A!B !B !B !B e

|A! A!B !B !B !B| = |A|2|B|4 = 232104 = 5290000.

Exemplo. Quantos pares distintos de inteiros a, b entre 1 e n e que existem com a " b?Pretendemos calcular |A|, onde A = {(a, b) ' N2 | 1 " a, b " n e a " b}. Sejam

B = {(a, b) ' N2 | 1 " a, b " n + 1 e a < b} e C = {X ( {1, . . . , n + 1} | |X| = 2}.Entao (a, b)

f)* (a, b + 1) e uma bijeccao de A em B e (x, y)g)* {x, y} e uma bijeccao

de B em C. Logo, g + f e uma bijeccao de A em C. Como veremos, |C| =!

n+12

", logo

|A| = |C| = (n+1)n2 .

O seguinte resultado e por vezes util em contagem:

Proposicao 2.2. Sejam A e B conjuntos finitos.

(a) Se existir uma funcao injectiva Af* B entao |A| " |B|.

(b) Se existir uma funcao sobrejectiva Af* B entao |A| ,| B|.


2.3 Convencoes

De forma a evitar algumas ambiguidades que comummente ocorrem na formulacaode problemas de contagem, iremos aqui adaptar algumas convencoes. O leitor deverano entanto conformar-se com a inevitabilidade da persistencia de ambiguidades emproblemas de contagem. Evita-lo implicaria frequentemente tornar o enunciado dosproblemas demasiado longo e complexo. Nestes casos, o leitor devera indicar quaisforam as convencoes que adoptou na resolucao do problema e, se possıvel, apresentarsolucoes alternativas de forma a prever outras possıveis interpretacoes.

Assumimos que e sempre possıvel distinguir duas pessoas de um grupo. Por suavez, todas as laranjas sao iguais, o mesmo acontecendo com macas, bolas amarelas, A’s,moedas com o mesmo valor facial e dados, a menos que haja indicacao em contrario.

So consideramos a ordem das escolhas relevante se tal for explicitado no problema.O alfabeto tem 23 letras, 5 das quais sao vogais, sendo as restantes 18 consoantes. Umapalavra e uma sequencia (ordenada) de letras ou sımbolos. Um baralho de cartas tem52 cartas, 13 de cada um dos 4 naipes, que sao espadas, paus, copas e ouros. As carasde espadas e de paus sao pretas; as de copas e de ouros sao vermelhas. Em cada naipeha uma carta com cada um dos valores faciais 2, 3, . . . , 10, rainha, valete, rei e as.


2.4 Alguns exercıcios de aquecimento

1. Em 8 minutos, responda as seguintes 10 questoes de forma concisa mas completa.Em caso de duvida, devera indicar quais foram os pressupostos assumidos.

(a) Quantas formas ha de escolher uma pessoa de um grupo de 6 rapazes e 8raparigas?

(b) Quantas formas ha de escolher uma peca de fruta de 6 laranjas e 8 macas?

(c) Quantas formas ha de escolher uma letra de 3 A’s, 5 B’s e 7 C’s?

(d) Quantas formas ha de escolher duas letras de 3 B’s e 3 G’s?

(e) Quantas formas ha de escolher duas pessoas de 3 rapazes e 3 raparigas?

(f) Quantas formas ha de escolher 5 laranjas de um conjunto de 6 laranjas?

(g) Quantas formas ha de escolher 5 raparigas de um conjunto de 6 raparigas?

(h) Quantas formas ha de escolher 1 rapariga de um conjunto de 6 raparigas?

(i) Quantas formas ha de escolher 5 pecas de fruta de 7 laranjas e 8 macas?

(j) Quantas formas ha de escolher algumas pecas de fruta de 9 laranjas e 6macas se pelo menos uma peca de fruta e escolhida?

2. Discuta as varias respostas possıveis a questao: “Quantos resultados podem serobtidos ao lancar um par de dados?”

3. Um numero de telefone e composto por sete dıgitos. Suponhamos que o primeirodıgito (da esquerda para a direita) e um algarismo entre 2 e 9, o segundo e oterceiro sao algarismos entre 1 e 9 e os restantes sao algarismos entre 0 e 9.Quantos numeros de telefone distintos podem ser formados nestas condicoes?

4. Uma empresa produz cadeados com combinacao. Cada combinacao consiste emtres numeros inteiros entre 0 e 99, mas nenhum numero pode aparecer mais deuma vez na combinacao. Por exemplo, 23 # 2 # 3 e uma combinacao possıvel,mas 23# 4# 23 nao e. Quantas combinacoes distintas e possıvel formar?

5. Uma companhia de computadores quer contratar um director e um subdirectorde entre um grupo de cinco candidatos ja pre-seleccionados. De quantas formasdistintas o pode fazer? E se em vez de contratar um director e um sub-directorquiserem contratar dois sub-directores?


2.5 Um trilema: tres visoes de um problema

Problema. E Pascoa e a professora Celeste quer colorir com os seus alunos k ovos daPascoa, dispondo para tal de tintas de n cores diferentes. De quantas formas distintase que o podem fazer?

Nota. A resposta nao e nk! Por exemplo, se n = k = 2, entao as possibilidades sao: osdois ovos da cor 1, os dois ovos da cor 2 ou um ovo de cada cor. Neste caso a respostae 3 -= 22.

Seja xi = numero de ovos a ser pintados da cor i. Entao, queremos saber quantassolucoes tem a equacao

x1 + x2 + · · · + xn = k,

com xi um inteiro nao negativo. Denotamos este numero por f(n, k).

1 o processo

Comecemos por usar um metodo heurıstico, estudando alguns casos particulares.

1. Se so ha uma cor (i.e., n = 1) entao so ha uma forma de pintar os ovos. Logo,

f(1, k) = 1 .k , 1.

2. Se so ha um ovo (i.e., k = 1) entao ha tantas formas de o pintar como o numerode cores. Logo,

f(n, 1) = n .n , 1.

3. Como ja observamos, f(2, 2) = 3.

Em geral, nao e difıcil de calcular f(n, k) para valores pequenos de n e k. Sera queconseguimos encontrar uma formula que permita calcular f(n, k) a partir de valoresmenores de n e k?

Exemplo. Seja!

nk

"o numero de formas de escolher k objectos de um conjunto de n

objectos distintos. Sabemos que#

n

k

$=

#n# 1

k

$+

#n# 1

k # 1

$,

e esta igualdade pode ser deduzida sem usar a formula explıcita para!

nk

", como vamos

agora recordar. Fixemos um dos n objectos, que designaremos por objecto especial.Quando escolhemos k dos n objectos, podemos ou nao escolher o objecto especial. Seoptarmos por nao o escolher, temos de escolher k objectos de entre os n#1 restantes, oque podemos fazer de

!n!1

k

"formas distintas. Caso contrario, se optarmos por escolher

o objecto especial, teremos ainda de escolher k # 1 objectos dos restantes n # 1, quepoderemos fazer de

!n!1k!1

"formas distintas. Pelo princıpio da adicao, temos

!n!1

k

"+

!n!1k!1

"

formas de escolher k objectos de um conjunto de n objectos distintos.


Tentemos proceder com f(n, k) de forma analoga ao que fizemos no exemplo an-terior. Fixemos entao uma cor, que designaremos por cor especial. Quando pintamosos k ovos, podemos usar ou nao a cor especial. Existem f(n # 1, k) formas de pintaros ovos sem usar a cor especial. Quantas formas existem de os pintar usando a corespecial? Temos de pintar pelo menos um com a cor especial, e restam k# 1 ovos, quepodemos pintar com as n cores de f(n, k # 1) formas diferentes. Logo,

f(n, k) = f(n, k # 1) + f(n# 1, k).

Assim, por exemplo,

f(4, 3) = f(4, 2) + f(3, 3)

= f(4, 1) + f(3, 2) + f(2, 3) + f(3, 2)

= 2(f(2, 2) + f(3, 1)) + f(4, 1) + f(2, 2) + f(1, 3)

= 3f(2, 2) + 2f(3, 1) + f(4, 1) + f(1, 3)

= 3! 3 + 2! 3 + 4 + 1

= 20.

Em geral, a relacao de recorrencia f(n, k) = f(n, k # 1) + f(n # 1, k) permite-noscalcular, recursivamente, todos os valores de f(n, k), conhecendo as condicoes iniciaisf(1, k) = 1 e f(n, 1) = n, para n, k , 1. No entanto, este processo pode ser bastantemoroso.

Um exemplo bem conhecido de uma relacao de recorrencia e a sucessao de Fibonacci,definida por

an = an!1 + an!2, n , 2,

com condicoes iniciais a0 = a1 = 1. Desta relacao de recorrencia nao e de todo obviaa expressao geral de an. De facto, para n , 0,

an =$n+1 # $n+1

/5

onde $ = 1+"

52 e $ = 1!

"5

2 sao as raızes da equacao x2 # x # 1 = 0. $ e o numero deouro.

Exercıcio. Calcular f(n, 2).

2 o processo

Tomemos o produto dos seguintes n factores

(1 + x + x2 + · · · )(1 + x + x2 + · · · ) · · · (1 + x + x2 + · · · ) (2.1)


onde x e uma variavel.Qual e o coeficiente de 1 = x0 no produto (2.1)? E 1 pois a unica forma de obter 1

no produto e escolher 1 em cada um dos factores. E o coeficiente de x? Para obter xtemos de escolher a parcela x num dos factores e a parcela 1 nos restantes n#1 factores.Isto pode ser feito de 1 + 1 + · · · + 1 = n formas, logo ao multiplicar a expressao (2.1)obtemos precisamente n parcelas da forma x. Ou seja, o coeficiente de x em (2.1) e n.Para obter x2 em (2.1) temos duas possibilidades: escolher a parcela 1 em n # 1 dosfactores e a parcela x2 no factor restante, que pode ser feito de n formas distintas, ouescolher a parcela x em dois dos factores e a parcela 1 nos restantes, que pode ser feitode

!n2

"formas distintas. Assim, o coeficiente de x2 em (2.1) e

n +

#n

2

$=

#n

1

$+

#n

2

$=

#n + 1

2

$.

Em geral, qual sera o coeficiente de xk em (2.1)? Se escolhermos a parcela xa1

do primeiro factor, xa2 do segundo, . . . , xan do ultimo factor, obtemos a parcelaxa1+···+an , logo o coeficiente de xk em (2.1) e o numero de escolhas diferentes de intei-ros a1, . . . , an , 0 que satisfazem a1 + · · · + an = k. Como vimos atras, este valor eprecisamente f(n, k). Logo,

f(n, k) = coeficiente de xk em (2.1)

= coeficiente de xk em (1# x)!n,

ja que

(1 + x + x2 + · · · )(1# x) = (1 + x + x2 + · · · )# (x + x2 + x3 + · · · ) = 1,

donde deduzimos que1 + x + x2 + · · · = (1# x)!1.

Assim, obtivemos a seguinte formula:

(1# x)!n = f(n, 0) · 1 + f(n, 1)x + f(n, 2)x2 + · · · + f(n, k)xk + · · ·

=%

k#0

f(n, k)xk.

No entanto, ainda nao temos uma formula fechada para f(n, k).

3 o processo

O que distingue resultados diferentes e o numero de ovos de cada cor, isto e, os va-lores de x1, x2, . . . , xn. Imaginemos os ovos ja pintados. Podemos alinha-los colocandoprimeiro os da cor 1, introduzir um separador, de seguida os de cor 2 e um separador,


etc., ate chegar aos ovos de cor n. Podemos esquematizar o que fizemos numa figurado tipo

0 · · · 0& '( )x1

| 0 · · · 0& '( )x2

| |&'()x3=0

0 · · · | 0&'()xn=1

onde “0” representa um ovo e “|” um separador. Usamos o sımbolo “0” k vezes e osımbolo “|” n # 1 vezes. Reciprocamente, a cada sequencia deste genero correspondeuma unica escolha para x1, x2, . . . , xn. Por exemplo, se n = 5 e k = 4, a sequencia

0 | 00 | 0 | |

representa x1 = 1, x2 = 2, x3 = 1, x4 = 0, x5 = 0, ou seja, um ovo da cor 1, dois ovosda cor 2, um ovo da cor 3 e nenhum ovo das cores 4 ou 5.

Reduzimos assim o nosso problema a enumeracao de todas as sequencias possıveisformadas pelos sımbolos “0” e “|”, de comprimento n + k# 1, usando o sımbolo “0” kvezes e o sımbolo “|” n# 1 vezes. Quantas sequencias ha? Temos n + k # 1 posicoes,e basta decidirmos em quais destas e que sao inseridos os n # 1 sımbolos “|”. Logo,f(n, k) =

!n+k!1

n!1

"=

!n+k!1

k

".

Como ja sabıamos, f(n, 1) =!

n1

"= n, f(1, k) =

!k0

"= 1, f(2, 2) =

!32

"= 3 e

f(n# 1, k) + f(n, k # 1) =

#n + k # 2

k

$+

#n + k # 2

k # 1

$=

#n + k # 1

k

$= f(n, k).


2.6 Exercıcios

1. Resolva a relacao de recorrencia an = n2an!1, com a1 = 1.

2. Sabendo que an = n!1n an!1 e que a1 = 2, determine an.

3. Sabendo que an = an!1 + n, determine an se (a) a1 = 1, (b) a1 = 0.

4. Sao dadas n jaulas dispostas uma a seguir a outra e e necessario colocar nelas kleoes indistinguıveis de forma a que nenhuma jaula fique com mais de um leao eque nao haja jaulas consecutivas com leoes. Seja g(n, k) o numero de maneirasde assim distribuir os leoes pelas jaulas. Mostre que:

(a) g(2k # 1, k) = 1;

(b) g(n, k) = 0 se n < 2k # 1;

(c) g(n, 1) = n;

(d) g(n, k) = g(n # 2, k # 1) + g(n # 1, k) se k , 2 [Sugestao: considere aspossibilidades de a ultima jaula ter ou nao um leao.];

(e) Deduza que: (i) g(6, 3) = 4; g(2k, k) = g(2k#2, k#1)+1; g(2k, k) = k+1.

5. Admita que t(n, n # 1) = 1 e que (n # k # 1)t(n, k) = k(n # 1)t(n, k + 1), parak < n# 1. Deduza que

t(n, k) =(n# 1)n!k!1(n# 2)!

(k # 1)!(n# k # 1)!.

6. Expanda (1# x)!3 em potencias de x ate ao termo em x5.

7. Seja h(n, k) o numero de maneiras de colorir k objectos identicos com n cores,usando cada cor pelo menos uma vez. Conclua que:

(a) h(n, k) = 0 se n > k;

(b) h(n, k) e o coeficiente de xk em (x + x2 + x3 + · · · )n;

(c) h(n, k) e o coeficiente de xk!n em (1# x)!n;

(d) h(n, k) = f(n, k # n);

(e) h(n, k) =!

k!1n!1

"se n " k;

(f) Calcule h(5, 10).

8. Expresse, em termos da funcao f(n, k) usada na seccao 2.5:

(a) o numero de sequencias de 0’s e 1’s de comprimento 10 contendo exactamentecinco 0’s;


(b) o numero de solucoes da equacao x + y + z = 24: (i) nos numeros inteirosnao negativos; (ii) nos numeros inteiros positivos;

(c) o numero de padroes distintos que e possıvel obter ao lancar tres dadosidenticos;

9. Mostre que o produto de r inteiros consecutivos e divisıvel por r!.

10. De quantas formas distintas e que se podem pintar as faces de um cubo usandocada uma de seis cores disponıveis?

11. Sete amigos querem organizar sete jantares entre eles. A cada jantar vao trespessoas de cada vez e, para evitar a monotonia, nao se repetem pares de pessoasem jantares diferentes. De quantas maneiras diferentes e que eles podem planearos jantares?


(a) De quantas maneiras e possıvel escolher um livro de latim e um livro de gregode um conjunto de 5 livros de latim distintos e 7 livros de grego distintos?

(b) De quantas maneiras e possıvel formar uma palavra de 2 letras?

(c) De quantas maneiras e possıvel formar uma palavra de 2 letras distintas?

(d) De quantas maneiras e possıvel formar uma palavra de 2 letras consistindonuma consoante seguida de uma vogal?

(e) De quantas maneiras e possıvel escolher um rapaz e uma rapariga de umgrupo de 3 rapazes e 8 raparigas?

(f) De quantas maneiras diferentes e que duas pessoas se podem sentar numafila de 5 cadeiras livres?

(g) De quantas maneiras diferentes e que se podem escolher 2 cadeiras de 5cadeiras dispostas em fila?

(h) De quantas maneiras e possıvel formar uma palavra de 4 letras?

(i) De quantas maneiras e possıvel escolher um elemento de uma matriz 5! 7?

(j) De quantas maneiras e possıvel escolher um elemento de uma matriz m!n?

(k) Quantos resultados se podem obter atirando uma moeda ao ar e lancandoum dado?

(l) Quantos resultados se podem obter atirando uma moeda ao ar, lancandoum dado e escolhendo uma carta de um baralho?

(m) De quantas formas e que se podem ordenar os as de um baralho de cartas?


(n) De quantas formas e que se podem ordenar as cartas de espadas de umbaralho de cartas?

13. Determine o numero de solucoes da inequacao

x1 + x2 + x3 + x4 + x5 + x6 < 91

(a) nos numeros inteiros positivos.

[Sugestao: Considere a equacao x1 + x2 + x3 + x4 + x5 + x6 + x7 = 91.]

(b) nos numeros inteiros nao negativos.


2.7 Permutacoes, arranjos, combinacoes

Temos n objectos dos quais queremos escolher k. De quantas formas distintas o pode-mos fazer? Ao nıvel mais simples, a resposta dependera essencialmente de dois factores:se a escolha e ordenada ou nao e se sao ou nao permitidas repeticoes.

Comecemos por ver de quantas formas diferentes podemos ordenar um conjuntocom n elementos. Para o primeiro elemento temos n possibilidades, restando n # 1elementos no conjunto. Para o segundo elemento temos n # 1 possibilidades, e assimsucessivamente. Ao fim de termos escolhido o (n # 1)-esimo elemento, restara umelemento, que e a unica possibilidade para o ultimo elemento da sequencia. Logo, peloprincıpio da multiplicacao, existem

n(n# 1) · · · 2 · 1 = n!

formas distintas de ordenar os elementos de um conjunto com n elementos (distintos).Uma ordenacao diz-se uma permutacao do conjunto. Nesta linguagem, existem n!

permutacoes de um conjunto com n elementos.

Exemplo. O jornal Publico quer publicar nas suas proximas 18 edicoes de Domingoum artigo sobre cada um dos clubes de futebol da 1 a divisao nacional. De quantasformas diferentes o pode fazer? E se o 3 o artigo tiver de ser sobre o Uniao de Leiria?E se o Boavista e a Academica tiverem de aparecer em semanas consecutivas?

Exemplo. De quantas formas distintas se podem sentar n pessoas numa mesa redonda?

Exemplo. O professor da disciplina de Portugues pediu a cada um dos seus alunospara expor duas obras de literatura portuguesa de movimentos literarios diferentes. Osmovimentos possıveis sao: romantismo, para o qual disponibilizou uma lista de setelivros; realismo, tendo para este movimento disponibilizado uma lista de cinco livros;modernismo, com uma lista de quatro livros possıveis.

Quantas escolhas diferentes podem os alunos fazer? Qual e a probabilidade de umadas obras ser do movimento realista?

Se tivermos um conjunto com n elementos e apenas quisermos escolher k deles deforma ordenada temos, ainda pelo princıpio da multiplicacao,

n(n# 1) · · · (n# (k # 1)) =n!

(n# k)!

formas de o fazer. Por exemplo, num inquerito sobre audiencias os inquiridos tem deseleccionar, por ordem de preferencia, as quatro series televisivas que mais veem, deentre uma lista de dez series. Assim, ha 10!

6! respostas possıveis.

Suponhamos que temos objectos que nao sao todos distintos. (Por exemplo, umtubo cheio de smarties, em que apenas distinguimos smarties de cores diferentes.) Mais


precisamente, digamos que de n objectos de que dispomos, q1 sao do tipo 1, q2 sao dotipo 2, . . . , e qk sao do tipo k, onde, claro esta, q1 + · · · + qk = n. De quantas formasdiferentes os podemos ordenar?

Comecamos por imaginar que os objectos foram rotulados de forma a ser possıveldistinguir, temporariamente, objectos do mesmo tipo. Ha neste caso n! formas deos ordenar. Quando “apagamos” todos os rotulos aos objectos, verificamos que cadasequencia de objectos nao rotulados da origem a q1!! · · ·! qk! sequencias de objectosrotulados. Logo, ha

n!

q1! · · · qk!

sequencias distintas de q1 objectos de tipo 1, q2 objectos de tipo 2, etc. Este numerodiz-se um coeficiente multinomial e denota-se por

#n

q1, . . . , qk

$.

Exemplo. Quantas “palavras” e possıvel construir usando as letras de cada uma dasseguintes palavras?

(a) bola;

(b) bolo;

(c) matematica: (i) ignorando o acento; (ii) nao ignorando o acento;

(d) combinatoria: (idem).

Exemplo. Quantas sequencias binarias de cinco algarismos e possıvel escrever usandoo algarismo 0 no maximo quatro vezes e o algarismo 1 no maximo tres vezes?

Suponhamos agora que nao estamos limitados no numero de objectos de cada tipoa usar. Assim, queremos saber quantas sequencias distintas de n objectos e possıvelconstruir, usando objectos de r tipos diferentes, com repeticao ilimitada. Temos r pos-sibilidades para o primeiro objecto, r para o segundo objecto, e assim sucessivamente,ate escolhermos de que tipo e o n-esimo objecto. Logo, o numero de tais sequencias ern.

Seja!

nk

"o numero de formas de escolher k objectos distintos de entre n objectos

distintos disponıveis. Entao, como nao nos interessa a ordem por que foram escolhidosesses k objectos, temos #

n

k

$· k! =

n!

(n# k)!


Isto porque cada escolha nao ordenada de k objectos distintos de entre n da origem ak! escolhas ordenadas, e o numero total de escolhas ordenadas e n!

(n!k)! . Logo,

#n

k

$=

n!

k!(n# k)!

Outra forma de obter este resultado e a seguinte: A cada escolha nao ordenadade k objectos de entre n fazemos corresponder uma sequencia ordenada de 0’s e 1’s,em que ocorre um 1 na i-esima posicao se o i-esimo objecto for escolhido e um 0 casocontrario. Obtemos assim uma correspondencia entre escolhas nao ordenadas de kobjectos e sequencias de 0’s e 1’s de comprimento n, com k 1’s e n# k 0’s. O numerode tais sequencias ja foi determinado e e o coeficiente multinomial

!n

k,n!k

"= n!

k!(n!k)! .

Nota.!

nk

"=

!n

n!k

", uma vez que escolher k objectos de n e o mesmo que escolher os

n# k objectos que nao sao seleccionados.

Exemplo. De quantas formas e possıvel escolher tres numeros diferentes entre 1 e 300de tal forma que a sua soma seja um multiplo de 3?

Comecemos por dividir o conjunto dos numeros entre 1 e 300 em tres subconjuntosdisjuntos: os que sao divisıveis por 3, os que dao resto 1 quando divididos por 3 eos que dao resto 2 quando divididos por 3. Cada um destes subconjuntos tem cemelementos. As unicas formas de escolher tres numeros cuja soma e um multiplo de 3 ese os tres numeros pertencerem ao mesmo subconjunto ou se cada um pertencer a umsubconjunto distinto. Logo, ha

#100

3

$+

#100

3

$+

#100

3

$+ 1003

formas de escolher os numeros.

Resta-nos estudar o caso de escolhas nao ordenadas com repeticao ilimitada de kobjectos de entre objectos de n tipos distintos. Isto corresponde as solucoes da equacao

x1 + · · · + xn = k

no conjunto dos inteiros nao negativos, onde xi indica o numero de vezes que umobjecto de tipo i e escolhido. Como ja vimos na seccao 2.5, o numero de tais solucoese

f(n, k) =

#n + k # 1

n# 1

$=

#n + k # 1

k

$

Exemplo. O Joao quer comprar sete berlindes. Na loja onde os vai comprar existemberlindes de quatro tipos diferentes. Assim, o Joao tem

!107

"= 120 escolhas possıveis.


Temos portanto o seguinte quadro:

escolher k objectos numero de escolhas numero de escolhasde n ordenadas (arranjos) nao ordenadas (combinacoes)

sem repeticao n!(n!k)!

!nk

"

com repeticao nk!

n+k!1k

"

Quando temos objectos, em quantidades limitadas, de k tipos diferentes, o numerode escolhas possıveis de objectos de entre eles e

(n1 + 1) · · · (nk + 1)

onde ni e o numero de objectos disponıveis de tipo i. Isto resulta do princıpio damultiplicacao, ja que para objectos do tipo 1 temos n1 + 1 possibilidades de escolha,entre 0 e n1 objectos, e analogamente para objectos de tipo 2, etc.

Exemplo. A Joana foi a padaria comprar pao. A padeira ainda tinha para vender 10paes biju, 3 cacetes, 1 pao de forma e 2 paes da avo. Ja nao havia pao integral. Qual ea probabilidade de a Joana sair da padaria com exactamente 2 paes biju e pelo menosum pao da avo?

Exemplo. Quantos divisores tem o numero 1400?A factorizacao de 1400 em primos e 23527, logo os divisores de 1400 sao os numeros

da forma 2a5b7c com 0 " a " 3, 0 " b " 2 e 0 " c " 1. Logo, 23527 tem (3 + 1)(2 +1)(1 + 1) = 24 divisores.

Exemplo. Temos 10 bandeiras diferentes que devem ser hasteadas em 6 mastros, sendoque nem todos os mastros tem de ser usados. De quantas formas e que podemos hastearessas bandeiras?

Precisamos apenas de escolher um dos 6 mastros para a primeira bandeira, um dos6 mastros para a segunda bandeira, etc., o que pode ser feito de 610 formas distintas.

No exemplo anterior, as escolhas de mastros para as bandeiras nao reflectiu o factode que se 2 ou mais bandeiras forem hasteadas no mesmo mastro entao terao de fi-car a alturas diferentes no mastro. Tomando isto em consideracao, cada atribuicaode bandeiras a mastros da ainda origem a varias configuracoes diferentes. Quantasconfiguracoes existem no total? Reformulemos o problema.

Temos n objectos distintos que queremos colocar em k caixas distintas, considerandoordem dentro de cada caixa. Esta situacao pode ser modelada por uma sequenciade comprimento n + k # 1 cujos elementos sao os n objectos e k # 1 separadoresentre as caixas. Se os separadores fossem distintos, terıamos um total de (n + k # 1)!sequencias. Identificando, como deverıamos, os separadores, temos (n+k!1)!

(k!1)! sequencias


distintas, sendo esse o numero de maneiras de colocar os n objectos distintos em kcaixas distintas, com ordem dentro de cada caixa.

Assim, para o exemplo anterior, assumindo que e necessario decidir a que alturarelativa nos mastros se dispoem as bandeiras, ha 15!

5! escolhas possıveis.

Exemplo. Pretende-se enviar 5 letras diferentes (ja escolhidas) atraves de um canalde comunicacao. Entre essas letras devem ser inseridos um total de 15 espacos embranco, sendo cada par de letras separadas por um mınimo de 3 espacos em branco.De quantas formas diferentes podem as letras e os espacos ser dispostos?

Se as letras nao fossem distintas, existiriam!15!12+3

3

"=

!63

"= 20 formas de o fazer.

Sendo as letras distintas, ha um total de 5!20 formas de dispor as letras e os espacos.

Pensemos agora no seguinte problema: Dos subconjuntos de {1, . . . , n} com k ele-mentos (0 " k " n) quantos e que nao contem numeros consecutivos?

Sem impor a restricao de nao haver numeros consecutivos, a resposta seria!

nk

".

Uma das formas de chegar a esta conclusao e pensar num subconjunto de {1, . . . , n}como uma sequencia de 0’s e 1’s cujo i-esimo algarismo e 1 se o inteiro i pertencer aosubconjunto em questao e 0 caso contrario. Desta forma, estabelece-se uma bijeccaoentre o conjunto dos subconjuntos de {1, . . . , n} com k elementos e o conjunto dassequencias binarias de comprimento n em que o sımbolo 1 ocorre k vezes e o sımbolo0 ocorre n# k vezes. O numero de tais sequencias e

!nk

".

Ao restringir esta correspondencia aos subconjuntos de k elementos sem inteirosconsecutivos obtemos exactamente as sequencias binarias de comprimento n nas quais1 ocorre k vezes, 0 ocorre n#k vezes e nao ha dois 1’s consecutivos. Quantas sequenciasdeste tipo havera? Uma tal sequencia e construıda inserindo os k sımbolos 1 nos espacosentre os n# k sımbolos 0, incluindo os espacos que antecedem e sucedem a sequenciade 0’s:

0 0 · · · 0

Como ha n#k+1 espacos e k sımbolos 1 a introduzir, no maximo um em cada espaco,ha

!n!k+1

k

"formas de o fazer. Temos entao o seguinte resultado:

Lema 2.3 (Kaplansky). O numero de subconjuntos de {1, . . . , n} com k elementos esem inteiros consecutivos e

!n!k+1

k

".

Exemplo. Quantas palavras e que se podem formar usando todas as letras da palavraINIMAGINAVEIS sem que haja dois I’s adjacentes e ignorando o acento?

Escolhemos primeiro a localizacao dos quatro I’s de entre as 13 posicoes possıveis.Como nao devem ocorrer I’s consecutivos, ha

!104

"= 210 posicoes possıveis. Resta

agora dispor as restantes letras, o que pode ser feito de 9!2!2! formas. Logo, ha 210 9!

2!2!palavras possıveis, sem I’s adjacentes.


Exemplo. Um relogio de cuco antigo esta um pouco avariado e apenas assinala ashoras 4 vezes ao dia, nunca o fazendo, no entanto, em horas consecutivas. De quantasformas distintas e que o relogio pode tocar (o relogio repete o mesmo padrao todos osdias)?

Este problema e analogo ao anterior no sentido em que estamos interessados emsaber quantos subconjuntos de {1, . . . , 24} com 4 elementos nao consecutivos e queexistem. No entanto, ha uma diferenca significativa, uma vez que para este problemadevemos considerar os numeros 24 e 1 como sendo consecutivos, ja que uma hora depoisda meia noite e uma hora da manha. Somos portanto levados a considerar o seguinteresultado, cuja prova e deixada como exercıcio.

Lema 2.4 (Kaplansky). O numero de subconjuntos de {1, . . . , n} com k elementose sem inteiros consecutivos, considerando n e 1 como sendo inteiros consecutivos, e

nn!k

!n!k

k

".


2.8 Exercıcios


(a) De quantas formas e possıvel ordenar as 6 letras da palavra ABCDEF?

(b) De quantas formas e possıvel ordenar as 6 letras da palavra A1A2A3E4E5F?

(c) De quantas formas e possıvel ordenar as 6 letras da palavra A1A2A3EEF?

(d) De quantas formas e possıvel ordenar as 6 letras da palavra AAAE4E5F?

(e) De quantas formas e possıvel ordenar as 6 letras da palavra AAAEEF?

(f) De quantas formas e possıvel ordenar as letras da palavra BANANA?

(g) De quantas formas e possıvel ordenar as letras da palavra AAABBCCCCD?

(h) De quantas formas e possıvel ordenar as letras da palavra MISSISSIPPI?

(i) De quantas formas e que se podem ordenar 4 A’s, 3 G’s e as 6 letras S, T,U, V, X, Z?

(j) De quantas formas e possıvel dispor numa prateleira 4 exemplares de umlivro de algebra, 3 exemplares de um livro de geometria e 6 romances decordel diferentes?

(k) De quantas formas e possıvel dispor numa prateleira 4 livros de algebradistintos, 3 livros de geometria distintos e 6 livros de calculo distintos deforma a que livros sobre o mesmo assunto fiquem juntos?

(l) Quantas palavras de n letras e que tem r C’s e n# r R’s?

2. De quantas formas e que se podem ordenar as 23 letras do alfabeto de forma aque: (i) as 5 vogais aparecam todas juntas; (ii) as letras A e B nao aparecamjuntas.

3. Quantos colares distintos de n missangas e possıvel formar usando uma missangade cada uma de n cores?

4. O Antonio tem 75 livros mas apenas 20 destes cabem na sua prateleira. Dequantas forma e que pode encher a prateleira com os livros?

5. Quantos numeros entre 1000 e 3000 e que e possıvel formar com os dıgitos1, 2, 3, 4, 5: (i) com possibilidade de repeticao de dıgitos; (ii) sem possibilidadede repeticao de dıgitos.

6. Em musica serial dodecafonica, as 12 notas da escala cromatica sao dispostas emlinha e tocadas nessa ordem. Quantas linhas sao possıveis?


7. Uma comissao de 12 pessoas tem de designar de entre os seus membros umPresidente, um Secretario e um Tesoureiro. De quantas formas e que isso podeser feito?

8. De quantas maneiras e possıvel formar uma palavra de 5 letras (de entre as23 letras do alfabeto): (i) com possibilidade de repeticao de letras; (ii) semrepeticao de letras.

9. Mostre que:

(a)!

nk

"=

!k!1k!1

"+

!k

k!1

"+

!k+1k!1

"+ · · · +

!n!1k!1

";

(b)!

n+m+1m

"=

!n0

"+

!n+1

1

"+

!n+2

2

"+ · · · +

!n+m

m

".

10. Responda as seguintes questoes de forma rapida, clara e concisa.

(a) De quantas formas e que 8 casais se podem sentar a volta de uma mesaredonda de forma a que os membros de cada casal fiquem juntos?

(b) De quantas formas e que 4 Americanos, 7 Belgas e 10 Portugueses se podemsentar a volta de uma mesa redonda?

(c) De quantas formas e que se podem ordenar 4 C’s e 8 R’s de forma a quenao haja C’s adjacentes?

(d) De quantas formas e possıvel escolher 5 de 11 professores para uma comissaode acompanhamento de alunos com necessidades especiais?

(e) Quantos full houses (tres cartas do mesmo valor facial e um par do mesmovalor facial, distinto do valor facial das tres cartas anteriores) existem nopoker?

(f) De quantas formas e que o Armindo pode convidar alguns dos seus 10 amigospara jantar, se convidar pelo menos 1 dos seus amigos?

(g) De quantas formas e que se podem arranjar as letras de DABBADABBA?

(h) Existem em casa do Duarte 5 livros de algebra, 7 de geometria e 4 de calculo.Os livros sao todos distintos. De quantas formas e possıvel escolher destes2 livros, nao ambos da mesma area?

(i) Quantas das permutacoes das 23 letras do alfabeto e que nao tem vogaisadjacentes?

(j) Quantas palavras de 10 letras e que nao tem letras iguais adjacentes?

(k) Quantos conjuntos de 10 letras do alfabeto e que tem letras consecutivas?

(l) De quantas formas e que 5 homens e 7 mulheres se podem sentar em filasem que dois homens fiquem juntos?


(m) De quantas formas e que 5 homens e 7 mulheres se podem sentar a volta deuma mesa redonda sem que dois homens fiquem juntos?

11. De quantas formas e que se podem hastear em 15 postes distintos, 5 bandeirasvermelhas identicas, 7 bandeiras azuis identicas e 11 bandeiras distintas (entre sie tambem distintas das anteriores)? Interessa a ordem das bandeiras nos postese nem todos os postes tem de ter bandeiras.

12. Determine o numero de solucoes, nos inteiros, da equacao

x + y + z + w = 50

sujeitas as restricoes adicionais x > 3, y > #4, z , 1 e w > #6.

13. De quantas formas diferentes e que 7 carros podem passar por 5 filas de portagem?

14. Prove o Lema 2.4.

15. Quantos triangulos e que se podem formar a partir de vertices nao adjacentes deum polıgono regular de n lados?

16. Quantas sequencias e possıvel formar usando a vezes o algarismo 0, b vezes oalgarismo 1 e c vezes o algarismo 2 de forma a que nao haja nenhum par de 0’sconsecutivos?

17. Quantos subconjuntos de {1, . . . , n} com k elementos e que existem, de forma aque entre dois quaisquer elementos do subconjunto haja pelo menos r elementosque nao lhe pertencam (isto e, tal que entre dois elementos haja uma diferencade pelo menos r + 1 unidades)?


2.9 Os teoremas binomial e multinomial

Vejamos agora algumas aplicacoes simples do que fizemos ate agora. Como alternativaa mais habitual prova por inducao do teorema binomial, apresentaremos de seguidauma prova combinatoria deste resultado, que se apresenta bastante mais simples e queadmite uma generalizacao natural – o teorema multinomial.

Teorema 2.5. Sejam n , 0 um inteiro e x, y numeros reais (ou complexos ou, maisgeralmente, elementos de um anel comutativo). Entao:

(x + y)n =n%

k=0

#n

k

$xkyn!k

Demonstracao. Ao usar a distributividade do produto relativamente a adicao na ex-pressao

(x + y)(x + y) · · · (x + y)& '( )n factores

(2.2)

e a comutatividade do produto, obtemos uma soma cujas parcelas sao da forma xkyl.Alem disso, como ha n factores em (2.2), k + l = n, isto e, l = n# k. Logo,

(x + y)n =n%

k=0

c(k)xkyn!k,

onde c(k) e o numero de vezes que e obtida a parcela xkyn!k ao efectuar a multiplicacao(2.2). Ora, para obter xkyn!k temos de escolher a parcela x em k dos factores de(2.2). Isto pode ser feito precisamente de

!nk

"formas, logo c(k) =

!nk

"e (x + y)n =*n

k=0

!nk

"xkyn!k.

Mais geralmente, podemos provar o teorema multinomial:

Teorema 2.6. Sejam n , 0 e k , 1 inteiros e x1, . . . , xk numeros reais (ou complexosou, mais geralmente, elementos de um anel comutativo). Entao:

(x1 + · · · + xk)n =

%

a1, . . . , ak # 0a1 + · · · + ak = n

#n

a1, . . . , ak

$xa1

1 · · ·xakk

Demonstracao. Ao expandir o produto

(x1 + · · · + xk) · · · (x1 + · · · + xk) (2.3)

as parcelas que obtemos sao da forma xa11 · · ·xak

k , com a1, . . . , ak , 0 e a1+· · ·+ak = n,o numero de factores de (2.3). Resta-nos determinar de quantas formas diferentes podeser obtida a parcela xa1

1 · · ·xakk . Para tal, temos de escolher os a1 factores em que

tomamos a parcela x1, os a2 factores em que tomamos a parcela x2, etc. Isto, como javimos, pode ser feito de n!

a1!···ak! =!

na1,...,ak

"formas.


Proposicao 2.7. Sejam n um inteiro positivo e x um numero real ou complexo tal que|x| < 1. Entao

(1# x)!n =+$%

k=0

#n + k # 1

k

$xk

= 1 +

#n

1

$x +

#n + 1

2

$x2 +

#n + 2

3

$x3 + · · ·

Demonstracao. Ja vimos que o coeficiente de xk no produto dos n factores

(1 + x + x2 + · · · )(1 + x + x2 + · · · ) · · · (1 + x + x2 + · · · )

e!

n+k!1k

", o que prova o teorema, ja que (1#x)!1 = 1+x+x2 + · · · , para |x| < 1.

Este resultado motiva a seguinte definicao, que estende a definicao dos coeficientesbinomiais

!nk

"para valores arbitrarios de n ' R e k ' N.

#n

k

$=

n(n# 1) · · · (n# k + 1)

k!, se k , 1 e

#n

0

$= 1.

Temos assim, por exemplo,#

1/2

3

$=

1/2(1/2# 1)(1/2# 2)

3!= 1/16,

#4

6

$=

4 · 3 · 2 · 1 · 0 · (#1)

6!= 0,

##n

k

$=#n(#n# 1) · · · (#n# k + 1)

k!= (#1)k n(n + 1) · · · (n + k # 1)

k!

= (#1)k

#n + k # 1

k

$. (2.4)

Teorema 2.8. Sejam n ' Z um inteiro qualquer e x um numero real ou complexo talque |x| < 1. Entao

(x + 1)n =+$%

k=0

#n

k

$xk. (2.5)

Demonstracao. Se n , 0 entao!

nk

"= 0 para k > n e assim a equacao (2.5) resume-se ao

Teorema 2.5, com y = 1. Se n < 0 entao podemos usar a Proposicao 2.7, substituindo


x por #x e #n por n, juntamente com a igualdade (2.4), para concluir que de facto

(x + 1)n =+$%

k=0

##n + k # 1

k

$(#x)k

=+$%

k=0

(#1)k

##n + k # 1

k

$xk

=+$%

k=0

#n

k

$xk.

Exemplo. Seja X um conjunto com n elementos. Entao o numero de subconjun-tos de X com k elementos e

!nk

", por definicao de

!nk

". Em particular, o numero de

subconjuntos de X e

#n

0

$+

#n

1

$+ · · · +

#n

n

$=

n%

k=0

#n

k

$= (1 + 1)n = 2n.

Exemplo. Determinemos o numero total de subconjuntos de {1, . . . , n}, onde n e uminteiro positivo, que nao contem inteiros consecutivos (nao consideramos os inteiros 1e n como sendo consecutivos). Note-se que o conjunto vazio e um destes subconjuntos.Entao, pelo Lema 2.3, o numero que procuramos e:

%

k#0

#n# k + 1

k

$.

Seja, para n , 0,

Fn =%n/2&%

k=0

#n# k

k

$=

#n

0

$+

#n# 1

1

$+

#n# 2

2

$+ · · ·

A sucessao Fn consiste nas somas dos elementos das diagonais do triangulo de Pascal.


Note-se que F0 =!00

"= 1 =

!10

"= F1 e que

Fn + Fn+1 =%

k#0

#n# k

k

$+

%

l#0

#n + 1# l

l

$

=%

k#0

+#n# k

k

$+

#n# k

k + 1

$,+

#n + 1

0

$

=%

k#0

#n + 2# (k + 1)

k + 1

$+ 1

=%

k#0

#n + 2# k

k

$

= Fn+2

Logo, (Fn)n#0 e a sucessao de Fibonacci.Assim, o numero total de subconjuntos de {1, . . . , n} que nao contem inteiros con-

secutivos e Fn+1, o (n + 1)-esimo numero de Fibonacci.

Exemplo. Considere-se a expansao binomial de (10 + 1)n:

11n =

#n

0

$10n +

#n

1

$10n!1 + · · · +

#n

n# 1

$10 +

#n

n

$.

Assim, as linhas do triangulo de Pascal permitem calcular a representacao decimal daspotencias de 11. Por exemplo, como a 6 a linha do triangulo de Pascal e

1 5 10 10 5 1

podemos concluir que 115 = 161051.


2.10 Exercıcios

1. Usando a identidade(1 + x)2n = (1 + x)n(1 + x)n

e considerando em ambos os membros o coeficiente de xn, mostre que

#2n

n

$=

#n

0

$2

+

#n

1

$2

+

#n

2

$2

+ · · · +#

n

n

$2

.

Verifique esta igualdade para n = 5.

2. Apresente uma prova combinatoria da identidade

n%

k=0

#a

k

$#b

n# k

$=

#a + b

n

$.

Observe que se a = b = n obtemos a identidade do exercıcio 1.

3. Mostre que!

n+13

"#

!n!1

3

"= (n# 1)2.

4. Mostre que, em cada uma das linhas do triangulo de Pascal, o numero maior e o(resp. sao os) do meio, isto e, mostre que

!nr

">

!n

r!1

"se r " 1

2(n + 1).

5. Mostre que, para n > 2 e 1 < k < n# 1, se tem sempre!

k2

"+

!n!k

2

"<

!n!1

2

".

6. Mostre que!

nr

"2>

!n

r!1

"!n

r+1

", para n > r.

7. Mostre que:

(a)!

n0

"#

!n1

"+

!n2

"# · · · + (#1)n

!nn

"= 0;

(b)!

n0

"+

!n2

"+

!n4

"+ · · · =

!n1

"+

!n3

"+

!n5

"+ · · · = 2n!1.

8. Calculen%

k=1

k

#n

k

$,

derivando ambos os membros da expansao binomial de (1 + x)n e fazendo asubstituicao x = 1.

9. Calcule, de forma analoga ao que e sugerido no exercıcio 8, as seguintes somas:

(a)*n

k=0(#1)k!1k!

nk

";

(b)*n

k=01

k+1

!nk

".


10. Dados 0 " s " k " r " n, mostre que#

n

r

$#r

k

$#k

s

$=

#n

s

$#n# s

k # s

$#n# k

r # k

$.

11. Dado n , 3, calcule o valor de

1 · 2 · 3 + 2 · 3 · 4 + 3 · 4 · 5 + · · · + (n# 2) · (n# 1) · n.

12. Considere a seguinte rede de estradas:

No Ponto inicial O encontram-se 2a soldados. Metade destes segue na direccao SOe a outra metade na direccao SE. Chegando a uma nova interseccao, cada grupode soldados divide-se novamente em dois, metade seguindo na direccao SO e aoutra metade na direccao SE. Quantos soldados chegam ao k-esimo cruzamentoda linha n? [Sugestao: Considere a posicao inicial de O como sendo o cruzamento0 da linha 0.]


2.11 O princıpio do pombal

Temos N objectos que queremos distribuir de alguma forma por k caixas, podendoeventualmente deixar algumas caixas vazias ou colocar todos os objectos na mesmacaixa. Se N > k entao, independentemente da forma como o fizermos, alguma caixatera pelo menos dois objectos. Mais geralmente, se N > km para algum inteiro naonegativo m, entao alguma das caixas tera pelo menos m + 1 objectos. Se assim naofosse, entao cada caixa conteria no maximo m objectos e o numero total de objectosnao excederia mk, contrariando a hipotese sobre N .

O princıpio ilustrado acima chama-se usualmente princıpio do pombal, ou princıpiodas caixas de Dirichlet, por poder ser formulado em termos de pombas (respecti-vamente, objectos) e pombais (respectivamente, caixas). Apesar de ser extrema-mente simples, tem inumeras aplicacoes nada obvias, como iremos ver de seguida.Comecamos, no entanto, com algumas aplicacoes imediatas.

Exemplo. Num grupo de 13 pessoas ha pelo menos duas pessoas com o mesmo signoastrologico.

Exemplo. Numa festa com 6 pessoas, existe necessariamente um grupo de 3 pessoasque se conhecem mutuamente ou um grupo de 3 pessoas que se desconhecem mutua-mente (estamos a assumir que a relacao de conhecer e simetrica).

Seja A uma das pessoa da festa. Dividimos as restantes 5 pessoas em dois grupos: ogrupo das que A conhece e o grupo das que A nao conhece. Pelo princıpio do pombal,algum destes grupos tem pelo menos 3 pessoas. Suponhamos, por exemplo, que o grupodas pessoas que A nao conhece tem pelo menos 3 pessoas, digamos B, C e D. Se B,C e D se conhecem mutuamente, entao ja temos um trio que se conhece mutuamente.Caso contrario, ha pelo menos um par de entre B, C e D que nao se conhece, digamosB e C. Entao A, B e C e um trio de desconhecidos. Fica assim provada a existenciade um trio de conhecidos ou de um trio de desconhecidos mutuos em qualquer grupode 6 pessoas.

Exemplo. Dados 5 pontos P1, . . . , P5 no interior de um quadrado de lado 1, algumpar deles esta a uma distancia inferior ou igual a

/2/2.

Se decompusermos o quadrado em 4 quadrados de lado 1/2, pelo menos dois dospontos dados estarao no mesmo quadrado de lado 1/2. Como o diametro de qualquerum destes quadrados e

/2/2, dois pontos no mesmo quadrado pequeno distam no

maximo/

2/2 um do outro.

Exemplo. Um jogador de xadrez quer treinar-se para um campeonato fazendo jogosde pratica nos proximos 77 dias. Ele quer jogar pelo menos um jogo por dia, mas naomais de 132 jogos no total dos 77 dias. Vamos ver que, independentemente do seuplano de treinos, havera um perıodo de dias consecutivos em que jogara precisamente21 jogos.


Seja ai o numero de jogos que ele faz desde o primeiro dia ate ao final do dia i.Entao a sucessao a1, a2, . . . , a77 e estritamente crescente, a1 , 1 e a77 " 132. A sucessaoa1 + 21, a2 + 21, . . . , a77 + 21 e ainda estritamente crescente e a77 + 21 " 153. Ora,os 77 ! 2 = 154 numeros a1, a2, . . . , a77, a1 + 21, a2 + 21, . . . , a77 + 21 nao podem sertodos distintos, ja que estao todos compreendidos entre 1 e 153. Logo, ha pelo menosdois iguais. Pela monotonia das sucessoes (ai)i e (ai + 21)i, os numeros iguais tem depertencer a sucessoes distintas. Logo ai = aj + 21 para alguns 1 " i, j " 77. Istosignifica que do dia j + 1 ao dia i o jogador joga exactamente 21 partidas de xadrez.

Exemplo. Seja a1, . . . , an uma sequencia de n numeros reais distintos e suponhamosque n > pq, para alguns inteiros positivos p e q. Vamos ver que: ou existe umasubsequencia crescente desta com pelo menos p+1 termos, ou existe uma subsequenciadecrescente desta com pelo menos q + 1 termos.

Suponhamos que nao ha nenhuma subsequencia crescente com p + 1 termos. Paracada i, seja xi o numero maximo de termos numa subsucessao crescente da sucessaodada comecando em ai. Por hipotese, 1 " xi " p para todo o 1 " i " n. Logo, comon > pq, ha pelo menos q + 1 termos da sucessao com o mesmo valor de xj. Estes q + 1termos formam necessariamente uma subsucessao decrescente de a1, . . . , an. De facto,se i < j e xi = xj entao nao pode acontecer ai < aj, pois tal implicaria a contradicaoxi , xj + 1.

Exemplo. Dois cırculos concentricos, um maior do que o outro, sao divididos em 200seccoes iguais. Das seccoes do disco exterior, 100 sao coloridas de vermelho e as 100restantes de azul. As seccoes do disco interior sao pintadas arbitrariamente de vermelhoe azul. Sera que e sempre possıvel rodar o cırculo interior de forma a que as cores dosdois cırculos coincidam em pelo menos 100 das seccoes? A figura abaixo ilustra asituacao descrita para 10 seccoes.

A resposta e afirmativa e passamos a prova-lo usando o princıpio do pombal. Fixe-se o disco exterior e comece-se a rodar o disco interior pelas 200 posicoes possıveis.Para cada uma das posicoes registe-se o numero de seccoes coincidentes. Se somarmostodos estes numeros ao percorrer as 200 posicoes, obtemos o numero 20000, pois cada


seccao interna coincide com exactamente 100 das seccoes externas, ao longo das variasposicoes que vai tomando. Assim, nalguma posicao tem de haver pelo menos 100seccoes coincidentes.

Exemplo. Dados n + 1 inteiros positivos entre 1 e 2n, ha algum deles que e multiplode outro.

Denotamos os n + 1 inteiros dados por x1, . . . , xn+1 e escrevemos, para cada i,xi = 2!iyi, com !i , 0 e yi ımpar. Como os yi sao n + 1 inteiros ımpares entre 1 e2n, nao podem ser todos diferentes. Logo existem ındices i -= j tais que yi = yj. Se!i " !j entao xj e multiplo de xi. Caso contrario, xi e multiplo de xj.

Exemplo. Seja S um subconjunto de {1, 2, . . . , 99} com 10 elementos. Mostrar queexistem subconjuntos nao vazios e disjuntos de S tais que a soma dos seus elementose igual.

O conjunto S tem 210#1 = 1023 subconjuntos nao vazios. A soma dos elementos dequalquer um desses subconjuntos e majorada por 90+91+ · · ·+99 < 10!100 = 1000.Logo, pelo princıpio do pombal, existem dois subconjuntos nao vazios e distintos de Scujas somas dos seus elementos coincidem, digamos X e Y . Estes conjuntos podem,no entanto, nao ser disjuntos, mas

A = X \ (X % Y ) e B = Y \ (X % Y )

sao disjuntos e a soma dos seus elementos e igual, ja que retiramos a X e a Y os mesmoselementos. Alem disso, se um destes conjuntos fosse vazio entao X 0 Y ou Y 0 X.Como

*x'X x =

*y'Y y e estes inteiros sao nao nulos, tal implicaria que X = Y , o

que e absurdo. Logo A e B tem a propriedade pretendida.


2.12 Exercıcios

1. Numa gaveta ha 10 meias brancas identicas e 10 meias pretas tambem identicas.Sem olhar para as meias, quantas meias e necessario retirar da gaveta para ga-rantir que se consegue um par de meias da mesma cor?

2. Quantas cartas e necessario retirar de um baralho de cartas para garantir que seretiram pelo menos duas cartas do mesmo naipe?

3. Quantas pessoas e necessario haver numa sala para garantir que pelo menos 3delas tem o mesmo dia de aniversario?

4. Quantas bolas e necessario retirar de um saco que contem 12 bolas vermelhas,20 bolas brancas, 7 bolas azuis e 8 bolas verdes para garantir que se tiram pelomenos 10 bolas da mesma cor?

5. Quantas pessoas devem ser escolhidas de entre n casais de forma a garantir quealgum casal e escolhido?

6. Mostre que numa sala com 20 pessoas ha pelo menos 2 pessoas com o mesmonumero de amigos na sala.

7. Considere todos os pontos do plano cujas coordenadas sao inteiros. Mostre quedados quaisquer 5 desses pontos, pelo menos 1 dos 10 segmentos que os unemcontem ainda algum ponto de coordenadas inteiras.[Sugest~ao: Considere os pontos medios dos segmentos.]

8. Sejam x1, . . . , xn inteiros arbitrarios. Mostre que existem i < j tais que xi +xi+1 + · · · + xj!1 e multiplo de n.

9. Usando o princıpio do pombal, mostre que a expansao decimal de um numeroracional e finita ou periodica.

10. Mostre que para qualquer inteiro N , existe um multiplo de N cuja representacaodecimal contem apenas os dıgitos 0 e 7. Por exemplo, se N = 3 entao 259! 3 =777; se N = 4 entao 1925! 4 = 7700.[Sugest~ao: Considerar as classes residuais modulo N dos seguintes inteiros:7, 77, . . . , 77 · · · 7& '( )

N algarismos

.]

11. Considere uma sequencia de N inteiros positivos contendo precisamente n inteirosdistintos. Mostre que se N , 2n entao existe um bloco de termos consecutivosda sequencia cujo produto e um quadrado perfeito.

Documents

Métodos Finitos em Matemática - arquivoescolar.org · maneiras distintas é ... quadrados do tabuleiro original tiverem alternadamente as cores ... Suponhamos que num determinado