Questão M06 da 2ª fase da FUVEST 2015
Um “alfabeto minimalista” é constituído por apenas dois símbolos, representados por * e #. Uma palavra de comprimento n, n \ge 1, é formada por n escolhas sucessivas de um desses dois símbolos. Por exemplo, # é uma palavra de comprimento 1 e #**# é uma palavra de comprimento 4.
Usando esse alfabeto minimalista,
a) quantas palavras de comprimento menor do que 6 podem ser formadas?
b) qual é o menor valor de N para o qual é possível formar 1.000.000 de palavras de tamanho menor ou igual a N?
Reportar erro na questão
Resolução comentada
a) Cada posição da palavra tem 2 escolhas (* ou #). Logo, existem 2^n palavras de comprimento n.
Como "menor do que 6" significa n = 1, 2, 3, 4, 5, somamos:
Outra forma é usar a soma da PG de razão 2: 2^{6} - 2 = 62.
62 palavras.
b) O total de palavras de comprimento menor ou igual a N é a soma de uma PG com primeiro termo 2 e razão 2:
Queremos S_N \ge 1\,000\,000, ou seja, 2^{N+1} \ge 1\,000\,002.
As potências de 2 próximas são 2^{19} = 524\,288 e 2^{20} = 1\,048\,576.
- Para N = 18: S_{18} = 2^{19} - 2 = 524\,286 < 10^6, que não basta.
- Para N = 19: S_{19} = 2^{20} - 2 = 1\,048\,574 \ge 10^6, que basta.
Portanto o menor valor é N = 19.
N = 19.
Assuntos: análise combinatória, progressão geométrica, princípio multiplicativo.
Reportar erro na resolução
Ver como caiu na prova
