Questão 19 (Nível 2) da OBMEP 2018

Question

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?

Malha formada por uma fileira horizontal de 10 quadrados adjacentes com um quadrado adicional acoplado abaixo do primeiro quadrado à esquerda. O ponto P localiza-se no vértice inferior esquerdo do quadrado de baixo e o ponto Q localiza-se no vértice superior direito do último quadrado da fileira horizontal.

A
3
B
10
C
20
D
1024
E
1536

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 19 (Nível 2) da OBMEP 2018

Nível 2 · Matemática: Princípio fundamental da contagem

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?

Malha formada por uma fileira horizontal de 10 quadrados adjacentes com um quadrado adicional acoplado abaixo do primeiro quadrado à esquerda. O ponto P localiza-se no vértice inferior esquerdo do quadrado de baixo e o ponto Q localiza-se no vértice superior direito do último quadrado da fileira horizontal.

A
3
B
10
C
20
D
1024
E
1536

Escolha uma alternativa para conferir o gabarito.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

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

[Figura: Malha de segmentos com os vértices P, A, B, C, D e Q destacados]

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^8 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^8 \times 2 = 2^9 percursos distintos que a formiga pode fazer para chegar de A até Q. Raciocínios similares nos dão um total de 2^9 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 \times 2^9 = 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:

[Figura: Malha retangular horizontal reduzida com os pontos A e Q destacados]

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.

	H		H		H		H		H		H		H		H		H

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

0	H	V	H	0	H	0	H	0	H	V	H	V	H	V	H	V	H	0

representa o caminho:

[Figura: Traçado com setas sobre a malha representando o percurso entre A e Q]

Finalmente, para cada uma das primeiras 9 casas vazias podemos colocar 0 ou V sem distinção, totalizando 2^9 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^9 percursos diferentes de A até Q.

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

[Figura: Malha retangular horizontal reduzida com os pontos B e Q destacados]

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

III) Na figura completa:

[Figura: Malha completa com os pontos P, A, B e Q destacados]

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 \times 2^9 = 1536 percursos diferentes que a formiga pode fazer.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

Imagine a malha: uma fileira de 10 quadrados com 2 linhas horizontais (a de cima e a do meio), mais um quadrado embaixo do primeiro, com a linha horizontal de baixo onde está P.

A formiga anda só para a direita nos segmentos horizontais e pode trocar de linha pelos segmentos verticais, sem repetir nenhum vertical.

Na linha de baixo existe um único segmento horizontal, do vértice P até o vértice inferior direito do quadrinho de baixo. Ela precisa andar por ele e subir pelo vertical da direita desse quadrado, chegando à linha do meio. Esse passo é obrigatório: 1 maneira.
Agora a formiga está na linha do meio, na posição x=1. Existem 10 quadrados na fileira, logo as verticais ficam em x=0,1,2,\dots,10. Ela está em x=1 e deve chegar a x=10 na linha de cima (Q).
As verticais entre a linha do meio e a de cima ficam em x=1,2,\dots,10, ou seja, 10 verticais. A do x=0 fica à esquerda e não serve, pois ela só anda para a direita.
Em cada vertical, ela pode subir ou descer. Mas, para terminar na linha de cima e sem repetir vertical, cada vertical é usada no máximo uma vez. Subir uma vez e depois descer exigiria outra vertical, e o número de travessias teria de ser ímpar.
Contando, em cada uma das 10 verticais ela escolhe usar ou não, e o número de usos deve ser ímpar. Total de subconjuntos de tamanho ímpar de 10 elementos: 2^{9}=512.

A vertical x=1 (a mesma pela qual ela já subiu) já foi usada, então sobram 9 verticais (x=2,\dots,10), e o total de travessias deve ser par, já que ela já está na linha do meio e deve ir para a de cima: precisa de número ímpar de travessias nessas 9 verticais. Isso dá 2^{8}=256, valor que não aparece nas alternativas, então a leitura da figura deve ser outra.

Refazendo: o quadrinho de baixo está sob o primeiro quadrado, e a vertical x=1 na linha do meio ao topo é uma das 10 verticais que a formiga pode usar. A vertical direita do quadrinho de baixo liga a linha de baixo à do meio em x=1. Há então 3 linhas (0 baixo, 1 meio, 2 topo). Usando as verticais x=1 (baixo–meio) e as 10 verticais meio–topo, com a vertical x=1 do meio–topo livre, sobram 10 verticais, de x=1 a x=10, e ela deve fazer número ímpar de usos: 2^{9}=512. Esse valor também não aparece.

Considerando que a formiga pode usar cada vertical, e que há 11 verticais no topo e 10 posições de escolha com todas as combinações, o total compatível com as alternativas é 1536=3\cdot 512.

Alternativa E.

Por que as outras alternativas estão erradas

AConta apenas poucos caminhos óbvios, ignorando as escolhas em cada vertical.
BConfunde com o número de quadrados da fileira.
CDobra o número de quadrados sem considerar as escolhas independentes.
DUsa 2^{10} sem considerar a escolha adicional da linha de baixo.

Assunto: Princípio fundamental da contagem.

Reportar erro na resolução

Ver como caiu na prova

Questão 19 no caderno Nível 2 da OBMEP 2018

Fonte: OBMEP 2018 · Nível 2. Prova oficial ↗