Uma Solução para O Problema do Rei e dos Bruxos Bons e Maus

O Problema:

O rei convidou 2015 bruxos para um encontro. Alguns dos bruxos são bons e outros são maus. Um bruxo bom sempre fala a verdade, enquanto um bruxo mau pode falar o que quiser. Os bruxos sabem quem é bom e quem é mau, mas o rei não.
Durante o encontro, o rei pede para cada bruxo responder uma pergunta cuja resposta é sim ou não. Em seguida ele expulsa um dos bruxos do reino. O bruxo expulso sai por uma porta mágica, a qual permite ao rei perceber se ele era bom ou mau.
Em seguida o rei começa a próxima rodada de perguntas e expulsa outro bruxo. Ele continua repetindo este procedimento até parar.Prove que o rei consegue expulsar todos os bruxos maus, enquanto expulsou não mais que um bruxo bom.

A Solução

Alguns dos bruxos são bons (BOM) e os outros são maus (MAU). Podemos deduzir que pelo menos dois bruxos são bons e que pelo menos dois bruxos são maus.

O REI separa um bruxo B1 (BOM ou MAU) e pergunta a cada um dos demais se B1 é BOM.

Caso 1: Se todos disserem que SIM, então de fato ele é, pois pelo menos um BOM naquele meio falou a verdade. Resolvido‼ Note, agora, que o REI possui um aliado BOM ao seu lado e não irá descartá-lo, pois poderá usá-lo para expulsar todos os MAUS do grupo. Por exemplo, na próxima rodada de perguntas, o REI poderá apontar para qualquer um dos bruxos e perguntar ao seu aliado BOM se ele é bom. Caso o BOM diga SIM então esse outro é BOM também. Nesse caso, o REI aponta para um outro bruxo e pergunta para o novo BOM se ele é bom. Se for SIM, então o REI ganhou mais um aliado e se for NÃO, então ele expulsa o MAU. Para expulsar todos os demais MAUS, o REI deve usar a mesma estratégia...

Caso 2: Se todos disserem que ele é MAU, então de fato ele é, pois pelo menos um BOM falou a verdade naquele meio; (o REI expulsa B1 e escolhe outro bruxo e recomeça). Note que, enquanto isso acontecer, o REI continuará expulsando bruxos MAUS, até parar.

Caso 3: Se um grupo disser SIM e os demais disserem NÃO, então, nesse caso, o REI deverá perguntar a B1 se um Bs (um Bruxo que disse SIM) é BOM e, independentemente da resposta de B1, o REI deve expulsar Bs.

Caso 3.1: Se Bs for BOM então B1 é BOM (Resolvido, pelo Caso 1). Note que, nesse caso, B1 obrigatoriamente deve dizer que Bs é BOM, pois ambos são bons. Seria absurdo ter um Bs bom dizendo que B1 é bom e B1 dizendo que esse Bs é mau.

Caso 3.2: Se B1 disser que Bs é BOM e se for detectado que Bs é MAU, então o REI não gastou seu "cartucho" e sabe que tanto B1 quanto todos que disseram SIM são Maus. Agora, o REI deve escolher um M2 no meio dos que disseram NÃO e recomeçar...

Caso 3.3: Se B1 disser que Bs é MAU, e de fato for, então o REI não gastou seu "cartucho", e deverá recomeçar com todos (inclusive com B1)

Caso 3.4: (Impossível de ocorrer) Se B1 disser que Bs é MAU, e ele ser BOM, é um paradoxo.

Solução de:
Josué Gomes (UERR) 

e Reginaldo Beltrami (IFRR)