티스토리 뷰
우리가 술 게임으로 즐겨하는(하곤 했던) 베스킨라빈스 게임에 수학적으로 접근해봅시다.
우선 게임 방식을 설명해봅시다.
게임 규칙 :
n명이 돌아가며 1부터 31까지의 숫자를 순서대로 말하는데
각자 자신의 차례 때 최소 1개, 최대 3개까지 말할 수 있다.
이때 31을 말하는 사람이 주인공이 된다.
**문제 설정 :**
**2명(n=2)이 베스킨을 할 때 나올 수 있는 구분 가능한 순열의 개수는? **
**(주인공이 되든 안되든 게임 규칙안에서 나올 수 있는 모든 경우의 수)**
(예를 들면, 30까지 말하고 상대방이 31을 말하게 하는게 이 게임의 묘미지만,
자신이 30, 31을 외치며 당당하게 주인공이 되는 경우 까지 포함)
갑자기 순열이라니? 이해가 되도록
아래 그림 1.을 보도록 하자.
그림 1. 2명 베스킨라빈스 게임의 순열 중 하나
(이 순열에서는 0번(빨강)이 주인공)
0번 사람이 부른 숫자를 빨간색, 1번 사람이 부른 숫자를 파란색으로 칠해보자.
이제 각 색깔을 0과 1에 대응시키면 하나의 순열 혹은 2진법 숫자가 나오게 된다.
`
*그러면 이 문제는 다음과 동치라고 할 수 있다. *
2명 베스킨 게임에서 나올 수 있는 구분 가능한 2진수의 개수를 구하여라
먼저, 해당 순열의 개수를 함수로 표현해보자.
참여자 수 = 2, 연속해서 말할 수 있는 최대 숫자 개수 = 3 일 때,
말해야 할 숫자의 개수가 x일 때, 순열의 개수를 f(x) 라고 하면
우리가 구해야 할 것은 f(31)이다.
여기서 0으로 끝나는 순열의 개수를 f0, 1로 끝나는 순열의 개수를 f1이라고 한다면
[수식 1] f = f0 + f1
이제 f(30)과 f(31)의 관계를 알아보도록 하자
0으로 끝나는 f0(30)의 순열들의 집합은
다음과 같이 3가지 경우로 나눌 수 있다.
1으로 끝나는 f1(30)의 순열들의 집합도
다음과 같이 3가지 경우로 나눌 수 있다.
Case 01 : (28번까지 어떻게 흘러왔는지에 상관없이 ) 29번은 1으로, 30번은 0으로 끝나는 경우
Case 02 : (27번까지 어떻게 흘러왔는지에 상관없이 ) 28번은 1으로, 29, 30번은 0으로 끝나는 경우
Case 03 : (26번까지 어떻게 흘러왔는지에 상관없이 ) 27번은 1으로, 28, 29, 30번은 0으로 끝나는 경우
Case 11 : (28번까지 어떻게 흘러왔는지에 상관없이 ) 29번은 0으로, 30번은 1으로 끝나는 경우
Case 12 : (27번까지 어떻게 흘러왔는지에 상관없이 ) 28번은 0으로, 29, 30번은 1으로 끝나는 경우
Case 13 : (26번까지 어떻게 흘러왔는지에 상관없이 ) 27번은 0으로, 28, 29, 30번은 1으로 끝나는 경우
Case 01. 순열의 개수 = f01
Case 02. 순열의 개수 = f02
Case 03. 순열의 개수 = f03
Case 11. 순열의 개수 = f11
Case 12. 순열의 개수 = f12
Case 13. 순열의 개수 = f13
이라고 하면
** [수식 2]** f0 = f01 + f02 + f03
[수식 3] f1 = f11 + f12 + f13
수식 1 ~ 수식 3을 종합하면
[수식 4] f = f01 + f02 + f03 + f11 + f12 + f13
수식 4를 통해
f(30) = f01(30) + f02(30) + f03(30) + f11(30) + f12(30) + f13(30)
위와 같이 f(30)을 표현 할 수 있다.
f(31)의 순열들의 집합도 f(30)를 기준으로 생각해보자
30에서
Case 01로 끝나는 경우 → 31에 0 또는 1 모두 올 수 있다 → 2 * f01(30)
Case 02로 끝나는 경우 → 31에 0 또는 1 모두 올 수 있다 → 2 * f02(30)
Case 03로 끝나는 경우 → 31에 오로지 1만 올 수 있다 → 1 * f03(30)
Case 11로 끝나는 경우 → 31에 0 또는 1 모두 올 수 있다 → 2 * f11(30)
Case 12로 끝나는 경우 → 31에 0 또는 1 모두 올 수 있다 → 2 * f12(30)
Case 13로 끝나는 경우 → 31에 오로지 0만 올 수 있다 → 1 * f13(30)
즉 f(31)은 이렇게 6개 경우의 합(덧셈법칙)으로 표현 가능하다!
f(31) = 2 f01(30) + 2 f02(30) + f03(30) + 2 f11(30) + 2 f12(30) + f13(30)
↓
f(31) = 2 (f01(30) + f02(30) + f03(30) + f11(30) + f12(30) + f13(30))
- (f03(30) + f13(30))
↓
수식 4를 적용하면 f(31) = 2f(30) - (f03(30) + f13(30))
다음으로 f03(30) + f13(30) 에 대해서 생각해보자
f03(30) = f1(27) * 1
f13(30) = f0(27) * 1
이라는 것을 알 수 있다.
What?
27까지만 보자. 어떤 생각이 드는가?
Case 03 : 27에서 1이고(f1(27)) 뒤에는 0 세 개로 고정되어 있으니 * 1
Case 13 : 27에서 0이고(f0(27)) 뒤에는 1 세 개로 고정되어 있으니 * 1
정리하면
f03(30) + f13(30) = f1(27) + f0(27) = f(27)
결과적으로
[수식 5] f(31) = 2f(30) - f(27)
수식 5를 일반화하면
*[수식 6] f(n+1) = 2f(n) – f(n-3) *
(단, n > 3)
이 점화식을 이용하여 f(31)을 구해볼까요?
f(1) = 2^1 = 2
f(2) = 2^2 = 4
f(3) = 2^3 = 8
f(4) = 6*2 + 2 = 14
까지 구하고 점화식에 대입
.
.
f(31) = 197,900,192
(엑셀로 계산했지만, 선형점화식 해법으로 일반항도 구하였다.
일반항을 구하는 방법에 대해서는 따로 글을 작성하도록 하겠다)
즉, 2명이 베스킨게임을 할 때
나올 수 있는 모든 경우의 수는
1억 9790만 192 가지!
물론!
이기려고 하는 게임이므로저 모든 경우의 수에서
아주 일부의 루트?만 타면서 게임이 끝나게 될 뿐이죠
수식 6을 더 일반화 해볼까요?
우선 위에서 사용한 f는 참여자 2명, 최대 수 3개 일 때,
아이스크림 개수 n에 대한 Single Variable Function인데
이를 Multi Variables Function으로 표현해보자
아이스크림 개수 N, 참여자 M, 최대 수 L
해당 게임의 경우의 수 P(N, M, L)
[수식 7]
P(N+1, M, L) = 2*P(N, M, L) – P(N-L, M, L)
(이 식이 유효하게 성립하는 N, M, L의 대소관계에 대해서 생각해보자)
그런데, 이게 과연 제대로 된 일반화라고 할 수 있을까? 생각해봅시다~
일반화하는 중에
P(N+1, M, L) = M*P(N, M, L) – (M-1)*P(N-L, M, L)
으로 잘못 생각할 수도 있다.
왜 수식 7에 M이 아니라 2가 들어갔을까?
이는 우리가 단체로 베스킨게임을 할 때 마구잡이로 하는 게 아니라, 정해진 순서
(시계 방향, 혹은 반-시계 방향, 아니면 말 그대로 정해진 순서)에 따라 진행하기 때문이다.
다음 글은 [조합론] 베스킨라빈스 게임의 수학(2. 전략)입니다.
거창하게 전략이라고 썼지만 거창하지는 않습니다.
이미 작성된 글들도 있는 것 같지만 MY STYLE로 작성해보겠습니다.