Análise de Algoritmos - Indução Finita

Analise de Algoritmos

Indução finita

– p. 1/20

Indução finita

Princıpio da inducao matematica:

Seja A um conjunto de números naturais tal que asseguintes propriedades são válidas:

0 ! A, e

para cada natural n, se {0, 1, 2, . . . , n} " A

então n+ 1 ! A.

Então A = N.

– p. 2/20

Indução finita

Na prática, o princípio da indução é usado paraprovar afirmações do tipo “para todo natural n, apropriedade P (n) é verdadeira”, onde P é umapropriedade que depende de algum parâmetrointeiro. A prova é feita da seguinte forma.

– p. 3/20

Indução finita

Seja A = {n : P é verdadeira para n}.

1. Base da indução: mostramos inicialmente que0 ! A, ou seja, P é verdadeira para n = 0.

2. Hipótese de indução: assumimos que{0, 1, 2, . . . , n} " A, ou seja, que P é verdadeirapara cada natural 0, 1, 2, . . . , n.

3. Passo da indução: mostramos que n+ 1 ! A,ou seja, que P é verdadeira para n+ 1.

– p. 4/20

Indução finita

Pelo princípio da indução, A = N. Logo, P éverdadeira para todo n.

– p. 5/20

Indução finita - em outras palavras

O princípio da indução finita pode também serdescrito da seguinte forma:

“Se uma afirmação P , que envolve um parâmetrointeiro n, é verdade para n = 0, e se para n # 1, ahipótese de que P é verdadeira para todo inteiro$ n implica que P é verdadeira para n+ 1, então P

é verdadeira para todo natural n.

– p. 6/20

Indução finita - exemplos

Mostre que 1+ 2+ · · ·+n = n(n+1)2 , para todo n # 1.

– p. 7/20

Indução finita - exemplos

Mostre que 1+ 2+ · · ·+n = n(n+1)2 , para todo n # 1.

1. Base da indução: para n = 1 temos 1 = 1(1+1)2 .

– p. 7/20

Indução finita - exemplos

Mostre que 1+ 2+ · · ·+n = n(n+1)2 , para todo n # 1.

1. Base da indução: para n = 1 temos 1 = 1(1+1)2 .

2. Hipótese de indução: assumimos que1 + 2 + · · ·+ k = k(k+1)

2 , para todo k $ n.

– p. 7/20

Indução finita - exemplos

Mostre que 1+ 2+ · · ·+n = n(n+1)2 , para todo n # 1.

3. Passo da indução:

– p. 8/20

Indução finita - exemplos

Mostre que 1+ 2+ · · ·+n = n(n+1)2 , para todo n # 1.

3. Passo da indução:

1 + 2 + · · ·+ n+ (n+ 1) = (1 + 2 + · · ·+ n) + (n+ 1)

=n(n+ 1)

2+ (n+ 1)

=n(n+ 1) + 2(n+ 1)

2

=(n+ 1)(n+ 2)

2

– p. 8/20

Indução finita - exemplos

Afirmação: o número de diagonais de um polígonoconvexo P de n # 3 lados é d = n(n%3)

2 .

– p. 9/20

Indução finita - exemplos

Afirmação: o número de diagonais de um polígonoconvexo P de n # 3 lados é d = n(n%3)

2 .

Prova: Por indução em n. A afirmação éclaramente verdadeira para n = 3.

– p. 9/20

Indução finita - exemplos

Afirmação: o número de diagonais de um polígonoconvexo P de n # 3 lados é d = n(n%3)

2 .

Prova: Por indução em n. A afirmação éclaramente verdadeira para n = 3.

Sejam v1, v2, . . . , vn os vértices de P , enumeradosem uma ordem cíclica.

– p. 9/20

Indução finita - exemplos

Afirmação: o número de diagonais de um polígonoconvexo P de n # 3 lados é d = n(n%3)

2 .

Prova: Por indução em n. A afirmação éclaramente verdadeira para n = 3.

Sejam v1, v2, . . . , vn os vértices de P , enumeradosem uma ordem cíclica. Considere o polígono P &

