100명의 죄수가 살아남을 확률을 높이기 위한 루프 전략 (Loop Strategy)

C, C++ 전체 링크

 

무한히 작은 확률을 30%까지 올리는 기적의 전략
확률 1000000000000000000000000000000배 높이기 구현 with Veritasium
https://www.youtube.com/watch?v=PE4vLbyOgw0

▲ 유튜버 베리타시움의 영상인 퀴즈를 직접 구현해보자.
영상이 길다면 fmkorea의 요약본을 보자.

1부터 100까지 번호가 매겨진 죄수가 있다.
이때 각 죄수의 번호가 적힌 쪽지가 100개의 상자에 무작위로 담겨있다.
죄수들은 한 번에 한 명씩 방에 들어가서 50개의 상자를 열 수 있다. - 이때, 자신의 번호를 찾아야 한다.
50개를 모두 열어본 후에는 방을 들어왔던 상태와 완벽히 동일하게 복구하고 나가야 한다.
만약 100명의 죄수가 모두 자신의 번호를 찾으면 모두 석방된다.
하지만 한 명이라도 번호를 찾지 못하면 모두 사형이다.

죄수들이 모두 살아날 확률은? (자신의 번호를 모두 찾을 확률은?)

→ 각 죄수가 번호를 찾을 확률이 50%, 100명의 경우라면 (1/2)¹⁰⁰ 가 된다.

 

→ 그러나 자신의 번호가 적힌 상자를 열고,
그 상자 속 숫자를 보고 그 숫자가 적힌 상자로 다시 이동하고,
자신의 번호가 있는 쪽지를 찾을 때까지 반복하면 확률이 약 30% 이상이 된다. (루프 전략)

---

구현

아래의 define을 정의하고 시작한다.
죄수의 수가 정해진다면, 박스를 선택할 횟수는 죄수의 수의 절반이다.
그리고 박스를 섞는 것은 죄수의 수 10배 정도면 충분하다.
테스트 횟수(TESTCASE)에 대해 몇 번 성공하는지 확인해보자.

#define NUMBER_OF_PRISONER (100) /* 죄수의 수 */
#define LIMIT_OF_BOXCOUNT (NUMBER_OF_PRISONER / 2) /* 죄수가 열어볼 수 있는 상자의 수 */
#define SHUFFLE_COUNT (NUMBER_OF_PRISONER * 10) /* 박스를 섞을 횟수 */
#define TESTCASE (10000) /* 테스트 횟수 */

i번째 box에 i를 저장하고 셔플 알고리즘을 이용하여 랜덤으로 카드를 적절히 섞는다.

void boxShuffle()
{
	for (int i = 1; i <= NUMBER_OF_PRISONER; i++) box[i] = i;

	for (int i = 1; i <= SHUFFLE_COUNT; i++)
	{
		int a = rand() % NUMBER_OF_PRISONER + 1;
		int b = rand() % NUMBER_OF_PRISONER + 1;

		int tmp = box[a];
		box[a] = box[b];
		box[b] = tmp;
	}
}

먼저 랜덤으로 박스를 찾아보자.
자신의 번호(startNumber)를 LIMIT_OF_BOXCOUNT만큼 랜덤으로 박스를 열어본다.
LIMIT_OF_BOXCOUNT 번 내에 찾으면 true, 그렇지 않으면 false를 반환한다.

bool findBoxRandom(int startNumber)
{
	bool checkBox[NUMBER_OF_PRISONER] = { false };

	for (int boxCount = 1; boxCount <= LIMIT_OF_BOXCOUNT;)
	{
		int random = rand() % NUMBER_OF_PRISONER + 1;
		int boxNumber = box[random];

		if (boxNumber == startNumber) return true;

		if (checkBox[boxNumber] == false)
		{
			checkBox[boxNumber] = true;
			boxCount++;
		}
	}

	return false;
}

findBoxWithNoStrategy는 박스를 한 번 섞고,
1번 부터 모든 죄수 (NUMBER_OF_PRISONER)가 자신의 번호를 findBoxRandom으로 찾는다.
한 명이라도 실패하면 findBoxWithNoStrategy는 false를 리턴하게 된다.

bool findBoxWithNoStrategy()
{	
	boxShuffle();

	for (int i = 1; i <= NUMBER_OF_PRISONER; i++)
		if (findBoxRandom(i) == false) return false;

	return true;
}

영상에서 소개한 루프 전략을 구현하면 다음과 같다.
현재의 번호로 박스를 열어서(=box[currentNumber]), 자신의 번호(startNumber)와 같으면 함수를 종료한다.
이때, 함수를 몇번 재귀 호출 했는지가 박스를 연 횟수(openCount)가 된다.
openCount가 LIMIT_OF_BOXCOUNT보다 작으면 true를 리턴하면 된다.

