Questão 6 (Nível 2) da 2ª fase da OBMEP 2021

Question

Cinco pedras, A, B, C, D e E, estão dispostas como na figura. Kiko, o sapo simpático, pula de uma pedra para outra somente se elas estiverem ligadas por um segmento. Assim, ele pode pular, partindo de A, para B ou D, mas não para E ou C. Por exemplo, começando em A e terminando em D, ele pode realizar o seguinte passeio de 5 pulos: A \to B \to E \to D \to C \to D.

Cinco pedras identificadas como A, B, C, D e E dispostas em torno e no interior de uma poça d'água. As pedras A, B, C e D formam um losango com ligações entre A e B, B e C, C e D, e D e A. A pedra central E está ligada às pedras B e D. Um sapo verde salta sobre a cena em direção à pedra A.

a) Quantos são os passeios de três pulos que Kiko pode fazer começando em A e terminando em B?

b) Kiko quer fazer um passeio de 1001 pulos, começando em A. Em quais pedras ele poderá terminar esse passeio? Justifique sua resposta.

c) Quantos são os passeios de 2020 pulos que Kiko pode fazer começando em A e terminando em C?

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 6 (Nível 2) da 2ª fase da OBMEP 2021

Nível 2 · Matemática: Lógica e raciocínio lógico

Cinco pedras, A, B, C, D e E, estão dispostas como na figura. Kiko, o sapo simpático, pula de uma pedra para outra somente se elas estiverem ligadas por um segmento. Assim, ele pode pular, partindo de A, para B ou D, mas não para E ou C. Por exemplo, começando em A e terminando em D, ele pode realizar o seguinte passeio de 5 pulos: A \to B \to E \to D \to C \to D.

Cinco pedras identificadas como A, B, C, D e E dispostas em torno e no interior de uma poça d'água. As pedras A, B, C e D formam um losango com ligações entre A e B, B e C, C e D, e D e A. A pedra central E está ligada às pedras B e D. Um sapo verde salta sobre a cena em direção à pedra A.

a) Quantos são os passeios de três pulos que Kiko pode fazer começando em A e terminando em B?

b) Kiko quer fazer um passeio de 1001 pulos, começando em A. Em quais pedras ele poderá terminar esse passeio? Justifique sua resposta.

c) Quantos são os passeios de 2020 pulos que Kiko pode fazer começando em A e terminando em C?

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

a)

No primeiro pulo, Kiko tem duas opções: ele pode ir de A para B ou para D. No segundo pulo, Kiko tem três opções, tanto partindo de B quanto partindo de D. Note que, após esse segundo pulo, Kiko estará, necessariamente, em A, E ou C. No pulo final, de qualquer uma dessas pedras, ele tem apenas uma opção para ir para B. Assim, pelo princípio multiplicativo, Kiko pode realizar 2 \times 3 \times 1 = 6 passeios distintos, começando em A e terminando em B.

Podemos listar os passeios, explicitamente, também: \text{A} \to \text{B} \to \text{A} \to \text{B}, \text{A} \to \text{B} \to \text{E} \to \text{B}, \text{A} \to \text{B} \to \text{C} \to \text{B}, \text{A} \to \text{D} \to \text{A} \to \text{B}, \text{A} \to \text{D} \to \text{E} \to \text{B}, \text{A} \to \text{D} \to \text{C} \to \text{B}.

b)

Analisando-se alguns casos com poucos pulos, como no item anterior, emerge um padrão: em um passeio qualquer, logo após os pulos de número ímpar (primeiro, terceiro, quinto e assim por diante), Kiko estará em B ou D, e, logo após os pulos de número par (segundo, quarto, sexto e assim por diante), Kiko estará em A, E ou C.

Isso pode ser entendido da seguinte maneira: se pintarmos as pedras B e D de branco e as pedras A, E e C de preto, vemos que de uma pedra branca ele pula para uma preta, e de uma pedra preta ele pula para uma branca.

A figura ao lado ilustra essa ideia.

