Nesta Sala, vamos apresentar problemas de Matemática que podem ser resolvidos utilizando-se recorrências. Boa diversão a todos!
Problema 1
Em uma festa, todos os convidados se cumprimentam com um aperto de mãos. Se houve [tex]45[/tex] apertos de mãos, quantas pessoas estavam na festa?
Denotaremos por [tex]a_{n}[/tex] o número total de apertos de mãos para [tex]n[/tex] convidados.
Se mais uma pessoa entrar na festa, passamos para [tex]n+1[/tex] convidados e serão [tex]a_{n+1}[/tex] apertos de mão.
Note que com o acréscimo de mais uma pessoa aos [tex]n[/tex] convidados, ela apertará a mão de todos os que lá estavam. Assim, teremos [tex]n[/tex] novos apertos de mãos, além dos [tex]a_{n}[/tex] anteriores.
Podemos então concluir que [tex]\boxed{a_{n+1}=a_{n}+n}.[/tex]
Observe também que com uma única pessoa na festa não existiriam apertos de mãos e, portanto, [tex]a_{1}=0[/tex].
Portanto, obtemos a seguinte relação de recorrência para o problema:
Portanto, na festa estavam presentes [tex]\fcolorbox{#589386}{#ddebe8}{$10$}[/tex] pessoas.
Particularmente, você pode conferir o caso em que há seis pessoas na festa, neste probleminha: Apertos de mãos.
Problema 2
De quantos modos podemos cobrir um tabuleiro [tex]2\times7[/tex] com peças iguais de dominós [tex]2\times1[/tex] ?
Chamaremos de [tex]a_{7}[/tex] a solução do problema para o tabuleiro [tex]2\times7[/tex] e faremos a discussão da solução em duas etapas: Etapa 1: O primeiro dominó está na vertical; Etapa 2: O primeiro dominó está na horizontal.
Com isso, [tex]a_{7}[/tex] será a soma do número de soluções com o primeiro dominó na vertical e do número de soluções com o primeiro dominó na horizontal.
Pela restrição imposta no enunciado, se o primeiro dominó estiver na vertical, nosso tabuleiro passa a ser um tabuleiro [tex]2\times6[/tex].
Assim, temos um “novo” problema com as mesmas restrições do anterior, porém com um tabuleiro cujo comprimento é uma unidade menor. Chamaremos de [tex]a_{6}[/tex] a solução do problema para o tabuleiro [tex]2\times 6[/tex].
De forma análoga, se o primeiro dominó estiver na horizontal (na verdade, obrigatoriamente teremos dois dominós na horizontal), nosso tabuleiro passa a ser [tex]2\times 5[/tex].
Assim, também temos um “novo” problema com as mesmas restrições do inicial, porém com um tabuleiro cujo comprimento é duas unidades menor. Também de forma análoga, chamaremos de [tex]a_{5}[/tex] a solução do problema para o tabuleiro [tex]2\times5[/tex].
Dessa estratégia de reduzir o problema a casos menores, resulta que:
[tex]\boxed{a_{7}=a_{6}+a_{5}}[/tex]
e, assim, a solução do problema para um tabuleiro [tex]2\times 7[/tex] é a soma das soluções de um tabuleiro [tex]2\times 6[/tex] com as soluções de um tabuleiro [tex]2\times 5[/tex].
Seguindo esse mesmo raciocínio, podemos generalizar essa relação para um tabuleiro [tex]2\times n[/tex]:
[tex]\boxed{a_{n}=a_{n-1}+a_{n-2}}.[/tex]
Essa relação genérica nos mostra que o número de soluções para um tabuleiro [tex]2\times n[/tex] é a soma das soluções de um tabuleiro [tex]2\times (n-1)[/tex] com as soluções de um tabuleiro [tex]2\times (n-2).[/tex]
Note que:
Em um tabuleiro [tex]2\times 1[/tex], só há uma solução, portanto [tex]a_{1}=1[/tex].
Em um tabuleiro [tex]2\times 2[/tex], teremos duas soluções (ou colocamos os dominós na vertical ou os colocamos na horizontal), portanto [tex]a_{2}=2[/tex].
Assim, ficamos com a seguinte relação de recorrência:
Portanto, podemos cobrir o tabuleiro [tex]2\times 7[/tex] de [tex]\fcolorbox{#589386}{#ddebe8}{$21$}[/tex] maneiras diferentes utilizando peças [tex]2\times1[/tex].
Problema 3
(OBMEP) Abaixo temos três figuras pentagonais: a primeira com [tex]5[/tex] pontos, a segunda com [tex]12[/tex] pontos e a terceira com [tex]22[/tex] pontos. Continuando esse processo de construção, a vigésima figura pentagonal terá [tex]651[/tex] pontos. Quantos pontos terá a vigésima primeira figura?
a) 656
b) 695
c) 715
d) 756
e) 769
Os números de pontos de cada figura formam uma sequência chamada de “números pentagonais”.
Denotaremos por [tex]a_{1}[/tex], [tex]a_{2}[/tex] e [tex]a_{3}[/tex] a quantidade de pontos da primeira, da segunda e da terceira figuras, respectivamente. Assim, [tex]a_{1}=5[/tex], [tex]a_{2}=12[/tex] e [tex]a_{3}=22[/tex].
Também denotaremos por [tex]a_{n}[/tex] a quantidade de pontos da figura [tex]n[/tex] e [tex]a_{n+1}[/tex] a quantidade de pontos da figura [tex]n+1[/tex].
Observe que, a partir da figura [tex]n[/tex], [tex]n \ge 1[/tex], a figura [tex]n+1[/tex] é obtida acrescentando-se à figura anterior [tex]4[/tex] novos pontos (vermelhos) que serão os vértices e [tex]n[/tex] novos pontos (azuis) em cada um dos três lados opostos ao vértice fixo, totalizando [tex]4+3n[/tex] novos pontos.
Portanto, [tex]a_{n+1}=a_{n}+4+3n[/tex].
Desse modo, se a vigésima figura possui [tex]651[/tex] pontos ([tex]a_{20}=651[/tex]) a vigésima primeira terá [tex]a_{21}=651+4+3\cdot20=\fcolorbox{#589386}{#ddebe8}{$715$}[/tex] pontos.
Problema 4
(OBMEP) Fábio gosta de brincar em escadas, subindo ou descendo seus degraus da seguinte maneira:
• começa no degrau de número [tex]1[/tex];
• a cada movimento ele sobe ou desce um ou dois degraus e, ao subir ou descer dois degraus, não pisa no degrau intermediário;
• pisa em todos os degraus exatamente uma vez.
Por exemplo, em uma escada com três degraus ele pode brincar de duas maneiras diferentes: [tex]\boxed{1-2-3}[/tex], [tex]\boxed{1-3-2}[/tex]; com quatro degraus ele pode brincar de quatro maneiras diferentes: [tex]\boxed{1-2-3-4}[/tex], [tex]\boxed{1-2-4-3}[/tex], [tex]\boxed{1-3-2-4}[/tex] e [tex]\boxed{1-3-4-2}.[/tex]
a) Fábio pode brincar de seis maneiras diferentes em uma escada com cinco degraus. Descreva essas seis maneiras.
b) Explique por que sempre é possível terminar a brincadeira no degrau de número [tex]2[/tex] em qualquer escada com dois ou mais degraus.
c) Há [tex]31[/tex] e [tex]68[/tex] maneiras diferentes de se brincar em escadas com nove e onze degraus, respectivamente. De quantas maneiras diferentes Fábio pode brincar em uma escada com doze degraus?
a)
[tex]1-2-3-4-5[/tex]
[tex]1-2-3-5-4[/tex]
[tex]1-2-4-3-5[/tex]
[tex]1-2-4-5-3[/tex]
[tex]1-3-2-4-5[/tex]
[tex]1-3-5- 4-2[/tex]
b) Basta subir pelos degraus ímpares até o mais alto deles e em seguida ir para o mais alto dos pares e descer pelos degraus pares.
c) Vamos denotar por [tex]a_{n}[/tex] a quantidade de maneiras diferentes que Fábio pode brincar em uma escada com [tex]n[/tex] degraus, segundo as regras estabelecidas.
Observe que:
devido às restrições do problema, podemos afirmar que [tex]a_{1}=1[/tex] e [tex]a_{2}=1[/tex];
pelo enunciado do problema, [tex]a_{3}=2[/tex] e [tex]a_{4}=4[/tex];
pelo item a, [tex]a_{5}=6[/tex] e
pelo enunciado do item c, [tex]a_{9}=31[/tex] e [tex]a_{11}=68[/tex].
Do mesmo modo como resolvemos alguns exercícios anteriores, vamos dividir este problema em dois casos: Caso 1: Fábio fez os movimentos [tex]1-2[/tex]
Neste caso, o problema passou de doze para onze degraus ([tex]a_{11}=68[/tex]). Caso 2: Fábio fez os movimentos [tex]1-3[/tex]
Neste caso, temos duas opções:
Fábio pode subir os degraus ímpares e voltar pelos pares, parando no degrau [tex]2[/tex], dando uma possível solução. (Essa foi a contribuição do item b.)
Fábio pode fazer [tex]1-3-2-4[/tex], tornando o problema para nove degraus ([tex]a_{9}=31[/tex]).
Portanto, [tex]a_{12}=a_{9}+a_{11}+1[/tex], donde [tex] \fcolorbox{#589386}{#ddebe8}{$a_{12}=100$}.[/tex]
Observação: Podemos generalizar e encontrar a recorrência envolvida no problema: [tex]\boxed{a_{n}=a_{n-3}+a_{n-1}+1}[/tex].
Problema 5
Quantas são as sequências de dez termos, todos iguais a [tex]0[/tex] ou [tex]1[/tex], que possuem um número ímpar de termos iguais a [tex]0[/tex]?
Seja [tex]a_{10}[/tex] a quantidade de sequências de [tex]10[/tex] termos que possuem um número ímpar de termos iguais a [tex]0[/tex]. Assim como fizemos em exercícios anteriores, vamos abrir a solução em dois casos:
1º caso: O primeiro elemento é igual a [tex]1[/tex]; 2º caso: O primeiro elemento é igual a [tex]0[/tex].
Se o primeiro elemento for [tex]1[/tex], o nosso problema passa para uma sequência com [tex]9[/tex] termos na qual a quantidade de termos iguais a [tex]0[/tex] deve ser ímpar. Assim, a quantidade de sequências de [tex]10[/tex] termos que começam por [tex]1[/tex] e possuem uma quantidade ímpar de termos iguais a [tex]0[/tex] é [tex]a_{9}[/tex].
No segundo caso, se o primeiro elemento for [tex]0[/tex], a sequência passa a ser uma sequência de [tex]9[/tex] termos na qual a quantidade de termos iguais a [tex]0[/tex] deve ser par. Para descobrirmos o número total de sequências de [tex]9[/tex] termos com uma quantidade par de termos iguais a [tex]0[/tex], basta fazer o número total de sequências menos o número de sequências com a quantidade ímpar de zeros. Pelo princípio multiplicativo, o número total de sequências é [tex]2^{9}[/tex] e o número de sequências com quantidade ímpar de termos [tex]0[/tex] é [tex]a_{9}[/tex] (como visto no primeiro caso).
Portanto,
[tex]\qquad a_{10}=[/tex]sequências com o primeiro elemento igual a [tex]1[/tex] [tex]+[/tex] sequências com o primeiro elemento igual a [tex]0[/tex]
[tex]\qquad a_{10}=a_{9}+(2^{9}-a_{9})[/tex]
[tex]\qquad a_{10}=2^{9}=\fcolorbox{#589386}{#ddebe8}{$512$}.[/tex]
Observação: Podemos generalizar essa solução e concluir que [tex]a_{n}=2^{n-1}[/tex], sendo [tex]a_{n}[/tex] a quantidade de sequências com [tex]n[/tex] termos que possui uma quantidade ímpar de termos iguais a [tex]0[/tex].
Perceba que nesse problema o pensamento recursivo já forneceu a forma fechada da sequência.
Agora é com vocês…
Tentem resolver os próximos problemas. Bom trabalho, pessoal!
Problema proposto 1
Seja [tex]S_{n}[/tex] a soma dos ângulos internos de um polígono convexo de [tex]n[/tex] lados.
a) Determine, em função de [tex]S_{n}[/tex], a soma dos ângulos internos de um polígono convexo de [tex]n+1[/tex] lados [tex](S_{n+1});[/tex]
b) Sabendo que a soma dos ângulos internos de um polígono convexo com [tex]19[/tex] lados vale [tex]3060^{\circ}[/tex], calcule a soma dos ângulos internos para um polígono convexo de [tex]20[/tex] lados.
a) [tex]S_{n+1}=S_{n}+180^{\circ}.[/tex]
b) [tex]S_{20}=S_{19}+180^{\circ}\\
S_{20}=3060^{\circ}+180^{\circ}=3240^{\circ}.[/tex]
Problema proposto 2
O próximo problema é conhecido como “A PIZZA DE STEINER”, em homenagem ao matemático suíço Jakob Steiner (1796-1863).
a) Qual é o número máximo de pedaços em que uma pizza pode ser dividida por [tex]8[/tex] cortes retilíneos?
b) Sendo [tex]a_{n}[/tex] o número máximo de regiões nas quais [tex]n[/tex] cortes retilíneos podem dividir uma pizza, encontre uma relação de recorrência que expresse [tex]a_{n}[/tex] em função de [tex]a_{n-1}[/tex].
a) [tex]a_{8}= 37[/tex].
b) [tex]a_{n}=a_{n-1}+n[/tex], [tex]n \ge 2[/tex].
Este vídeo pode lhe ajudar…
Problema proposto 3
a) Quantas são as sequências de [tex]6[/tex] termos, todos iguais a [tex]0[/tex], [tex]1[/tex] ou [tex]2[/tex], que possuem um número ímpar de termos iguais a [tex]0[/tex]?
b) Determine uma relação de recorrência que expressa o termo [tex]a_{n}[/tex] em função de [tex]a_{n-1}[/tex], sendo [tex]a_{n}[/tex] e [tex]a_{n-1}[/tex] o número de sequências de [tex]n[/tex] e [tex]n-1[/tex] termos, respectivamente, que possuem um número ímpar de termos iguais a [tex]0[/tex].
a) [tex] \dfrac {3^{6}-1}{2}=364[/tex].
b) [tex]a_{n}=a_{n-1}+3^{n-1}[/tex], [tex]n \ge 2[/tex].
Problema proposto 4
(OBMEP– Adaptado) Um número natural é setespalhado quando não tem dois algarismos [tex]7[/tex] seguidos em sua representação decimal. Por exemplo, [tex]345[/tex], [tex]2071[/tex] e [tex]72347[/tex] são setespalhados, enquanto [tex]277304[/tex] e [tex]777[/tex] não são.
a) Quantos são os números setespalhados de [tex]2[/tex] algarismos?
b) Quantos são os números setespalhados de [tex]3[/tex] algarismos?
c) Quantos são os números setespalhados de [tex]4[/tex] algarismos nos quais o algarismo das unidades não é [tex]7[/tex]?
d) Seja [tex]a_{n}[/tex] a quantidade de números setespalhados de [tex]n[/tex] algarismos. Expresse [tex]a_{n}[/tex] em função de [tex]a_{n-1}[/tex] e [tex]a_{n-2}[/tex], para [tex]n \ge3[/tex].
