MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3091 6140

E-MAIL cef@ime.usp.br

MAC 330 - Programação Inteira - MAC 5780

Segundo semestre de 2002

Desafio do Exercício 1 - Entrega: 2 de dezembro de 2002

Resolução do problema dos pesos

No primeiro EP vocês escreveram modelos (baseados em Programação Inteira ou não) para o problemas dos 7 pesos, definido a seguir:

• O problema dos 7 pesos
  Em uma viagem à Amazonia foi descoberta uma tribo de índios com um estranho ritual. Neste, cada membro da tribo (com idade maior ou igual a um ano) deveria trazer para a festa uma quantidade de milho proporcional à sua idade. As ofertas eram medidas usando 7 pesos rituais, porém em cada medição no máximo três deles poderiam ser usados (não necessariamente do mesmo lado da balança). Uma lenda da tribo diz que se alguém vivesse tanto que fosse impossível medir sua contribuição usando os pesos rituais, os deuses se irritariam e as colheitas de milho seriam escassas para sempre. Coincidentemente, semanas antes da festa desse ano o mais velho da tribo morreu, para grande alívio do cacique e todos na tribo. Determine quais são os sete pesos rituais e qual a idade crítica que o ancião havia atingido.

Neste desafio vocês deverão resolver o problema, apresentando os pesos, a idade crítica e a estratégia de solução utilizada. O exercício poderá ser feito em grupos de qualquer tamanho, e os grupos poderão obter um bônus de até 5 pontos na nota do primeiro EP (inclusive se sua nota naquele EP foi maior que 5). Utilizem a mailing list da disciplina para discutir o problema!