.Problema para ajudar na escola: Número bonzinho

Link do problema para dispositivos da Apple.

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 dois eventos forem independentes entre si (isto é, a ocorrência de um não muda a quantidade de possibilidades para a ocorrência do outro), 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 PDF desta página, com o problema e a solução, clicando no botão abaixo.
Você pode abrir o arquivo diretamente no seu navegador (Chrome, Edge, Firefox, Safari, entre outros), mas também pode utilizar o software gratuito Adobe Acrobat Reader.
Caso o dispositivo que você está utilizando não tenha o Acrobat Reader instalado, é só clicar AQUI para fazer o download adequado ao seu dispositivo.

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