Desafio Semanal

Professor Ricardo tem n chips supostamente idênticos que, em princípio, são capazes de testar uns aos outros. Um testador do professor acomoda dois chips ao mesmo tempo. Quando os chips são carregados, cada chip testa o outro e relata se é bom ou ruim. Um bom chip de sempre relata com precisão se o outro chip é bom ou ruim, mas a resposta de um mau chip não pode ser confiável. Assim, os quatro possíveis resultados de um teste são como se segue:

Chip A	Chip B	Conclusão
B é bom	A é bom	ambos são bons, ou ambos são ruins
B é bom	A é ruim	pelo menos um é ruim
B é ruim	A é bom	pelo menos um é ruim
B é ruim	A é ruim	pelo menos um é ruim

a. Mostre que, se mais de n / 2 chips são ruins, o professor pode não determina necessariamente quem são os bons chips usando qualquer estratégia com base neste tipo de teste emparelhado. Suponha que os maus chips podem conspirar para enganar o professor.

b. Considere o problema de encontrar um único chip de bom entre n chips, supondo que o mais que n / 2 dos chips são bons. Mostre que  ⎣ n / 2 ⎦ testes de pares são suficientes para reduzir o problema para aproximadamente a metade do tamanho.

c. Mostre que os bons chips podem ser identificados com Θ (n) testes emparelhados, assumindo que mais que n / 2 dos chips são bons. Dê e resolva a recorrência que descreve o número de testes.