bool findBoxLoop(int startNumber, int currentNumber, int openCount)
{
	if (box[currentNumber] == startNumber)
	{
		if (openCount <= LIMIT_OF_BOXCOUNT) return true;
		else return false;
	}

	return findBoxLoop(startNumber, box[currentNumber], openCount + 1);
}

findBoxWithLoopStrategy도 NoStrategy와 마찬가지로 하나라도 실패하면 false를 return한다.

bool findBoxWithLoopStrategy()
{
	boxShuffle();

	for (int i = 1; i <= NUMBER_OF_PRISONER; i++)
		if (findBoxLoop(i, i, 1) == false) return false;

	return true;
}

main에서 각 전략을 실행해보자.

int main()
{
	int success = 0;

	printf("NUMBER_OF_PRISONER : %d\n", NUMBER_OF_PRISONER);

	for (int tc = 1; tc <= TESTCASE; tc++)
		success += findBoxWithNoStrategy();
	
	printf("No Strategy : %d / %d\n", success, TESTCASE);

	success = 0;
	for (int tc = 1; tc <= TESTCASE; tc++)
		success += findBoxWithLoopStrategy();
	
	printf("Loop Strategy : %d / %d\n", success, TESTCASE);

	return 0;
}

실행결과는 다음과 같다.

죄수가 100명인 경우 / TESTCASE 10,000회

죄수가 100명인 경우 / TESTCASE 50,000회

죄수가 500명인 경우 / TESTCASE 10,000회

영상에서 본 것과 같이 랜덤으로 박스를 선택하는 경우는 0%지만,

루프 전략으로 죄수가 모두 살아남을 확률은 30% 이상이다.

전체 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>

#define NUMBER_OF_PRISONER (100) /* 죄수의 수 */
#define LIMIT_OF_BOXCOUNT (NUMBER_OF_PRISONER / 2) /* 죄수가 열어볼 수 있는 상자의 수 */
#define SHUFFLE_COUNT (NUMBER_OF_PRISONER * 10) /* 박스를 섞을 횟수 */
#define TESTCASE (50000) /* 테스트 횟수 */

int box[NUMBER_OF_PRISONER + 1];

void boxShuffle()
{
	for (int i = 1; i <= NUMBER_OF_PRISONER; i++) box[i] = i;

	for (int i = 1; i <= SHUFFLE_COUNT; i++)
	{
		int a = rand() % NUMBER_OF_PRISONER + 1;
		int b = rand() % NUMBER_OF_PRISONER + 1;

		int tmp = box[a];
		box[a] = box[b];
		box[b] = tmp;
	}
}

bool findBoxRandom(int startNumber)
{
	bool checkBox[NUMBER_OF_PRISONER] = { false };

	for (int boxCount = 1; boxCount <= LIMIT_OF_BOXCOUNT;)
	{
		int random = rand() % NUMBER_OF_PRISONER + 1;
		int boxNumber = box[random];

		if (boxNumber == startNumber) return true;

		if (checkBox[boxNumber] == false)
		{
			checkBox[boxNumber] = true;
			boxCount++;
		}
	}

	return false;
}

bool findBoxWithNoStrategy()
{	
	boxShuffle();

	for (int i = 1; i <= NUMBER_OF_PRISONER; i++)
		if (findBoxRandom(i) == false) return false;

	return true;
}

bool findBoxLoop(int startNumber, int currentNumber, int openCount)
{
	if (box[currentNumber] == startNumber)
	{
		if (openCount <= LIMIT_OF_BOXCOUNT) return true;
		else return false;
	}

	return findBoxLoop(startNumber, box[currentNumber], openCount + 1);
}

bool findBoxWithLoopStrategy()
{
	boxShuffle();

	for (int i = 1; i <= NUMBER_OF_PRISONER; i++)
		if (findBoxLoop(i, i, 1) == false) return false;

	return true;
}

int main()
{
	int success = 0;

	printf("NUMBER_OF_PRISONER : %d\n", NUMBER_OF_PRISONER);

	for (int tc = 1; tc <= TESTCASE; tc++)
		success += findBoxWithNoStrategy();
	
	printf("No Strategy : %d / %d\n", success, TESTCASE);

	success = 0;
	for (int tc = 1; tc <= TESTCASE; tc++)
		success += findBoxWithLoopStrategy();
	
	printf("Loop Strategy : %d / %d\n", success, TESTCASE);

	return 0;
}