[Figura: Esquema com cinco pedras representadas por círculos nos vértices de um quadrilátero com um ponto central: os vértices A, E e C são círculos pretos preenchidos, enquanto os vértices B e D são círculos brancos vazados. Há segmentos conectando A a B, B a C, C a D, D a A, e o ponto central E está ligado aos vértices B e D.]

Isso indica que, após o 1001^o pulo, Kiko irá se encontrar, necessariamente, em B ou D. Note que o argumento não basta para mostrar que, de fato, ele pode terminar tanto em B quanto em D. Para isso, devemos mostrar que é possível, após o 1001^o pulo, terminar em qualquer uma das duas pedras.

Uma maneira de mostrar que as duas pedras são finais possíveis para o passeio de Kiko é exibir, explicitamente, passeios que terminam em B ou em D depois de 1001 pulos. Um passeio assim pode ser feito da seguinte maneira: simplesmente Kiko pula de A para B e de B para A até completar 1000 pulos. Após o milésimo pulo ele estará em A. De A ele pode dar mais um pulo, tanto para B quanto para D.

c)

Como discutido no item anterior, Kiko tem duas opções para o primeiro pulo (B ou D), 3 opções para o segundo pulo (A, C ou E), e assim por diante, até o 2019^o pulo, quando tem duas opções. No 2020^o pulo, Kiko tem apenas uma opção, que é pular para C. Assim, pelo princípio multiplicativo, Kiko pode realizar 2 \times 3 \times 2 \times 3 \times \dots \times 2 \times 1 = 2^{1010} \times 3^{1009} passeios.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

Primeiro, leia o grafo da figura. Os segmentos são AB, BC, CD, DA, EB e ED. Assim, A, C e E ligam-se somente a B e D, e B e D ligam-se somente a A, C e E. Cada pulo vai, portanto, de \{A,C,E\} para \{B,D\} ou o contrário.

a) O passeio é A \to \square \to \square \to B.

No 1º pulo, Kiko vai de A para B ou D: 2 opções.
No 2º pulo, de B ou de D ele pode ir para qualquer uma de A, C ou E: 3 opções.
No 3º pulo, de A, C ou E ele vai para B, e só há 1 jeito, pois as três pedras estão ligadas a B.

Total: 2\cdot 3\cdot 1 = 6 passeios.

6

b) Cada pulo troca o grupo em que Kiko está, entre \{A,C,E\} e \{B,D\}. Ele começa em A, que está em \{A,C,E\}. Depois de um número ímpar de pulos, ele está sempre em \{B,D\}. Como 1001 é ímpar, ele não pode terminar em A, C nem E.

Agora, B e D são possíveis. Para terminar em B, faça A\to B e depois repita B\to A\to B por 500 vezes: 1+2\cdot 500=1001 pulos. Para terminar em D, faça A\to D e repita D\to A\to D por 500 vezes.

Ele pode terminar em B ou em D (e somente nelas).

c) Em 2020 pulos (número par), Kiko termina em \{A,C,E\}. Cada pulo tem as escolhas abaixo:

de A, C ou E, há 2 opções (ir para B ou D);
de B ou D, há 3 opções (ir para A, C ou E).

Em cada par de pulos há então 2\cdot 3 = 6 escolhas. Em 2020 pulos, que são 1010 pares, há 6^{1010} passeios saindo de A.

Pelo mesmo raciocínio da letra (a), A, C e E são equivalentes: cada uma está ligada a B e a D. Depois de cada par de pulos, a pedra de chegada, entre A, C e E, é escolhida pelo último pulo, e as três têm o mesmo número de passeios. Por exemplo, em 2 pulos há 2 passeios para cada uma das três pedras, num total de 6.

Logo, os 6^{1010} passeios se dividem igualmente entre A, C e E. Em C terminam

\frac{6^{1010}}{3}=2\cdot 6^{1009}.

2\cdot 6^{1009} passeios

Assuntos: Lógica e raciocínio lógico, Princípio fundamental da contagem.

Reportar erro na resolução

Ver como caiu na prova

Questão 6 no caderno Nível 2 da 2ª fase da OBMEP 2021

Fonte: OBMEP 2ª fase 2021 · Nível 2. Prova oficial ↗