de n% 1 lados formado pelos vérticesv1, v2, . . . , vn%1. Note que P & é convexo.

– p. 9/20

Indução finita - exemplos

Seja d& o número de diagonais de P &.

– p. 10/20

Indução finita - exemplos

Seja d& o número de diagonais de P &.Por hipótese de indução,

d& =(n% 1)(n% 4)

2.

– p. 10/20

Indução finita - exemplos

Seja d& o número de diagonais de P &.Por hipótese de indução,

d& =(n% 1)(n% 4)

2.

Mas, d = d& + (n% 2).

– p. 10/20

Indução finita - exemplos

Seja d& o número de diagonais de P &.Por hipótese de indução,

d& =(n% 1)(n% 4)

2.

Mas, d = d& + (n% 2). Logo,

d =(n% 1)(n% 4)

2+ (n% 2) =

n(n% 3)

2.

– p. 10/20

Indução finita - exemplos

Proposição: Seja G uma árvore com v # 1 vérticese a arestas então a = v % 1.

– p. 11/20

Indução finita - exemplos

Proposição: Seja G uma árvore com v # 1 vérticese a arestas então a = v % 1.

Prova: Por indução em a.

– p. 11/20

Indução finita - exemplos

Proposição: Seja G uma árvore com v # 1 vérticese a arestas então a = v % 1.

Prova: Por indução em a. Se a = 0 então v = 1,pois v # 1 e G é conexo. Logo, a = v % 1 nestecaso.

– p. 11/20

Indução finita - exemplos

Proposição: Seja G uma árvore com v # 1 vérticese a arestas então a = v % 1.

Prova: Por indução em a. Se a = 0 então v = 1,pois v # 1 e G é conexo. Logo, a = v % 1 nestecaso.

Suponha que a # 1. Seja e uma aresta de G.Como G é uma árvore, o grafo G% e é formado porexatamente duas componentes, digamos G1 e G2.Além disso, G1 e G2 são árvores.

– p. 11/20

Indução finita - exemplos

Sejam v1 e a1 o número de vértices e arestas deG1. Defina v2 e a2 similarmente para G2.

– p. 12/20

Indução finita - exemplos

Sejam v1 e a1 o número de vértices e arestas deG1. Defina v2 e a2 similarmente para G2.

Claramente, a1 < a e a2 < a. Por hipótese deindução, a1 = v1 % 1 e a2 = v2 % 1.

– p. 12/20

Indução finita - exemplos

Sejam v1 e a1 o número de vértices e arestas deG1. Defina v2 e a2 similarmente para G2.

Claramente, a1 < a e a2 < a. Por hipótese deindução, a1 = v1 % 1 e a2 = v2 % 1.

Mas a = a1 + a2 + 1 e v = v1 + v2.

– p. 12/20

Indução finita - exemplos

Sejam v1 e a1 o número de vértices e arestas deG1. Defina v2 e a2 similarmente para G2.

Claramente, a1 < a e a2 < a. Por hipótese deindução, a1 = v1 % 1 e a2 = v2 % 1.

Mas a = a1 + a2 + 1 e v = v1 + v2. Logo,

a = (v1 % 1) + (v2 % 1) + 1 = v % 1.

– p. 12/20

Indução finita - cuidados

Ao utilizarmos a indução finita devemos estaratentos aos seguintes detalhes:

– p. 13/20

Indução finita - cuidados

Ao utilizarmos a indução finita devemos estaratentos aos seguintes detalhes:

Base da indução

– p. 13/20

Indução finita - cuidados

Ao utilizarmos a indução finita devemos estaratentos aos seguintes detalhes:

Base da indução

Aplicação da hipótese de indução

– p. 13/20

Indução finita - exercícios

Provar as seguintes afirmações:1. 1 + 3 + 5 + · · · + (2n% 1) = n2, 'n # 1.2. 1 + 2 + 22 + · · · + 2n = 2n+1 % 1, 'n # 0.

3. a1 + a1.r + a1.r2 + · · · + a1.rn!1 = a1.(rn!1)

r!1 , 'n # 1.

4. 12 +

14 +

18 + · · · + 1

2n < 1, para n # 1.

