Questão 3 (Nível 3) da 2ª fase da OBMEP 2015

Question

Mônica desenha caminhos poligonais em tabuleiros formados por quadradinhos de 1 cm de lado. Cada caminho começa e termina na borda do tabuleiro, contém somente esses dois pontos da borda e nunca passa duas vezes por um mesmo ponto.

Por exemplo, no tabuleiro 4 \times 4 ao lado, ela desenhou um desses caminhos com 6 cm de comprimento.

Tabuleiro de 4 por 4 quadradinhos com uma linha poligonal preta destacada de 6 cm de comprimento, partindo da borda superior e terminando na borda inferior.

a) Trace um possível caminho desenhado por Mônica no tabuleiro 4 \times 6 abaixo, com 16 cm de comprimento.

Grade retangular de 4 por 6 quadradinhos.

b) Explique por que o comprimento, em centímetros, do maior caminho que Mônica pode desenhar em um tabuleiro m \times n é igual a (m-1)(n-1)+1.

c) Há vários tipos diferentes de tabuleiros retangulares com 100 quadradinhos. Mônica formou tabuleiros de todos esses tipos e, em cada um, ela desenhou um caminho com o maior comprimento possível. Qual é o comprimento do maior desses caminhos?

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 3 (Nível 3) da 2ª fase da OBMEP 2015

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

Mônica desenha caminhos poligonais em tabuleiros formados por quadradinhos de 1 cm de lado. Cada caminho começa e termina na borda do tabuleiro, contém somente esses dois pontos da borda e nunca passa duas vezes por um mesmo ponto.

Por exemplo, no tabuleiro 4 \times 4 ao lado, ela desenhou um desses caminhos com 6 cm de comprimento.

Tabuleiro de 4 por 4 quadradinhos com uma linha poligonal preta destacada de 6 cm de comprimento, partindo da borda superior e terminando na borda inferior.

a) Trace um possível caminho desenhado por Mônica no tabuleiro 4 \times 6 abaixo, com 16 cm de comprimento.

Grade retangular de 4 por 6 quadradinhos.

b) Explique por que o comprimento, em centímetros, do maior caminho que Mônica pode desenhar em um tabuleiro m \times n é igual a (m-1)(n-1)+1.

c) Há vários tipos diferentes de tabuleiros retangulares com 100 quadradinhos. Mônica formou tabuleiros de todos esses tipos e, em cada um, ela desenhou um caminho com o maior comprimento possível. Qual é o comprimento do maior desses caminhos?

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

a)

Podemos traçar várias linhas poligonais diferentes de comprimento 16 cm, as quais dividem o tabuleiro em duas regiões. Abaixo estão alguns exemplos.

[Figura: cinco malhas quadriculadas de dimensões 5 por 5 exibindo diferentes linhas poligonais em vermelho que começam e terminam no bordo do tabuleiro, cada uma de comprimento 16 cm, dividindo o tabuleiro em duas regiões.]

b)

O comprimento de qualquer linha poligonal que começa e termina na borda do tabuleiro sempre será igual à quantidade de vértices dos quadradinhos que estão no interior do tabuleiro pelos quais o caminho passa, mais um. Assim, a linha poligonal de maior comprimento deve ter os seus pontos inicial e final no contorno do tabuleiro e passar por todos os vértices dos quadradinhos que estão no seu interior. Sempre é possível fazer um caminho assim, por exemplo serpenteando o interior do tabuleiro como na primeira figura acima. O número de vértices dos quadradinhos que estão no interior do tabuleiro m \times n é (m - 1)(n - 1), pois, nos lados do contorno do tabuleiro

c)

Dentre todos os tabuleiros possíveis com 100 casas, o comprimento da maior linha poligonal que Mônica traçou é 82 cm, pois para os comprimentos dos lados de tabuleiros retangulares com 100 quadradinhos temos as possibilidades listadas no quadro abaixo.

Comprimentos dos lados m \times n	Comprimento da maior poligonal (m - 1)(n - 1) + 1
1 \times 100	0 \times 99 + 1 = 1\text{ cm}
2 \times 50	1 \times 49 + 1 = 50\text{ cm}
4 \times 25	3 \times 24 + 1 = 73\text{ cm}
5 \times 20	4 \times 19 + 1 = 77\text{ cm}
10 \times 10	9 \times 9 + 1 = 82\text{ cm}

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

a) Coloque os vértices da malha em coordenadas (x,y), com x de 0 a 6 (largura) e y de 0 a 4 (altura). Os vértices internos são (x,y) com x=1,\dots,5 e y=1,2,3, ou seja, 15 pontos. Como o caminho de 16 cm tem 16 segmentos, ele passa por 17 pontos: 2 na borda e 15 internos. Então o caminho precisa passar por todos os pontos internos, uma única vez.

Faça um "zigue-zague" vertical:

Comece na borda em (1,0) e suba até (1,3): 3 cm.
Vá para (2,3) (1 cm) e desça até (2,1) (2 cm).
Vá para (3,1) (1 cm) e suba até (3,3) (2 cm).
Vá para (4,3) (1 cm) e desça até (4,1) (2 cm).
Vá para (5,1) (1 cm) e suba até (5,3) (2 cm).
Suba mais 1 cm até (5,4), que está na borda.

Total: 3+1+2+1+2+1+2+1+2+1=16 cm. O caminho só toca a borda no início e no fim e não repete pontos.

Um caminho possível é o zigue-zague descrito, de (1,0) a (5,4), com 16 cm.

b) Num tabuleiro m\times n, os vértices internos da malha formam uma grade de (m-1) linhas e (n-1) colunas. São (m-1)(n-1) pontos.

Limite superior. Um caminho com k segmentos de 1 cm passa por k+1 pontos da malha, todos distintos. Dois deles são os extremos, que estão na borda. Os outros k-1 pontos não estão na borda, logo são internos. Assim k-1\le (m-1)(n-1), ou seja, k\le (m-1)(n-1)+1.

Esse valor é atingido. Faça o zigue-zague do item (a). Entre pela borda inferior na primeira coluna de pontos internos e suba até o topo da coluna. Ande 1 cm para a coluna seguinte, desça toda ela, e assim por diante, percorrendo todas as colunas. Na última coluna, saia pela borda, para cima ou para baixo, conforme o ponto em que o caminho chegou. Todos os (m-1)(n-1) pontos internos são visitados uma só vez, e os dois extremos estão na borda. Logo o caminho tem (m-1)(n-1)+1 segmentos.

Portanto o maior comprimento é (m-1)(n-1)+1 cm.

c) Os tabuleiros com 100 quadradinhos têm m\times n com mn=100. Os pares possíveis, a menos da ordem, são 1\times100, 2\times50, 4\times25, 5\times20 e 10\times10.

Usando o item (b):

(m-1)(n-1)+1=mn-(m+n)+2=102-(m+n).

O comprimento é maior quando m+n é menor. Calculando cada caso:

1\times100: 1 cm
2\times50: 49+1=50 cm
4\times25: 3\cdot24+1=73 cm
5\times20: 4\cdot19+1=77 cm
10\times10: 9\cdot9+1=82 cm

O maior valor ocorre no tabuleiro 10\times10.

82 cm

Assuntos: Lógica e raciocínio lógico, Divisibilidade, MMC e MDC.

Reportar erro na resolução

Ver como caiu na prova

Questão 3 no caderno Nível 3 da 2ª fase da OBMEP 2015

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