MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-072

Enunciado: Considere o seguinte tabuleiro 3x4 onde cada quadrado contém um número de pontos:

Imagine agora um jogo jogado neste tabuleiro, em que o objetivo consiste em deslocar sua peça do canto superior esquerdo até o canto inferior direito, através de uma sequência de movimentos para a direita ou para baixo, de forma de minimizar o somatório dos pontos correspondentes aos quadrados pelos quais você passou.  O jogo pode ser descrito como um problema de caminhos mínimos no grafo mostrado na figura abaixo:

Nestas condições, ao resolvermos o problema, quantos quadrados com número par de pontos NÃO estarão no caminho ótimo ?

(a) 2

(b) 3

(c) 4

(d) 5

(e) NDA

Ideia original de: Lucas Miguel de Carvalho