É lógico!

Ok. Todo mundo está perguntando que questão complicada foi aquela da minha entrevista. Vou tentar reproduzi-la aqui. Trata-se de uma questão que envolve mais lógica e matemática do que propriamente programação. Em todo caso, ela foi proposta na segunda entrevista, pelo CTO da empresa. A princípio ele pediu para eu desenhar algum projeto que tivesse desenvolvido. Depois ele me veio com essa:

Considere uma empresa que produz peças: parafusos e porcas. Os parafusos pesam 11g e as porcas, 10g. Para atender a uma encomenda de porcas, foi separado um certo número de caixas, mas, por engano, uma das caixas continha parafusos, só que agora todas as caixas já estão fechadas. É preciso descobrir qual é a caixa errada!
Suponha-se um sistema automático que pode coletar uma determinada quantidade de peças de uma determinada caixa e guardar numa bandeja e pode também levar o conteúdo da bandeja para uma balança. A primeira ação é executada por uma função void pegar(int numPecas, int caixa); e a segunda por uma função int pesar(); embora isso seja meramente ilustrativo, porque não precisava escrever o programa, mas apenas demonstrar a minha maneira de raciocinar (se bem que essas funções acabaram me dando uma dica importante no final).
O problema é montar um algoritmo que execute essas operações (um programa que chame essas funções) para determinar qual é a caixa que contém parafusos em vez de porcas.
A princípio, ele disse que era apenas uma maneira de observar a minha maneira de pensar e resolver problemas. Por isso eu comecei com a solução mais simples: pegar uma peça da primeira caixa e pesar, depois uma da segunda e assim sucessivamente até encontrar um parafuso. Depois ele pediu para considerar a balança como um recurso caro que precisa ser otimizado e pediu para elaborar um algoritmo que executasse menos pesagens. Eu propus uma solução com busca binária (ele me pediu até a função matemática que descreve a eficiência da busca binária). Por fim, ele disse que a balança era um recurso muito, muito caro e perguntou se eu poderia fazer um algoritmo com o mínimo de pesagens possível. Ele até saiu da sala para deixar eu pensando. Se bem que a resposta me veio logo que ele saiu. Na verdade esse é um problema clássico de lógica que aparece em muitos livrinhos de passatempo. Apesar disso, depois que eu dei a resposta, ele disse que mais ou menos 90% das pessoas não conseguem chegar a essa solução.
Alguém mais sabe a resposta?