.Problema para ajudar na escola: Número bonzinho

Problema
(A partir do 9º ano do E. F.- Nível de dificuldade: Difícil)


Um número natural B é dito bonzinho se ele tem apenas os algarismos [tex]1[/tex], [tex]2[/tex] ou [tex]3[/tex] e todos os números de dois dígitos formados por algarismos localizados em posições adjacentes (vizinhas) de B são números distintos.
Por exemplo,

  • [tex]2212[/tex] é bonzinho ([tex]22[/tex], [tex]21[/tex] e [tex]12[/tex] são distintos);
  • [tex]321[/tex] é bonzinho ([tex]32[/tex] e [tex]21[/tex] são distintos) ;
  • [tex]112233[/tex] é bonzinho;
  • [tex]31231[/tex] não é bonzinho ([tex]\textcolor{red}{31}2\textcolor{red}{31}[/tex]), mas [tex]31233[/tex] e [tex]31232[/tex] são.

Existe algum número bonzinho com dez dígitos?
E com onze?

Extraído da Olimpiada de Mayo, 2004.

explicador_p

Lembrete

Princípio Fundamental da Contagem, ou Princípio Multiplicativo, para dois eventos: Se

  • um evento E1 puder ocorrer de [tex] m_1 [/tex] maneiras,
  • um evento E2 puder ocorrer de [tex]m_2 [/tex] maneiras,

e esses eventos forem independentes entre si, então a quantidade de maneiras em que os dois eventos ocorrem ao mesmo tempo é
[tex]\qquad \qquad \boxed{m_1\times m_2 }\, .[/tex]
(Se você não se lembra desse Princípio, seria interessante dar uma passadinha nesta Sala de Estudo.)

Solução


  • Observe, inicialmente, que um número que tenha [tex]n[/tex] algarismos define [tex]n-1[/tex] números de dois algarismos localizados em posições adjacentes, já que todos os seus algarismos, com exceção do último, são primeiro algarismo de um número de dois algarismos.
  • Por outro lado, a partir dos algarismos [tex]1[/tex], [tex]2[/tex] e [tex]3[/tex], podemos formar nove números de dois algarismos: [tex]3[/tex] possibilidades de escolha para o primeiro algarismo e [tex]3[/tex] para o segundo; logo, pelo Princípio Multiplicativo, existem [tex]3\times 3=9[/tex] maneiras de construirmos os números em questão.

Pelo até aqui exposto, a partir de um número natural B bonzinho com [tex]n[/tex] algarismos é possível definir [tex]n-1[/tex] números de dois algarismos localizados em posições adjacentes. Mas utilizando os algarismos [tex]1[/tex], [tex]2[/tex] e [tex]3[/tex] só conseguimos definir [tex]9[/tex] números distintos com dois algarismos. Assim, [tex]n-1 \leqslant 9[/tex], donde [tex]n \leqslant 10\;.[/tex]
Dessa forma, um número bonzinho não pode ter mais de dez algarismos e, portanto, não existe um número bonzinho com [tex]11[/tex] algarismos.
O fato de teoricamente ser possível definir nove números diferentes com dois algarismos utilizando apenas o [tex]1[/tex], o [tex]2[/tex] e o [tex]3[/tex] não garante por si só a existência de um número bonzinho com dez algarismos; precisamos exibir, de fato, um.
Mas, por exemplo, [tex]1121322331[/tex] é bonzinho:
[tex]\qquad 1121322331\\
\qquad 11 \\
\qquad \;\; 12\\
\qquad \;\; \;\; 21\\
\qquad \;\;\;\;\;\;13\\
\qquad \;\; \;\; \;\; \;\; 32\\
\qquad \;\;\;\;\;\;\;\;\;\;22\\
\qquad \;\; \;\; \;\; \;\; \;\; \;\;23\\
\qquad \;\; \;\; \;\; \;\; \;\; \;\; \;\;33\\
\qquad \;\; \;\; \;\; \;\; \;\; \;\;\;\;\;\;31\\[/tex]
o que garante a existência de pelo menos um número bonzinho com dez algarismos.


Solução elaborada pelos Moderadores do Blog.

Se for conveniente, você pode obter um arquivo desta página em PDF. Mas, para abrir esse arquivo, é necessário que você tenha o Adobe Acrobat Reader instalado no dispositivo que você está utilizando. Caso não tenha, é só clicar AQUI para fazer o download.
Se o seu dispositivo já tem o Adobe Acrobat Reader instalado, basta copiar o arquivo abaixo e abri-lo sempre que quiser!

Link permanente para este artigo: http://clubes.obmep.org.br/blog/problema-para-ajudar-na-escola-numero-bonzinho/