OBMEP 2018: Para fazer um percurso do ponto P ao ponto Q da figura, uma formiguinha

OBMEP 2018: Para fazer um percurso do ponto P ao ponto Q da figura, uma formiguinha deve andar sobre os segmentos horizontais sempre para a ...

OBMEP 2018: Para fazer um percurso do ponto P ao ponto Q da figura, uma formiguinha deve andar sobre os segmentos horizontais sempre para a direita e nunca passar duas vezes por um mesmo segmento vertical. De quantas maneiras diferentes ela pode fazer esse percurso?

A) 3
B) 10
C) 20
D) 1024
E) 1536

QUESTÃO ANTERIOR:
- OBMEP 2018: Ao redor de uma mesa sentaram-se os 17 participantes de um debate. Alguns deles sempre dizem a verdade, e os demais sempre mentem. Todos iniciaram o debate dizendo: “Meus dois vizinhos mentem”. No máximo, quantos mentirosos havia entre os participantes?

RESOLUÇÃO:

Destacamos os pontos A, B, C e D, conforme a figura:

I) Há 3 formas distintas de a formiga chegar, saindo de P, a um dos pontos A ou B sem andar pelo segmento vertical AB (duas maneiras de chegar a A – horizontal/vertical ou vertical/horizontal – e uma só de chegar a B – vertical/vertical/horizontal).

II) A partir de A, fazendo percursos do tipo H (horizontal) ou VH (vertical - horizontal), a formiga chega de 2⁸ formas distintas a um dos pontos C ou D, sem passar pelo segmento CD. Além disso, a partir de cada ponto C ou D há duas formas distintas de chegar até Q (sendo agora permitido passar pelo segmento CD). Portanto, pelo princípio multiplicativo, há um total de 2⁸ × 2 = 2⁹ percursos distintos que a formiga pode fazer para chegar de A até Q. Raciocínios similares nos dão um total de 2⁹ percursos distintos que a formiga pode fazer para chegar de B até Q.

Considerando os casos I) e II), segue do Princípio Multiplicativo da Contagem que há um total de 3 x 2⁹ = 1536 percursos diferentes que a formiga pode fazer para sair de P e chegar a Q, seguindo as regras do enunciado.

Segunda solução:

I) Primeiro consideramos o problema restrito à seguinte figura reduzida:

Ou seja, se deseja determinar de quantas maneiras diferentes a formiga pode fazer o percurso de A até Q, nas mesmas condições do enunciado. As seguintes observações são importantes:

a) a formiga deverá percorrer exatamente 9 segmentos horizontais até chegar a Q;

b) como os pontos A e Q não estão situados numa mesma linha horizontal, a formiga deverá percorrer um número ímpar de segmentos verticais até chegar a Q;

c) dois movimentos verticais consecutivos não podem ser realizados.

Usaremos a letra H para indicar cada movimento sobre um segmento horizontal e V para indicar cada movimento sobre um segmento vertical. Na tabela a seguir, contendo 19 casas, colocamos 9 letras H que indicam os 9 movimentos horizontais realizados pela formiga em cada caminho.

Cada caminho, realizado pela formiga, é definido preenchendo as 10 casas vazias com um número ímpar de letras V e as restantes com 0, onde 0 indica que não foi realizado movimento vertical antes do início ou depois do final de um segmento horizontal. Por exemplo, a tabela

representa o caminho:

Finalmente, para cada uma das primeiras 9 casas vazias podemos colocar 0 ou V sem distinção, totalizando 2⁹ escolhas distintas. Para cada uma dessas escolhas, a última casa vazia fica completamente determinada pelo preenchimento das anteriores, pois o total de letras V deve ser ímpar; logo, há um total de 2⁹ percursos diferentes de A até Q.

II) Uma análise análoga nos dá que a resposta é a mesma (29 escolhas distintas) se trocamos o ponto A de partida da formiga pelo ponto B, conforme a figura a seguir:

Observação: Nesse caso a número de letras V é par.

III) Na figura completa:

basta observar que há 3 formas distintas de a formiga chegar a um dos pontos A ou B sem andar pelo segmento vertical AB. Logo, usando a contagem realizada nos casos I) e II) temos um total de 3 x 2⁹ = 1536 percursos diferentes que a formiga pode fazer.

RESPOSTA:
E) 1536

PRÓXIMA QUESTÃO:
- OBMEP 2018: Um polígono simples com 2018 lados é desenhado a partir de um vértice P no interior de um quadrado. Nenhum vértice do polígono está sobre qualquer lado do quadrado, e nenhum vértice do quadrado está sobre qualquer lado do polígono.