프로그래머 두뇌 단련(2) 동로마의 내기꾼들

이 문제의 이름의 의미는 관리들의 암투와 음모를 연상시키게 한다고 한다.

돈을 걸어 내기의 결과에 따라 돈을 버는 문제인데 내기의 내용은 다음과 같다.

도전자 외에 여러명의 "조언자"들이 있다. 도전자를 제외한 조언자들은 각자 1이나 0을 적고 서로 숫자를 보여준다.

그다음 종이를 엎어서 도전자 앞에 놓는다. 각 조언자는 도전자에게 종이에 적힌 숫자가 무엇인지 알려준다. 그러나 항상 진실을 말하진 않는다.

각 내기에서 도전자는 그 종이에 써있는 숫자를 선택하고, 조언자들의 말을 참고하여 돈을 건다. 내기돈은 0~올인으로 선택할 수 있다. 정답일 경우 걸은 돈의 2배를 얻고 실패하면 돈을 잃는다.

1. 조언자가 네 명이고 그 중 둘은 항상 진실을 이야기하나 누가 진실을 이야기하는지는 알 수 없다고 하자. 도전자가 총 세 번 내기를 할 수 있고 초기 소지금이 $100라고 할 때, 반드시 돈을 딸 수 있으려면 어떤 전략을 취해야 할까?

2. 이제 조언자가 세 명이고 그 중 한 명만 진실을 말한다고 하자. 이번에도 세 번의 내기를 할 수 있으며 초기 소지금은 $100이다. 반드시 돈을 딸 수 있는 전략은 무엇일까?

 

---

이제 게임을 좀 더 복잡하게 만들어 보자. 우선 총 네 번의 내기를 걸기로 한다. 그런데 이번에는 진실을 말하는 조언자들 대신 오직 "부분적으로만 진실을 말하는" 조언자들이 있을 뿐이다. 구체적으로 말하자면, 그런 조언자들은 네 번 중 적어도 세 번은 반드시 진실을 말해야 한다. 더 나아가서, 조언자들은 도전자를 골탕먹이기 위해 도전자가 선택한 숫자를 들은 후 종이 조각에 적힌 숫자를 바꿀 수도 있다. 그러나 부분적으로 진실을 말하는 조언자가 하나도 없게 되도록 숫자를 바꾸지는 못한다.

 

3. 조언자가 네 명이며 그 중 셋은 임의로 거짓말을 할 수 있으나 한 명은 반드시 네 번 중 적어도 세 번은 반드시 진실을 말해야 한다고 할 때, 네 번의 내기에서 결과적으로 확실히 돈을 딸 수 있는 전략은 무엇일까?

 

4. 3번과 같은 조건이되 내기가 총 다섯 번이라고 할 때, 최종적인 소지금이 적어도 $150가 되게 하려면 어떻게 해야 할까?