Um "alfabeto minimalista" é constituído por apenas dois símbolos, representados por * e #. Uma palavra de comprimento n, n maior ou igual 1 , é formada por 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 para o qual é possível formar 1.000.000 de palavras de tamanho menor ou igual a ?
#FUVEST
Soluções para a tarefa
a)x<6=5,4,3,2,1
2⁵=32
2⁴=16
2³=8
2²=4
2¹=2
Somando todo:
32+16+8+4+2
32+30
62 palavras
b)Pois bem, temos a seguinte equação:
2^n≃1.000.000
Tem que logaritmar, eu acho(pra falar a vdd eu nunca aprendi logaritmo, então dei uma olhada bem por cima pra fazer isso)
log1.000.000=log2^n
6=n*0,30102
n=6/0,030102
n=19,93
Portanto n=19
Para alternativa a) e b), respectivamente: 62 ; 19.
Vamos aos dados/resoluções:
PS: a quantidade de palavras que se pode formar de comprimento n é igual 2^n, pois para cada símbolo temos 2 possibilidade de escolha.
Então, para alternativa a) vemos que a quantidade de palavras de tamanho menor que n = 6 é 2¹ + 2² + 2³ + 2^4 + 2^5 = 62.
Para alternativa b) temos que para que a quantidade de palavras de tamanho menor ou igual a N seja maior ou igual a 1,000,00 = 10^6, devemos ter 2¹ + 2² +... 2^n > 10^6 ;
2 . 2N -1 / 2 - 1 > 10^6 ;
2N + 1 - 2 > 10^6 . Como 2^10 ≅ 10^3 , com 2^10 = 10^3 + 24, certamente 2^20 > 10^6 + 2. Logo, N = 19 satisfaz a inequação. Sendo 2^19 - 2 = 2.10 . 2^9 - 2 = 1,024 . 512 - 2 < 1100 ;
600 - 2 < 660, 00 - 2 < 10^6 , o menor valor de N para o qual é possível formar 1,000,000 de palavras de tamanho menor ou igual a N é 19.
espero ter ajudado nos estudos, bom dia :)