3배 NIM 게임에 대하여

On 3 Times NIM Games

3배 NIM 게임은 동전 더미에서 두 참가자가 차례로 동전을 가져가서 마지막 동전을 가져가는 사람이 승자가 되는 NIM 게임의 변형으로 상대방이 가져가는 동전개수의 3배까지 동전을 가져갈 수 있다. 동전의 개수가 2개인 경우부터 76개인 경우까지 3배 NIM 게임을 실행하여 분석하고 승리전략을 탐구하였으며, 두 번째 참가자인 B 가 승리하게 되는 경우는 2, 3, 4, 6, 8, 11, 15, 21, 29, 40, 55, 76 등 12가지임을 확인하였다. 이 결과에서 B 가 승리하게 되는 경우의 동전 개수의 규칙을 찾았으며, 규칙을 이용하여 T1=2, T2=3, T3=4. T4=6. Tn+1=Tn+Tn-3(n≥4)으로 T 수 Tn을 정의하였다. 그리고 N0가 Tm<N0<Tm+1이면 N0=N+Tn1_Tn2+…+Tnr(단, N=0 또는 1, 3N<Tn1. nr=m, nj+1-nj≥4(j=1, …, r-1))로 나타낼 수 있음을 증명하였으며 N0의 T 표현이라 하였다. 동전의 개수가 T 수인 3배 NIM 게임에서는 두번째 참가자인 B 가 승리하고 동전의 개수가 T 수가 아닌 3배 NIM 게임에서는 첫 번째 참가자인 A 가 승리하게 됨을 증명하였다. 그리고 승자의 승리전략은 남아있는 동전의 개수를 T 표현으로 나타내고 T 표현에서 가장 작은 수만큼 동전을 가져가는 것임을 증명하였다.

3 times NIM game, a variation of the Fibonacci NIM game, is played as followings: There is one pile of coins with N0 coins, and there are two players A, B. The first player A must take at least one coin from the pile of coins, but may not take the entire pile. On subsequent turns, each player take at least one coin and at most 3 times(2 times in the case of Fibonacci NIM game) of the previous take. And the player who takes the last coin wins the game. We play the 3 times NIM games on the pile of N0 coins for N0=2,3,…,76 then we find that the second player B wins only for N0 = 2, 3, 4, 6, 8, 11, 15, 21, 29, 40, 55, 76 and the winning strategy for each case. From the 12 winning case of B, we find a relation between the number N0 of coins, and we define the T numbers : T1=2, T2=3, T3=4. T4=6. Tn+1=Tn+Tn-3(n≥4). We prove that if N0 is a T number, then the second player B wins the 3 times NIM game. If N0≥2 is not a T number, we prove that the first player A wins the 3 times NIM game. If N0 ≥ 2 is not a T number with Tm<N0<Tm+1 then we prove that N0 can be represented by a sum of T numbers and 1 or 0 as follows : N0=N+Tn1_Tn2+…+Tnr, where N=0 or 1, 3N<Tn1, nj=1-nj≥4, (1 ≤ j ≤ r-1), nr=m, this is called the T representation of N0. Using the T representation, we find the winning strategy for the winners as follows: represent the number of remaining coins as the T representation then take the coin as many as the smallest number in the T representation.