Lista de Exercícios 2

Prévia do material em texto

II Lista de Exerc´ıcios de Ana´lise Combinato´ria.
Profo Danilo Artigas
Polo Universita´rio de Rio das Ostras
UFF
1) Determine uma relac¸a˜o de recorreˆncia T (n) para determinar o nu´mero de quadrados que possui um
tabuleiro de xadrez n× n. Determine sua fo´rmula fechada.
2) Uma bandeira e´ formada por n listras, que devem ser coloridas usando-se apenas as cores azul, amarelo
e verde, na˜o devendo listras adjacentes ter a mesma cor. Determine uma relac¸a˜o de recorreˆncia para
T (n) o nu´mero de modos distintos que a bandeira pode ser colorida. Determine sua fo´rmula fechada.
3) Determine uma relac¸a˜o de recorreˆncia para Dn, o nu´mero de permutac¸o˜es cao´ticas dos naturais de 1 a
n.
4) Dispomos de uma quantidade ilimitada de blocos coloridos nas cores branca, amarela e vermelha. Os
blocos amarelos sa˜o quadrados e medem 1dm de lado. Os blocos brancos e vermelhos sa˜o retangulares
e medem 1dm × 2dm. De quantas maneiras podemos arruma´-los em uma fila que ocupe n dm com
os lados menores em contato?
5) Um nu´mero triangular e´ um nu´mero natural que pode ser representado na forma de triaˆngulo
equila´tero. Para encontrar o n-e´simo nu´mero triangular a partir do anterior basta somar-lhe n unidades.
Os primeiros nu´meros triangulares sa˜o: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Monte uma relac¸a˜o de recorreˆncia para determinar o n-e´simo nu´mero triangular.
Determine qual e´ o menor nu´mero triangular que possui mais de 500 divisores naturais?
Se for necessa´rio, desenvolva um programa para auxiliar a obter esta resposta.
6) Considere nu´meros escritos na base K, contendo exatamente N digitos. Um nu´mero e´ considerado va´lido
se sua notac¸a˜o na base K na˜o conte´m zeros sucessivos. Por exemplo:
• 1010230 e´ um nu´mero va´lido de 7 d´ıgitos;
• 1000198 na˜o e´ um nu´mero va´lido;
• 0001235 na˜o e´ um nu´mero de 7 d´ıgitos, mas sim, um nu´mero de 4 d´ıgitos.
Dados 2 nu´meros N e K, calcule o total de nu´meros va´lidos, escritos na base K, contendo N d´ıgitos.
7) Considere a relac¸a˜o de recorreˆncia definida abaixo:
S(n) =
{
2S(n− 1) + 3 , n ≥ 2
4 , n = 1
Prove por induc¸a˜o que S(n) = 2n+1 + 3[2n−1 − 1].
8) Monte uma relac¸a˜o de recorreˆncia para o nu´mero de comparac¸o˜es realizadas por um algoritmo de busca
bina´ria. Considere que o vetor V , onde efetuamos a busca, tem n elementos; V esta´ ordenado; e o
elemento desejado na˜o se encontra em V .
1