5. 12 + 22 + · · · + n2 = n(n+1)(2n+1)6 , 'n # 1.

6. Para qualquer inteiro n, o número 22n % 1 é divisível por3.

7. A soma dos ângulos internos de um polígono convexocom n lados é S = (n% 2)180o.

– p. 14/20

Indução finita - exercícios

8. O número de vértices V , arestas E e faces F de ummapa planar conexo satisfazem a equação:

V % E + F = 2.

9. Um número (em sua representação decimal) é múltiplode 3 se e somente se a soma de seus dígitos é múltiplode 3.

10. Considere n # 3 retas em posições gerais no plano (ouseja, quaisquer duas retas se cruzam e quaisquer trêsretas se cruzam em pontos distintos). Prove que pelomenos uma região que elas formam é um triângulo.

– p. 15/20

Indução finita - exercícios

11. Considere n # 3 retas em posições gerais no plano.Prove que elas formam pelo menos n% 2 triângulos.

12. Considere o conjunto S = {1, 2, . . . , 2n} dos 2nprimeiros números naturais. Mostre que qualquersubconjunto de S com n+ 1 elementos contém doiselementos um dos quais é múltiplo do outro.

13. É possível colorir as regiões formadas por qualquernúmero de retas no plano com apenas duas cores detal forma que regiões vizinhas recebam cores distintas.

– p. 16/20

Analise de Algoritmos

Princípio da casa do pombo

–p. 17/20

Princípio da casa do pombo

Princıpio da casa do pombo:

Se A e B são conjuntos finitos com |A| > |B|,então não existe função bijetora de A para B.

Em outras palavras, se tentarmos associarelementos de A (os “pombos”) com elementos deB (suas “casas”), mais cedo ou mais tarde teremosque colocar mais de um pombo em alguma casa.

– p. 18/20

Princípio da casa do pombo - Exercícios

1. Quantas pessoas são necessárias para se ter certezaque pelo menos duas delas fazem aniversário nomesmo mês?

– p. 19/20

Princípio da casa do pombo - Exercícios

1. Quantas pessoas são necessárias para se ter certezaque pelo menos duas delas fazem aniversário nomesmo mês?

2. Quantas cartas precisam ser tiradas de um baralhoconvencional de 52 cartas para garantir que duas delasserão do mesmo naipe?

– p. 19/20

Princípio da casa do pombo - Exercícios

1. Quantas pessoas são necessárias para se ter certezaque pelo menos duas delas fazem aniversário nomesmo mês?

2. Quantas cartas precisam ser tiradas de um baralhoconvencional de 52 cartas para garantir que duas delasserão do mesmo naipe?

3. Mostre que em qualquer grupo de n # 2 pessoasexistem 2 pessoas com o mesmo número de amigos nogrupo.

– p. 19/20

Princípio da casa do pombo - Exercícios

1. Quantas pessoas são necessárias para se ter certezaque pelo menos duas delas fazem aniversário nomesmo mês?

2. Quantas cartas precisam ser tiradas de um baralhoconvencional de 52 cartas para garantir que duas delasserão do mesmo naipe?

3. Mostre que em qualquer grupo de n # 2 pessoasexistem 2 pessoas com o mesmo número de amigos nogrupo.

4. Seja P = {p1, p2, p3, p4, p5} um conjunto de pontosdistintos no plano, com coordenadas inteiras positivas.Mostre que algum par tem um ponto médio que temcoordenadas inteiras.

– p. 19/20

Princípio da casa do pombo - Exercícios

5. Suponha que façamos 50 disparos em um alvoquadrado de 70cm de lado. Se todos os disparosatingem o alvo, mostre que existem dois disparos cujadistância é no máximo 15cm.

6. Mostre que existe uma potência de 3 que termina com001.

7. Dado um conjunto A ( {1, 2, . . . , 100} de 10 inteiros,mostre que existem dois subconjuntos disjuntos nãovazios de A com a mesma soma de seus membros.

8. Há 25 garotos e 25 garotas sentados em torno de umamesa redonda de 50 lugares. Mostre que existe umapessoa cujos dois vizinhos são garotas.

– p. 20/20