Questão 12 (Nível 1) da OBMEP 2019

Question

A formiguinha da OBMEP está no ponto A e quer ir até o doce que está no ponto B. Ela anda sobre as linhas da figura e faz um caminho com o menor comprimento possível. Quantos são esses caminhos de menor comprimento?

Malha quadriculada com diagonais, indicando a formiga no ponto A no canto superior esquerdo e o doce no ponto B na parte inferior

A
1
B
2
C
3
D
4
E
5

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 12 (Nível 1) da OBMEP 2019

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

A formiguinha da OBMEP está no ponto A e quer ir até o doce que está no ponto B. Ela anda sobre as linhas da figura e faz um caminho com o menor comprimento possível. Quantos são esses caminhos de menor comprimento?

Malha quadriculada com diagonais, indicando a formiga no ponto A no canto superior esquerdo e o doce no ponto B na parte inferior

A
1
B
2
C
3
D
4
E
5

Escolha uma alternativa para conferir o gabarito.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

Para ir até o doce andando sobre as linhas da figura, a formiguinha deve andar 4 vezes para frente e 5 vezes para baixo. Um caminho de menor comprimento possível ocorre quando ela anda simultaneamente para frente e para baixo, na diagonal, o máximo de vezes possível. De acordo com as linhas da figura, esse caminho de menor tamanho possível ocorre quando ela anda 4 vezes na diagonal, escolhendo uma vez só para andar para baixo. Logo, se a letra D representar andar na diagonal e a letra B andar para baixo, os caminhos de menor comprimento possível são:

\text{D}+\text{D}+\text{D}+\text{D}+\text{B};
\text{D}+\text{D}+\text{D}+\text{B}+\text{D};
\text{D}+\text{D}+\text{B}+\text{D}+\text{D};
\text{D}+\text{B}+\text{D}+\text{D}+\text{D};
\text{B}+\text{D}+\text{D}+\text{D}+\text{D}.

Portanto, são 5 os caminhos de menor comprimento possível.

DETALHAMENTO DA SOLUÇÃO:
A principal ideia para a resolução desse problema é a percepção de que o caminho mais curto para ir de um ponto a outro é através do segmento de reta que une os dois pontos, como exemplificamos na figura abaixo:

[Figura: Dois caminhos entre dois pontos pretos: uma linha reta horizontal vermelha e uma linha curva em arco azul por cima, com o texto abaixo em negrito: "O caminho vermelho é mais curto que o azul"]

Utilizando este conceito, vamos a duas considerações:

I) Nenhum caminho mínimo pode passar por qualquer ponto acima da diagonal azul indicada na figura abaixo. Isso é fato, pois a formiga começa em um ponto da diagonal azul e, se em algum momento passar, por exemplo, no ponto verde, obrigatoriamente terá que tornar a passar na diagonal azul e, portanto, o caminho que fosse direto do ponto inicial até este ponto de retorno à diagonal seria menor que o caminho em questão.

II) O mesmo raciocínio se aplica para concluirmos que o caminho mínimo não pode passar por qualquer ponto abaixo da diagonal vermelha, pois, se passar por um ponto, o laranja por exemplo, ela obrigatoriamente passaria por dois pontos da diagonal vermelha e, portanto, esse caminho ficaria maior do que o que une os dois pontos diretamente.

[Figura: Grade quadriculada com diagonais, vértices A no canto superior esquerdo e B no canto inferior direito. Uma faixa diagonal entre uma linha azul e uma linha vermelha é destacada, mostrando também um caminho verde que sobe além da linha azul e um caminho laranja que desce além da linha vermelha.]

Portanto, todos os caminhos mínimos precisam ficar restritos à região compreendida entre as paralelas azul e vermelha, a formiga começa na diagonal azul e, em algum momento, desce para vermelha. Como há 5 segmentos verticais unindo as duas diagonais, há 5 maneiras de ela fazer um caminho mínimo.

[Figura: Diagrama com duas diagonais paralelas, azul e vermelha, ligando o ponto A ao ponto B por meio de 5 segmentos verticais conectando os vértices azuis aos vértices vermelhos.]

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

A figura é uma malha de 4 colunas por 5 linhas de quadrados, cada um com a diagonal que vai do canto superior esquerdo ao inferior direito. A está no canto superior esquerdo e B no canto inferior direito, então as diagonais apontam na direção de B.

O caminho mais curto usa o máximo de diagonais. Uma diagonal mede \sqrt{2}\approx 1{,}41 lado e leva a formiga 1 para a direita e 1 para baixo, enquanto o caminho pelos lados gastaria 2 lados para o mesmo deslocamento.

Precisamos ir 4 para a direita e 5 para baixo. Usando d diagonais, r passos à direita e b passos para baixo, temos:

d + r = 4
d + b = 5

O comprimento é d\sqrt{2} + r + b = d\sqrt{2} + (4-d) + (5-d) = 9 - d(2-\sqrt{2}).

Como 2-\sqrt{2}>0, o comprimento diminui quando d aumenta. O máximo é d=4, com r=0 e b=1. O comprimento mínimo é 4\sqrt{2}+1.

Agora contamos os caminhos: são 4 diagonais e 1 passo vertical para baixo, em qualquer ordem. O passo vertical pode ocupar qualquer uma das 5 posições na sequência, ou seja, pode ser dado depois de 0, 1, 2, 3 ou 4 diagonais.

As diagonais estão todas no mesmo sentido, então qualquer posição do passo vertical é possível: a diagonal seguinte sempre existe na malha, pois o passo vertical desce uma linha e não sai da figura. Em cada caso, o caminho é válido e diferente dos outros.

Portanto são 5 caminhos.

Alternativa E.

Por que as outras alternativas estão erradas

AConsidera apenas o caminho pela diagonal principal, ignorando o passo vertical em outras posições.
BConta só as posições extremas do passo vertical (início e fim).
CNão considera todas as posições possíveis do passo vertical entre as diagonais.
DEsquece uma das 5 posições possíveis do passo vertical, contando só 4.

Assunto: Princípio fundamental da contagem.

Reportar erro na resolução

Ver como caiu na prova

Questão 12 no caderno Nível 1 da OBMEP 2019

Fonte: OBMEP 2019 · Nível 1. Prova oficial ↗