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.
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)
Josué Gomes (UERR)
e Reginaldo Beltrami (IFRR)
Problema muito interessante!
ResponderExcluirSolução Melhor ainda kkkk
ExcluirKkkk... É vero!
ResponderExcluirKkkk... É vero!
ResponderExcluir