Questão 5 (Nível 1) da 2ª fase da OBMEP 2023

Question

A formiguinha da OBMEP caminha do ponto A até o ponto B ao longo dos lados dos 10 quadradinhos da figura abaixo.

Malha retangular formada por uma fila horizontal de 10 quadradinhos, com o ponto A no vértice inferior esquerdo e o ponto B no vértice superior direito.

Ela só pode andar para a direita, para cima ou para baixo, sem passar por onde já passou. Para representar um caminho, ela inventou o seguinte código: para cada quadradinho, da esquerda para a direita, se ela passar por baixo, escreve 0 e se passar por cima, escreve 1. Na figura a seguir observamos o caminho representado por 0010100011.

Malha de 10 quadradinhos indicando um caminho contínuo em linha mais grossa do ponto A ao ponto B, com os dígitos 0 sob os segmentos inferiores percorridos e os dígitos 1 sobre os segmentos superiores percorridos.

a) Desenhe o caminho representado por 1001001100.

Malha retangular idêntica à inicial, com 10 quadradinhos e os pontos A e B indicados.

b) De quantas maneiras diferentes a formiguinha pode ir de A até B?

c) De quantas maneiras diferentes a formiguinha pode ir de A até B passando pelo ponto C?

Malha retangular de 10 quadradinhos com os pontos A no canto inferior esquerdo, B no canto superior direito e o ponto C localizado na borda inferior, no sexto vértice a partir da esquerda.

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 5 (Nível 1) da 2ª fase da OBMEP 2023

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

A formiguinha da OBMEP caminha do ponto A até o ponto B ao longo dos lados dos 10 quadradinhos da figura abaixo.

Malha retangular formada por uma fila horizontal de 10 quadradinhos, com o ponto A no vértice inferior esquerdo e o ponto B no vértice superior direito.

Ela só pode andar para a direita, para cima ou para baixo, sem passar por onde já passou. Para representar um caminho, ela inventou o seguinte código: para cada quadradinho, da esquerda para a direita, se ela passar por baixo, escreve 0 e se passar por cima, escreve 1. Na figura a seguir observamos o caminho representado por 0010100011.

Malha de 10 quadradinhos indicando um caminho contínuo em linha mais grossa do ponto A ao ponto B, com os dígitos 0 sob os segmentos inferiores percorridos e os dígitos 1 sobre os segmentos superiores percorridos.

a) Desenhe o caminho representado por 1001001100.

Malha retangular idêntica à inicial, com 10 quadradinhos e os pontos A e B indicados.

b) De quantas maneiras diferentes a formiguinha pode ir de A até B?

c) De quantas maneiras diferentes a formiguinha pode ir de A até B passando pelo ponto C?

Malha retangular de 10 quadradinhos com os pontos A no canto inferior esquerdo, B no canto superior direito e o ponto C localizado na borda inferior, no sexto vértice a partir da esquerda.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

a)

[Figura: Malha de 10 quadradinhos alinhados horizontalmente, com ponto A no vértice inferior esquerdo e ponto B no vértice superior direito. Um caminho em linha vermelha parte de A, sobe, percorre o lado superior do 1º quadradinho (marcado com 1), desce, percorre a base do 2º e 3º quadradinhos (marcados com 0 e 0), sobe, percorre o lado superior do 4º quadradinho (marcado com 1), desce, percorre a base do 5º e 6º quadradinhos (marcados com 0 e 0), sobe, percorre o lado superior do 7º e 8º quadradinhos (marcados com 1 e 1), desce, percorre a base do 9º e 10º quadradinhos (marcados com 0 e 0) e sobe até B.]

b) Um caminho de A até B é determinado pelas escolhas da formiguinha de como ela vai passar por cada quadradinho. Ela pode escolher se vai passar por baixo (0) ou por cima (1). Dessa maneira, ela tem 10 escolhas a fazer e, para cada escolha, ela tem 2 possibilidades. Como qualquer escolha independe das anteriores, segue que o número de caminhos de A até B é 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 = 2^{10} = 1024.

