FGV-SP 2015

Um sistema de código de barras tem extensão de 13 cm, e é composto por barras alternadas de cor branca ou preta, começando e terminando sempre por uma barra preta. Cada barra (branca ou preta) mede 1 ou 2 cm. A figura indica uma possibilidade de código nesse sistema. A leitura de código no sistema sempre é feita da esquerda para a direita.

Calcule o total de códigos diferentes que podem ser formados nesse sistema.



Gabarito: 189

Primeira solução.
Vamos colocar lado a lado algumas barras alternadas: primeiro preto, segundo branco, terceiro preto, ..., até a última, também preta, então eu tenho necessariamente um número de barras ímpar. Sejam x de tamanho 1 e y de tamanho 2. Segue que n = x + y é ímpar. Também, 13 = x + 2y. As soluções (x,y) =:
(1,6) -> n = 7 
(3,5) -> n = 8 
(5,4) -> n = 9 
(7,3) -> n = 10 
(9,2) -> n = 11
(11,1) -> n = 12
(13,0) -> n = 13

Agora a gente permuta as "palavras formadas". Por exemplo, (1,6) => ABBBBBB -> 7!/6! = 7
(5,4) -> 9!/5!4! = 126
(9,2) -> 11!/9!2! = 55
(13,0) -> 13!/13! = 1
Somando tudo, n = 7 + 126 + 55 + 1 = 189.

Segunda solução
Vou notar | como preto e - como branco. Vamos construir por partes supondo que eu somente terminasse com a barra preta. Então para 4 temos as seguintes possibilidades:
--||  -|-|  |--|  |-||  ||-|
Para criar os com 5, separamos em quatro categorias:
1. Um só - no início (-|-|), ela vai gerar seu próprio número na categoria 2 e 3
Aqui temos só 1 nesse tipo, dizemos x1(4) = 1, que vai adicionar x2(5) e x3(5) em uma unidade (--|-| ou |-|-|)

2. Dois -- no início (--||), vai gerar seu próprio número na categoria 3. Temos x2(4) = 1 -> adiciona 1 em x3(5)

3. Um só | no início (|--| e |-||), vai gerar seu próprio número nas categorias 1 e 4 -> dizemos x3(4) = 2 e adiciona 2 em x1(5) e em x4(5)

4. Dois || no início (||-|), vai gerar seu próprio número na categoria 1. Temos x4(1) = 1 -> adiciona 1 em x1(5)

