MAT233 – Matemática Discreta A Exercícios de Revisão 1. Descreva cada problema e o procedimento para encontrar sua relação de recorrência: a) Sequência de Fibonacci b) Regiões criadas num plano por n retas, duas a duas concorrentes, cuja intersecção de qualquer subconjunto de três retas é vazia. c) Torre de Hanoi. 2. Num trabalho escolar participarão 6 alunos, onde há três duplas que não podem ficar sentadas lado a lado, pois dispersam o grupo com a conversa. Determine o número de alocações possíveis dessas pessoas em torno de uma mesa circular, de forma que nenhuma dessas duplas fique em lugares adjacentes. 3. Quantas sequências ternárias de 4 dígitos podemos formar, onde existe um número par de dígitos 0’s e de dígitos 1’s? 4. Qual o menor número de movimentos necessários para se mover uma torre de Hanoi com cinco discos? E com 10 discos? 5. Quantas regiões são criadas num plano por 2 retas paralelas e 2 retas concorrentes? Represente graficamente a situação e confira o resultado com o calculado. 6. Quantas regiões são criadas num plano por 5 retas concorrentes e 6 retas paralelas? 7. Utilizando as técnicas de solução de relações de recorrência linear encontre a forma fechada para as relações de recorrência dos problemas: a) Sequência de Fibonacci b) Regiões criadas num plano por n retas, duas a duas concorrentes, cuja intersecção de qualquer subconjunto de três retas é vazia. c) Torre de Hanoi. 8. Enuncie o princípio da casa dos pombos e apresente um exemplo de aplicação. 9. Quantas pessoas, no mínimo, devem estar presentes numa sala para que possamos garantir que: a) Pelo menos duas delas fazem aniversário no mesmo mês? b) Pelo menos três delas escreverão o mesmo número num papel, sendo que os números informados para escolha são de 1 a 10.