c) A formiguinha pode passar por C de 3 maneiras diferentes, como mostrado na figura abaixo.

[Figura: Três esquemas com dois quadradinhos adjacentes e o ponto C no vértice inferior comum: no primeiro, o trajeto passa pela base de ambos, com a indicação "0 C 0"; no segundo, o trajeto passa pela parte superior de ambos, com "1 1" no topo e "C" na base; no terceiro, o trajeto percorre a base do primeiro quadradinho, sobe pela aresta vertical sobre C e segue pelo topo do segundo quadradinho, com "0 C" na base e "1" no topo.]

Dessa maneira, para escolher um caminho passando por C, ela pode primeiro escolher uma das 3 possibilidades acima e depois escolher como vai passar pelos outros 8 quadradinhos. Dessa maneira, ela pode ir de A para B passando por C de 3 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 = 3 \times 2^8 = 768 maneiras diferentes.

Outra maneira de resolver esse item é notar que para não passar por C a formiguinha tem que percorrer o seguinte trajeto em seu caminho de A até B e isso pode ser feito de 2^8 maneiras diferentes. Desse modo, ela pode passar por C de 2^{10} - 2^8 = (2^2 - 1) \times 2^8 = 3 \times 2^8 = 768 maneiras diferentes, como antes.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

a) Cada dígito diz por onde ela passa no quadradinho correspondente: 0 é pela borda de baixo e 1 é pela borda de cima. Os trechos verticais aparecem sempre que o dígito muda. Se o primeiro dígito é 1, ela sobe logo em A. Se o último é 0, ela sobe no fim para chegar a B.

Para 1001001100, numerando as retas verticais de 0 (a da esquerda) a 10 (a da direita), o caminho é:

sobe pela reta 0 e anda pela borda de cima do quadradinho 1;
desce pela reta 1 e anda por baixo dos quadradinhos 2 e 3;
sobe pela reta 3 e anda por cima do quadradinho 4;
desce pela reta 4 e anda por baixo dos quadradinhos 5 e 6;
sobe pela reta 6 e anda por cima dos quadradinhos 7 e 8;
desce pela reta 8 e anda por baixo dos quadradinhos 9 e 10;
sobe pela reta 10 e chega a B.

O desenho é esse caminho, com subidas nas retas 0, 3, 6 e 10 e descidas nas retas 1, 4 e 8.

b) Cada código de 10 dígitos corresponde a exatamente um caminho, e cada caminho gera um único código. Ela só pode cruzar cada reta vertical uma vez, porque subir e descer pelo mesmo segmento seria repetir o trecho. Logo, em cada um dos 10 quadradinhos ela escolhe entre 2 possibilidades (0 ou 1), de forma independente:

2^{10}=1024.

Há 1024 caminhos.

c) Pela figura, C está na borda de baixo, na reta vertical 6, ou seja, depois de 6 quadradinhos. Vejamos quais códigos passam por C, olhando os dígitos 6 e 7, que são os dos quadradinhos vizinhos a essa reta:

dígito 6 = 0: ela chega a C por baixo, então passa por C, e o dígito 7 pode ser 0 ou 1;
dígito 6 = 1 e dígito 7 = 0: ela desce pela reta 6 até C e segue por baixo, então passa por C;
dígito 6 = 1 e dígito 7 = 1: ela fica em cima e nunca toca C.

Portanto os dígitos 6 e 7 têm 4-1=3 possibilidades. Os dígitos 1 a 5 são livres (2^5=32) e os dígitos 8 a 10 também (2^3=8):

32\cdot 3\cdot 8=768.

Outra forma de ver: 1024 caminhos no total menos os 2^8=256 que têm os dígitos 6 e 7 iguais a 1, o que dá 768.

Há 768 caminhos passando por C.

Assunto: Princípio fundamental da contagem.

Reportar erro na resolução

Ver como caiu na prova

Questão 5 no caderno Nível 1 da 2ª fase da OBMEP 2023

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