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

Question

Um terreno quadrado foi dividido em 9 lotes também quadrados, cercados por muros. Câmeras instaladas no encontro de dois ou mais muros vigiam os muros adjacentes ao ponto de instalação. Na figura temos duas câmeras vigiando 6 muros.

Grade de 3 por 3 quadrados com linhas tracejadas, contendo duas câmeras indicadas por círculos pretos: uma na borda superior e outra na interseção interna abaixo dela, destacando em linha contínua preta os 6 muros adjacentes a elas.

a) Indique uma posição de duas câmeras na figura abaixo de modo que elas vigiem a maior quantidade possível de muros.

Grade de 3 por 3 quadrados formada por linhas tracejadas.

b) Qual é o número mínimo de câmeras necessárias para vigiar os 12 muros na fronteira do terreno? Justifique sua resposta.

c) Encontre o número mínimo de câmeras necessárias para vigiar todos os muros do terreno. Justifique sua resposta.

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

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

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

Um terreno quadrado foi dividido em 9 lotes também quadrados, cercados por muros. Câmeras instaladas no encontro de dois ou mais muros vigiam os muros adjacentes ao ponto de instalação. Na figura temos duas câmeras vigiando 6 muros.

Grade de 3 por 3 quadrados com linhas tracejadas, contendo duas câmeras indicadas por círculos pretos: uma na borda superior e outra na interseção interna abaixo dela, destacando em linha contínua preta os 6 muros adjacentes a elas.

a) Indique uma posição de duas câmeras na figura abaixo de modo que elas vigiem a maior quantidade possível de muros.

Grade de 3 por 3 quadrados formada por linhas tracejadas.

b) Qual é o número mínimo de câmeras necessárias para vigiar os 12 muros na fronteira do terreno? Justifique sua resposta.

c) Encontre o número mínimo de câmeras necessárias para vigiar todos os muros do terreno. Justifique sua resposta.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

Item a) Como cada câmera pode vigiar no máximo 4 muros, o máximo que duas câmeras podem vigiar são 8 muros. A figura ilustra um exemplo em que esse máximo ocorre.

[Figura: Malha quadriculada 3 por 3 com linhas pontilhadas, destacando duas câmeras representadas por pontos pretos e 8 segmentos de reta em linha contínua vigiados por elas.]

Item b) Uma câmera na fronteira vigia exatamente 2 muros dessa região. Como apenas câmeras na fronteira podem vigiar os muros dessa região e existem exatamente 12 muros nela, o mínimo de câmeras necessárias é \frac{12}{2} = 6. A figura ilustra um exemplo com essa quantidade de câmeras.

[Figura: Malha quadriculada 3 por 3 com linhas internas pontilhadas e o contorno externo em linha contínua, com 6 câmeras representadas por pontos pretos distribuídas na fronteira.]

Item c) Uma câmera posicionada no interior não pode vigiar nenhum muro da fronteira, portanto, pelo item anterior precisamos de pelo menos 6 câmeras nessa região para vigiar seus 12 muros. Nenhuma das câmeras posicionadas na fronteira pode vigiar os 4 muros do quadrado central e, como qualquer câmera só pode vigiar 2 deles, precisamos de pelo menos 2 câmeras para vigiar esses 4 muros. Assim, precisamos de pelo menos 6 + 2 = 8 câmeras para vigiar os muros. A figura mostra que é possível vigiar todos eles com essa quantidade, garantindo assim que esse número é o mínimo.

[Figura: Grade quadriculada 3 por 3 com todos os segmentos em linha contínua e 8 câmeras representadas por pontos pretos posicionadas nos vértices da grade.]

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

a) Cada câmera vigia no máximo 4 muros, que é o caso de um ponto interno (encontro de 4 muros). Então duas câmeras vigiam no máximo 4+4=8 muros. Para chegar a 8, os dois pontos precisam ser internos e não podem ter um muro em comum, senão esse muro seria contado duas vezes.

O terreno tem 4 pontos internos, os vértices do quadrado central. Dois pontos internos vizinhos compartilham um muro, mas dois pontos internos em diagonal não. Basta colocar as câmeras em dois pontos internos opostos pela diagonal do quadrado central, por exemplo o ponto superior esquerdo e o inferior direito. Assim vigiam 4+4=8 muros distintos, que é o máximo.

Resposta: duas câmeras em dois pontos internos em diagonal, vigiando 8 muros.

b) Os 12 muros da fronteira formam um contorno fechado com 12 pontos (4 cantos e 8 pontos no meio dos lados). Veja quantos muros da fronteira cada câmera vigia:

câmera em canto: 2 muros da fronteira;
câmera em ponto do meio de um lado: 2 muros da fronteira (o terceiro muro dela é interno);
câmera em ponto interno: 0 muro da fronteira.

Logo, cada câmera vigia no máximo 2 muros da fronteira. Para cobrir 12 muros são necessárias pelo menos 12\div 2=6 câmeras.

Seis câmeras bastam: percorrendo o contorno, numere os 12 pontos e coloque câmeras em um sim, um não (6 pontos). Cada muro da fronteira liga dois pontos consecutivos, e um deles tem câmera.

Resposta: 6 câmeras.

c) O terreno tem 24 muros (12 horizontais e 12 verticais) e 16 pontos, dispostos em 4 linhas de 4 pontos.

Mínimo. Em cada linha horizontal de 4 pontos, separe os muros horizontais em dois pares: o muro entre o 1º e o 2º ponto e o muro entre o 3º e o 4º ponto. Isso dá 4\times 2=8 muros que não têm ponto em comum. Uma câmera num ponto vigia no máximo um desses 8 muros, porque cada ponto pertence a no máximo um deles. Para vigiar os 8 muros são necessárias pelo menos 8 câmeras.

Construção. Pinte os 16 pontos como um tabuleiro de xadrez e coloque câmeras nos 8 pontos de uma das cores. Todo muro liga dois pontos de cores diferentes, então tem sempre uma extremidade com câmera. Assim os 24 muros ficam vigiados com 8 câmeras.

Resposta: 8 câmeras.

Assunto: Lógica e raciocínio lógico.

Reportar erro na resolução

Ver como caiu na prova

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

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