O que estamos fazendo é reanalisar esses números de novo e de novo. De forma geral, x1(n+1) = x3(n) + x4(n)
x2(n+1) = x1(n)
x3(n+1) = x1(n) + x2(n)
x4(n+1) = x3(n)
E as formas válidas (que começam por |) são f(n) = x3(n) + x4(n). Então vamos trabalhar em cima desse povo. Quero pôr f(n+1) em função de uma soma de f(k), menores.
Note: x1(n+1) = x3(n) + x4(n) = f(n), logo x1(n) = f(n-1). Daí, x2(n+1) = x1(n) = f(n-1) => x2(n) = f(n-2), seguindo que x3(n+1) = x1(n) + x2(n) = f(n-1) + f(n-2), logo x3(n) = f(n-2) + f(n-3). Por fim, x4(n+1) = x3(n) = f(n-2) + f(n-3) => x4(n) = f(n-3) + f(n-4). Portanto, f(n) = x3(n) + x4(n) = f(n-2) + 2f(n-3) + f(n-4).
É fácil ver que f(1) = f(2) = f(3) = 1. Para 1: | (abstraindo), para 2: ||, para 3: |-|. Podemos fazer ainda f(0) = 0, de forma que f(4) = 1 + 2.1 + 0 = 3 (como é previsto). Então, 
f(2) = 1
f(3) = 1
f(4) = 3
f(5) = 1 + 2.1 + 1 = 4
f(6) = 3 + 2.1 + 1 = 6
f(7) = 4 + 2.3 + 1 = 11
f( = 6 + 2.4 + 3 = 17
f(9) = 11 + 2.6 + 4 = 27
f(10) = 17 + 2.11 + 6 = 45
f(11) = 27 + 2.17 + 11 = 72
f(12) = 45 + 2.27 + 17 = 116 (é desnecessário calcular esse rs)
f(13) = 72 + 2.45 + 27 = 189.

Lipo_f escreveu:Primeira solução.
Vamos colocar lado a lado algumas barras alternadas: primeiro preto, segundo branco, terceiro preto, ..., até a última, também preta, então eu tenho necessariamente um número de barras ímpar. Sejam x de tamanho 1 e y de tamanho 2. Segue que n = x + y é ímpar. Também, 13 = x + 2y. As soluções (x,y) =:
(1,6) -> n = 7 
(3,5) -> n = 8 
(5,4) -> n = 9 
(7,3) -> n = 10 
(9,2) -> n = 11
(11,1) -> n = 12
(13,0) -> n = 13

Agora a gente permuta as "palavras formadas". Por exemplo, (1,6) => ABBBBBB -> 7!/6! = 7
(5,4) -> 9!/5!4! = 126
(9,2) -> 11!/9!2! = 55
(13,0) -> 13!/13! = 1
Somando tudo, n = 7 + 126 + 55 + 1 = 189.

Segunda solução
Vou notar | como preto e - como branco. Vamos construir por partes supondo que eu somente terminasse com a barra preta. Então para 4 temos as seguintes possibilidades:
--||  -|-|  |--|  |-||  ||-|
Para criar os com 5, separamos em quatro categorias:
1. Um só - no início (-|-|), ela vai gerar seu próprio número na categoria 2 e 3
Aqui temos só 1 nesse tipo, dizemos x1(4) = 1, que vai adicionar x2(5) e x3(5) em uma unidade (--|-| ou |-|-|)

2. Dois -- no início (--||), vai gerar seu próprio número na categoria 3. Temos x2(4) = 1 -> adiciona 1 em x3(5)

3. Um só | no início (|--| e |-||), vai gerar seu próprio número nas categorias 1 e 4 -> dizemos x3(4) = 2 e adiciona 2 em x1(5) e em x4(5)

4. Dois || no início (||-|), vai gerar seu próprio número na categoria 1. Temos x4(1) = 1 -> adiciona 1 em x1(5)

O que estamos fazendo é reanalisar esses números de novo e de novo. De forma geral, x1(n+1) = x3(n) + x4(n)
x2(n+1) = x1(n)
x3(n+1) = x1(n) + x2(n)
x4(n+1) = x3(n)
E as formas válidas (que começam por |) são f(n) = x3(n) + x4(n). Então vamos trabalhar em cima desse povo. Quero pôr f(n+1) em função de uma soma de f(k), menores.
Note: x1(n+1) = x3(n) + x4(n) = f(n), logo x1(n) = f(n-1). Daí, x2(n+1) = x1(n) = f(n-1) => x2(n) = f(n-2), seguindo que x3(n+1) = x1(n) + x2(n) = f(n-1) + f(n-2), logo x3(n) = f(n-2) + f(n-3). Por fim, x4(n+1) = x3(n) = f(n-2) + f(n-3) => x4(n) = f(n-3) + f(n-4). Portanto, f(n) = x3(n) + x4(n) = f(n-2) + 2f(n-3) + f(n-4).
É fácil ver que f(1) = f(2) = f(3) = 1. Para 1: | (abstraindo), para 2: ||, para 3: |-|. Podemos fazer ainda f(0) = 0, de forma que f(4) = 1 + 2.1 + 0 = 3 (como é previsto). Então, 
f(2) = 1
f(3) = 1
f(4) = 3
f(5) = 1 + 2.1 + 1 = 4
f(6) = 3 + 2.1 + 1 = 6
f(7) = 4 + 2.3 + 1 = 11
f( = 6 + 2.4 + 3 = 17
f(9) = 11 + 2.6 + 4 = 27
f(10) = 17 + 2.11 + 6 = 45
f(11) = 27 + 2.17 + 11 = 72
f(12) = 45 + 2.27 + 17 = 116 (é desnecessário calcular esse rs)
f(13) = 72 + 2.45 + 27 = 189.

Eu vi essa primeira solução em outro site. Não entendi o porquê de podermos fazer essa forma. Tipo, entendo o fato de ser 2/1cm, mas não onde que entra a possibilidade de ser branca ou preta. Outra coisa, faz sentido o número diminuir? Porque da maneira que eu penso fazer daria para repetir a barra, assim sendo 2.4.4.4...2 e fazer os outros casos nos números diferentes das barras. Enfim, agradeço se puder explicar melhor a lógica!

Lucas Schokal escreveu:Eu vi essa primeira solução em outro site. Não entendi o porquê de podermos fazer essa forma. Tipo, entendo o fato de ser 2/1cm, mas não onde que entra a possibilidade de ser branca ou preta. Outra coisa, faz sentido o número diminuir? Porque da maneira que eu penso fazer daria para repetir a barra, assim sendo 2.4.4.4...2 e fazer os outros casos nos números diferentes das barras. Enfim, agradeço se puder explicar melhor a lógica!

Uma outra forma de olhar a questão é: tenho 13 barras de 1cm, as duas extremas são pretas e eu não posso ter três ou mais pretas ou brancas juntas. Por exemplo, |--||---|-|-| é inválida por ter três brancas contíguas, então você não pode juntar as barras como disse, porque ultrapassaria o limite de 2cm por cor contígua. Sobre a solução funcionar, como eu preciso que o limite contíguo seja de 2cm, eu preciso alternar a cor de preto pra branco e vice-versa. No exemplo desta resposta, eu separei em 13 barras, mas na solução isso não ocorre, as barras são de tamanhos variados. Tente imaginar como uma palavra: U (1cm) D (2cm). Vou colocar as barras lado a lado, por exemplo, UUUDUDDUD (1+1+1+2+1+2+2+1+2 = 13). Nota que eu não preciso definir as cores, elas já são pré-definidas, porque se alternam e começam pelo preto. Transferindo pra convenção: |-|--|--||-||. Agora se eu permuto isso: UUUUUDDDD -> |-|-|--||--||. Independente de como estejam os D's e U's, sempre tenho um novo código válido que comece e termine por preto.