Questão 2 (Nível 1) da OBMEP 2016

Resolução comentada

Cortar um anel o libera de todos os que estavam presos a ele. Então o problema é escolher o menor conjunto de anéis cortados de modo que nenhum par de anéis entrelaçados continue com os dois inteiros.

Vamos listar os pares entrelaçados, conforme a figura (V = vermelho, VC = verde-claro, AE = azul-escuro, AC = azul-claro, R = rosa, VE = verde-escuro):

1. AC–V
2. AC–VC
3. AC–VE
4. R–VC
5. R–AE
6. R–VE

Cada par precisa ter pelo menos um anel cortado.

O AC participa de 3 pares (1, 2, 3) e o R participa de 3 pares (4, 5, 6). Esses dois conjuntos de pares cobrem todos os 6 pares. Cortando AC e R, todos os pares ficam resolvidos: 2 cortes.

Para ver que 1 corte não basta, observe que os pares AC–V e R–AE não têm nenhum anel em comum. Um único anel cortado não pode estar nos dois pares ao mesmo tempo. Logo, são necessários pelo menos 2 cortes.

Portanto, o mínimo é 2.

Alternativa B.

Por que as outras alternativas estão erradas

• AUm só corte não resolve, pois os pares AC–V e R–AE não têm anel em comum.
• CTrês cortes funcionam, mas não é o mínimo, já que cortar o azul-claro e o rosa basta.
• DQuatro cortes é exagero; cortar só os dois anéis do meio libera todos.
• ECortar cinco anéis seria soltar todos menos um, longe do mínimo.

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

Reportar erro na resolução

O que está errado?

Conta ou raciocínio errado Chega em outra resposta Explicação confusa Outro problema

Detalhes (opcional) Não preencha

Enviar Sem cadastro: não guardamos quem enviou.