배스킨라빈스(게임)
1. 게임 규칙
게임의 참여자들은 차례를 정해 1부터 31까지의 수를 순차적으로 부른다. 한번에 1~3개까지 수를 연달아 부를 수 있으며, 마지막 31을 부른 사람이 진다. 님(nim)게임의 파생 게임 중 가장 유명한 게임이라 볼 수 있겠다.
1.1. 승리 전략
이 게임엔 다음을 만족하는 상황에 한해 반드시 이겨낼 수 있는 승리 전략이 있다. 체르멜로 정리 참고..
1.게임 참여자가 2명이다.
2.상대방은 이 승리전략을 모른다. 만약, 상대방이 승리전략을 알 경우 내 차례에 반드시 2를 불러야한다.
승리전략은 다음과 같다.
무조건 이길 수 있는 방법이고 이렇게 필승법이 존재하는 게임은 게임으로서의 수명이 끝났다고 봐도 무방하다. 왜냐하면 이 승리전략을 아는 두 명이 게임을 하면 게임 고유의 재미는 묵살되고 그저 "2 먼저 부르기 게임" 혹은 "선공 잡기 게임"으로 전락하기 때문.상대방이 3개를 부르면 나는 1개를 부르고, 상대가 2개만 부르면 역으로 하나 늘려서 나는 2개, 상대가 1개만 말하면 나는 3개를 부른다. 이런 식으로 둘이 부르는 갯수가 4개가 되도록 항상 일정하게 맞춘다.
이 점을 이용하여 맨 처음에 2를 부를 수만 있다면, 6, 10, 14, 18, 22, 26, 30도 반드시 부를 수 있게 되고 내가 30을 불렀으니 상대방이 31을 부르고 패배한다.
혹시라도 이 승리 전략을 모르는 상대에게 계속 우려먹고 싶다면, 공식쓰는 것을 들키지 않아야하므로 변칙적으로 필승 숫자들을 불러나가는 등 약간의 심리전을 가미하는 것이 좋다.
1.2. 승리 전략의 수학적 심화
조금만 더 생각해보면 좀 더 다양한 조건에도 통할 수 있는 범용 승리전략을 구할 수 있다.
문제부터 다시 적어보자.
$$S$$명의 플레이어들은 $$j$$부터 $$k$$까지의 자연수를 번갈아가며 한 턴에 $$l$$~$$m$$개씩 연달아 부른다. $$k$$를 부르면 진다.
설명하기에 앞서 한 라운드에서 $$x$$명의 플래이어가 부르는 숫자의 개수를 $$C(x)$$라고 하자. 라운드란 모든 참가자의 차례가 한번씩 돌아간 것을 말한다.
만약 $$S>2$$라면, $$C(1)<C(S-1)$$이므로 $$C(1)$$이 모든 $$C(S-1)$$에 대하여 $$C(S)$$의 값을 임의로 조정할 수 없지만,승리전략의 핵심은 $$C(S)$$를 제어하는 것
만약 $$S=2$$라면, $$C(1)=C(S-1)$$이므로 $$C(1)$$이 모든 $$C(S-1)$$에 대하여 $$C(S)$$의 값을 둘의 평균으로 맞출 수 있고 이 때의 값은 $$l+m$$이다.
즉,$$S=2$$인 상황에선 특정 플레이어가 한 라운드에서 불러지는 숫자의 갯수를 항상 일정하게 맞출 수 있기 때문에 이를 활용하여 최종적으로 마지막 수를 부르지 않게 하는 승리전략이 존재하게 되는 것이다. 허나 $$S>2$$의 경우엔 $$C(1)<C(S-1)$$이라 다수의 횡포(?)를 막아낼 도리가 없기에 어찌보면 승리전략은 존재하지 않는다고 봐야할지도 모른다. 추측컨대 이 경우 완벽한 승리전략은 존재하지 않지만 다만, 확률적으로 k를 부르지 않게 할 수 있는 것은 가능할 것이다.(단, $$C(S)<k$$)
[image]
3명이서 게임을 진행했을 때, 마지막 부른 숫자가 유리한 정도를 100만여 번의 컴퓨터 시뮬레이션을 통해 정리한 것이다. (단, 모든 참여자는 자신에게 가장 유리한 수를 선택한다.) 유리한 숫자는 29를 기준으로, 불리한 숫자는 26[1]을 기준으로 6의 주기로 반복되는 것을 확인할 수 있다.
비록 적용할 수 있는 상황이 제한적이긴 하지만 어쨌든 승리전략을 파악하였다. 이제 남은 건 단순한 산수작업뿐.
먼저, 전체의 갯수에서 $$l$$을 뺀 값에다 $$l+m$$으로 나눈 나머지 $$r$$을 구한다.
이 식에서 전체의 숫자 중 $$r$$번째의 숫자가 필승수열의 초항이고, 그 초항 자신과 그로부터 $$l+m$$개씩 더해나간 $$q$$개의 숫자들까지 총 $$q+1$$개의 필승숫자들이 존재함을 알 수 있다.$$((k-j+1-l) / (l+m)=q...r $$
그런데 이 때 $$2 \leq l$$일 경우 $$0<C(1)< l$$일 때에도 필승숫자가 존재할 수 있다. 맨마지막에 최소로 불러야하는 $$l$$개도 다 채워부르지 못하면서 k를 말해야하는 경우다.
이를 고려하여 필승수열의 일반항을 구해보면 다음과 같다.
가령, 2~31까지의 수를 한턴에 2~3개말하는 게임을 두 명이서 하는 상황에서의 필승수열은 다음과 같다.$$a_n=j+r-1-o+(l+m)n$$이다.(단, $$n=0,1,2..., 0 \leq o < l$$ )
$$o=0, a_n=5n+5$$
$$o=1, a_n=5n+4$$
[1] '''3명이 할 때의 한정.''' 2명이 게임을 할 때 필승 숫자이다.