필승 전략 게임 - 돌 줍기 게임에서 반드시 이기는 방법

1. 돌 줍기 게임

 

1) A부터 시작하여, A와 B가 번갈아가며 쌓여 있는 돌 무더기에서 돌을 1개 이상 집어온다.

 

2) 자기 차례가 되어 돌을 집어 올때는, 반드시 상대방이 조금 전에 집어간 돌의 개수의 2배 이하로 집어와야 한다.

 

예를 들어, A가 2개를 집고 차례를 넘겼다면, B는 1개~4개까지 범위에서 돌을 집어와야한다.

 

이제 B가 3개를 집고 넘겨준다면, A는 다시 1개~6개 범위에서 마음대로 돌을 집어갈 수 있다.

 

3) 마지막 돌을 집어간 사람이 게임에서 승리한다.

 

4) 맨 처음 시작하는 사람이 돌을 다 집어갈 수는 없다

 

 

2. 반드시 이길 수는 없나?

 

A,B가 최선의 전략으로 게임할때, 누가 이기는지 예측할 수 있을까?

 

1) 돌멩이가 1개 있을때, 게임 자체가 성립하지 않는다. 맨 처음 시작하는 사람이 1개만 집어도 다 집어가니까

 

2) 2개인 경우, 무조건 B가 이기는건 자명하다. 

 

3) 3개인 경우, 무조건 B가 이길 수 있다.

 

4) 4개인 경우, A가 처음에 1개를 집으면 B는 2개까지 집을 수 있으므로, A가 이길 수 있다.

 

5) 5개인 경우, A가 2개 이상 집으면 바로 패배한다. 그래서 1개만 집어야하는데,

 

그러면 4개가 되어 B가 첫턴으로 시작하는거나 마찬가지라서 4)에 의해 B가 이긴다.

 

6) 6개인 경우 A가 맨 처음 2개 이상 집으면 바로 패배하므로, A는 1개만 집어야한다.

 

그러면 5개가 남고, B가 처음 시작하는 상황이다. 따라서 5)에 의해 A가 게임에서 이길 수 있다.

 

7) 7개인 경우, A가 1개를 집으면 6개가 남고 B가 처음 시작하는 상황과 마찬가지니 6)에 의해 B가 이긴다.

 

A가 3개를 집으면 바로 패배한다. 그래서 A는 2개를 집어야한다. 

 

그러면 5개가 남았고 B는 최대 4개까지만 집을 수 있다. 이는 5)와 같은 상황으로 A가 게임을 이길 수 있다.

 

8) 8개인 경우, A는 3개 이상을 집으면 바로 패배한다. 그래서 1개나 2개를 집어야하는데,

 

1개를 집으면 7개가 남고 B가 게임을 시작한다. 7)에 의해 최선의 전략으로 게임하면 B가 게임을 이길 수 있다.

 

2개를 집으면 6개가 남고 B가 게임을 시작한다. 6)에 의해 최선의 전략으로 게임하면 B가 게임을 이길 수 있다.

 

-----------------------------------------------------------------------------------------------------------------------------

 

처음에 돌멩이 개수가 2,3,5,8개이면 최선의 전략으로 플레이할 때 B가 게임을 이길 수 있다.

 

조금 더 생각해보면 마치 피보나치 수열을 이루는 것 같다.

 

13개에서도 B가 게임을 이길 수 있다는 것을 생각할 수 있는데 생각해볼까?

 

A가 5개 이상을 집으면 바로 게임에서 패배한다.

 

A는 1~4개까지 집을 수 있는데, 

 

A가 4개를 집으면 9개가 남은 상황에서 B가 게임을 시작한다. 이 경우 1개를 집으면 8개를 남기고 A가 시작하는 상황이 된다.

 

8)에 의해 B가 게임을 이길 수 있다.

 

A가 3개를 집으면 10개가 남은 상황에서 B가 게임을 시작한다. 

 

B가 3개를 집으면 7개가 남아서 7)에 의해 B가 질 수 있다.

 

그런데 B가 2개를 집으면 8개가 남는데, 8)에 의해 B가 이길 수 있게 된다.

 

이번엔 A가 2개를 집으면 11개가 남은 상황에서 B가 게임을 시작한다.

 

역시 B가 3개를 집어서 8개를 남기고 A한테 넘기면, 8)에 의해 B가 이기게 된다.

 

A가 1개를 집으면 12개가 남고 B가 시작하게 된다.

 

그러면 B는 1개,2개를 집을 수 있는데 B가 1개를 집는다면? 11개가 남고 A가 시작

 

A가 1개 집고 넘기면 10개가 남아서 B가 2개를 집으면 8개 남기고 A한테 넘기니 8)에 의해 B가 이긴다.

 

A가 2개 집고 넘기면 9개가 남아서 B가 1개를 집으면 8개 남기고 A한테 넘기니 8)에 의해 B가 이긴다.

 

따라서 13개더라도 B가 최선으로 게임한다면 반드시 이길 수 있다.

 

 

3. Fibonacci Nim

 

2,3,5,8,13,...개에서 B가 최선으로 게임한다면 반드시 이길 수 있다는 것을 증명할 수 있다.

 

이 수열이 피보나치 수열 형태라서 Fibonacci Nim이라는 이름이 붙었고 

 

The Fibonacci Quarterly 1963년 12월 호에 이 게임의 필승전략이 증명되었다

 

 

 

대충 논문이 저렇게 생김.. 읽어봐야하나?? 간단해보이긴 한디 뭔가 가독성이 떨어져서 읽기 싫게 생겼는데

 

대충 훑어보면 님 게임 필승 전략의 증명이랑 비슷함

 

지금 상황이 "safe"일때, "unsafe"인 상태로 상대에게 넘겨줄 수 있고... 이런 느낌으로?

 

https://terms.naver.com/entry.naver?docId=3574974&cid=58944&categoryId=58970 

돌 줍기 게임 필승 전략

 

조금 더 쉽게 설명해준 이 글에서 필승전략을 요약하면

 

1) N이 피보나치 수이면 B가 반드시 게임을 이길 수 있다.

 

2) N이 피보나치 수가 아니라면, N에 대한 제켄도르프 분해에서 나타나는 가장 작은 피보나치 수를 Z(N)이라고 할때,

 

Z(N)개의 돌을 처음에 집는다면 A가 게임에서 반드시 이길 수 있다.

 

 

4. 간단 증명

 

돌멩이 수가 N개이면 집을 수 있는 돌의 개수가 M개 이하일때, 현재 게임의 상태를 (N,M)으로 나타내자.

 

예를 들어 돌 12개로 게임을 시작한다면 (12,11)로 나타나고 A가 2개를 집는다면 다음 상태는 (10,4)이다.

 

그리고 B가 3개를 집으면 A는 (7,6)을 건네받는다.

 

그러면 어떤 순서쌍을 넘겨줘야 최선을 다할 경우 항상 이길 수 있을까?

 

"safe"를 반드시 이길 수 있는 상태, "unsafe"를 절대로 이길 수 없는 상태라고 하자.

 

여기서 "safe"인 상태는 $M \geq Z(N)$이고 "unsafe"는 $M < Z(N)$이다.

 

1) (N,M)이 "safe"일때, Z(N)개의 돌을 집는다면 (N-Z(N), 2Z(N))은 반드시 "unsafe"이다.

 

2) (N,M)이 "unsafe"일때, 1이상 M이하의 자연수 K에 대하여 K개의 돌을 집는다면 (N-K,2K)는 반드시 "safe"이다.

 

예를 들어보자.

 

N = 30일때, 제켄도르프 분해에 의해 30 = 21 + 8 + 1이다. 그래서 Z(30) = 1이다.

 

여기서 M = 29인데, $M \geq Z(30)$이므로, (30,29)는 "safe"이다. 

 

그러니까 최선으로 잘 하면 게임에서 반드시 이길 수 있는 상태이다.

 

이때, Z(30) = 1개를 집으면 (29,2)를 상대방에게 넘기는데 이는 "unsafe"이다.

 

실제로 29 = 21 + 8이며, Z(29) = 8로 2보다 크니 "unsafe"이고,

 

(29,2)를 넘겨받은 사람은 어떻게 하더라도 상대방에게 "safe"인 상태를 넘겨준다.

 

1개를 집으면 (28,2)이고, 28 = 21+5+2로 $Z(28) = 2 \geq 2$이다.

 

2개를 집으면 (27,4)이고, 27 = 21 + 5 + 1로 $Z(27) = 1 \geq 4$이다.

 

 

----------------------------------------------------------------------------------------------------------------------------------

 

1)에 대한 증명

 

보조정리: 모든 자연수 n에 대하여 $2F_{n} <= F_{n+2}$임을 보이면 충분하다.

 

$F_{1} = 1, F_{3} = 2$이므로 부등식이 참이다.

 

자연수 n에 대해 부등식이 성립한다고 가정하면, 양변에 $F_{n+1}$을 더하자.

 

$2F_{n} + F_{n+1} <= F_{n+3}$인데, 여기서 $2F_{n+1} < 2F_{n} + F_{n+1}$이다.

 

왜냐하면, $F_{n-1} < F_{n}$에서, $F_{n}$을 더하면, $F_{n+1} < 2F_{n}$이다. 

 

여기에 $F_{n+1}$을 더하면, $2F_{n+1} < 2F_{n} + F_{n+1}$이다.

 

따라서 모든 피보나치 수의 항은 그 2번째 이후 항이 원래 수의 2배보다 크다. 

 

N에 대한 제켄도르프 분해의 가장 작은 값 Z(N)은 피보나치 수이며, 이것이 $F_{k}$를 만족한다고 하자.

 

즉, $F_{k} = Z(N)$인 어떤 자연수 k가 존재한다.

 

그러면 N의 제켄도르프 분해는..

 

$$N = F_{k} + F_{k+i_{1}} + F_{k+i_{2}} + ... + F_{k + i_{n}}$$이다.

 

여기서 $F_{k} \leq F_{k+i_{1}} \leq F_{k+i_{2}} ... $라고 가정하자.

 

제켄도르프 분해는 항상 존재하며, $F_{k}$와 $F_{k+i_{1}}$은 인접한 피보나치 수가 아니다.

 

그러니까 $i_{1}$은 최소 2이상이다.

 

그러므로, 보조정리로부터 $F_{k+i_{1}} > 2F_{k}$이다.

 

따라서, N - Z(N)의 제켄도르프 분해는...

 

$$N = F_{k} + F_{k+i_{1}} + F_{k+i_{2}} + ... + F_{k + i_{n}} = Z(N) + F_{k+i_{1}} + ... + F_{k+i_{n}}$$이므로,

 

$$N - Z(N) = F_{k + i_{1}} + ... + F_{k+i_{n}} = Z(N-Z(N)) + ... + F_{k+i_{n}}$$

 

그리고, $Z(N-Z(N)) = F_{k+i_{1}} > 2Z(N) = 2F_{k}$이다.

 

따라서, (N-Z(N), 2Z(N))은 반드시 "unsafe"이다.

 

-----------------------------------------------------------------------------------------------------------------------------

 

2)에 대한 증명

 

비슷한 방식으로 전개해보면 N이 "unsafe"이므로, $Z(N) > M$이고, 

 

가정으로부터 $K \leq M$이다. 따라서, $K \leq M < Z(N)$이라서, $K < Z(N)$

 

N에 대한 제켄도르프 분해는...

 

$N = Z(N) + F_{i_{1}} + F_{i_{2}} + ... + F_{i_{n}}$

 

Z(N)은 제켄도르프 분해에서 나타나는 모든 피보나치 수에서 가장 작은 수이므로, 그것보다 작은 K는,

 

제켄도르프 분해에서 나타나는 모든 피보나치 수보다도 더 작다. 

 

이제 양변에 K를 빼주면..

 

$N - K = Z(N) - K + F_{i_{1}} + F_{i_{2}} + ... + F_{i_{n}}$

 

결국에 우변을 피보나치 수의 합으로 나타내기 위해서는,

 

$min(F_{i_{k}}) - K$를 제켄도르프 분해하면 된다. (k = 0,1,2,...,n이고 $F_{i_{0}} = Z(N)$)

 

--------------------------------------------------------------------------------------------------------------------------------------------------------

 

"보조정리: 피보나치 수 F와 그보다 작은 K에 대하여, Z(F-K)는 항상 2K보다 작거나 같다."

 

따라서 보조정리가 참임을 보이면 2)를 증명한 것이나 마찬가지다.

 

n = 1,2는 의미없으므로, (1이상의 K가 존재하지 않는다)

 

3이상의 자연수 n에 대하여 $F_{n} > K$일때, $Z(F_{n} - K) \leq 2K$임을 보인다.

 

n = 3이면 $F_{3} = 2$이고 K = 1밖에 없다.

 

Z(2-1) = Z(1) = 1이고, 이는 2K = 2이하이다. 따라서 부등식이 성립한다.

 

n = 4이면 $F_{4} = 3$이고 K = 1,2가 가능하다.

 

Z(2) = 2이고 Z(1) = 1이므로, 모두 2K보다 작거나 같다. 따라서 부등식이 성립한다.

 

이제 4이상의 자연수 n에 대해 부등식이 성립한다고 가정한다.

 

$Z(F_{n} - K) \leq 2K$가 성립하고, $Z_{F_{n-1} - K) \leq 2K$가 성립한다.

 

그럴때, n+1에서 성립함을 보이고자 한다.

 

$F_{n-1} - K$의 제켄도르프 분해는...

 

$$F_{n-1} - K = Z(F_{n-1} - K) + F_{i_{1}} + F_{i_{2}} + ... + F_{i_{n}} \leq 2K + F_{i_{1}} + ... + F_{i_{n}}$$

 

여기서 $F_{i_{n}} < F_{n-1}$이다.

 

왜냐하면, $F_{n-1}$보다 작은 수에서 제켄도르프 분해를 했기 때문이다.

 

즉, $F_{i_{n}}$은 $F_{n}$과 인접하지 않은 피보나치 수이다.

 

양변에 $F_{n}$을 더하면,

 

$$F_{n-1} + F_{n} - K = F_{n+1}-K \leq 2K + F_{i_{1}} + F_{i_{2}} + ... + F_{i_{n}} + F_{n}$$

 

결과적으로, $F_{n+1}-K \leq 2K + F_{i_{1}} + F_{i_{2}} + ... + F_{i_{n}} + F_{n}$이다.

 

이제 $F_{n+1}-K$의 제켄도르프 분해를 수행한다.

 

제켄도르프 분해는, $F_{n+1} - K$보다 작거나 같은 가장 큰 피보나치 수를 빼나가는 것인데,

 

$F_{n} \leq F_{n+1} - K$이므로, 우변의 $F_{n}$을 빼면.. $X = F_{n+1} - K$라 하고...

 

$$X - F_{n} \leq 2K + F_{i_{1}} + F_{i_{2}} + ... + F_{i_{n}}$$

 

그 다음 제켄도르프 분해의 구성요소는 $F_{i_{n}}$이다.

 

왜냐하면, $F_{i_{1}}, F_{i_{2}}, ... F_{i_{n}}$들은 $F_{n-1} - K$의 제켄도르프 분해의 구성요소인데,

 

이들은 피보나치 수이며 인접하지 않은 수이고, $F_{n-1} - K < F_{n}$이기 때문에...

 

$$X - F{n} - F_{i_{n}} - F_{i_{n-1}} ... - F_{i_{1}} \leq 2K$$

 

좌변의 $X - F_{n} - F_{i_{n}} - F_{i_{n-1}} - ... - F_{i_{1}}$에 대해 생각해보면...

 

X에 대한 제켄도르프 분해의 구성요소들을 뺀 값인데.. 이 값의 최소는 무엇일까?

 

$Z(X) = Z(F_{n+1} - K)$가 된다.

 

그러니까 X의 제켄도르프 분해 요소가 더 있을 수도 있는데, 더 없다면 당연히 $$Z(F_{n+1} - K) \leq 2K$$지만,

 

더 있다고 치더라도,

 

$$Z(F_{n+1} - K) \leq 2K - (F_{n+1} - K 제켄도르프 분해의 나머지) \leq 2K$$이므로,

 

반드시, $Z(F_{n+1} - K) \leq 2K$를 얻는다.

 

그러므로, 3이상의 모든 자연수 n에 대하여 $Z(F_{n} - K) \leq 2K$이다.

 

----------------------------------------------------------------------------------------------------------------------------------------------------

 

이제 이어서,

 

N-K의 제켄도르프 분해는.. $N-K = Z(min(F_{i_{k}})-K) + F_{i_{1}} + F_{i_{2}} + ... + F_{i_{n}}$인데,

 

보조정리로부터 $Z(N-K) = Z(min(F_{i_{k}) - K) \leq 2K$이다.

 

따라서, (N,M)이 "unsafe"일때, M이하의 어떠한 K개를 집더라도, 상대에게 반드시 "safe"인 상태를 넘겨준다.

 

증명의 논리가 조금 찝찝한데

 

아무리 생각해도 여기까지다...

 

---------------------------------------------------------------------------------------------------------------------

 

아무튼 핵심은 님게임이랑 비슷하게, 

 

1) 이길 수 있는 상태에서, 특정한 개수를 집으면 반드시 상대에게 패배할 수 밖에 없는 상태를 넘겨줄 수 있다

 

2) 패배할 수 밖에 없는 상태에선, 어떻게 하더라도 상대에게 이길 수 있는 상태를 넘겨준다

 

그리고 그 특정한 개수가, 자연수 N을 제켄도르프 분해할때, 나타나는 가장 작은 피보나치 수

 

그리고 이길 수 있는 상태일려면, 피보나치 수가 아니어야한다.

 

----------------------------------------------------------------------------------------------------------------------

 

5. 연습문제

 

2373번: Fibonacci Game (acmicpc.net) 

2373번: Fibonacci Game

 

6. 풀이

 

위에서 제시한 피보나치 게임의 필승전략을 그대로 구현하면 된다..

 

1) 완전제곱수인지 판단하는 함수

 

2) 피보나치 수인지 판단하는 함수

 

3) 제켄도르프 분해해서 가장 작은 피보나치 수를 구하는 함수

 

4) 피보나치 수이면 게임을 이길 수 없고

 

5) 피보나치 수가 아니라면, 제켄도르프 분해해서 가장 작은 피보나치 수만큼 처음에 집는다.

 

from sys import stdin

#완전제곱수인지 판단
def is_perfect(n):
    
    if int((n**(1/2)))**2 == n:
        
        return True
    
    return False

#피보나치 수인지 판단
def is_fib(n):
    
    x = 5*n*n+4
    y = 5*n*n-4

    if is_perfect(x) or is_perfect(y):
        
        return True
    
    return False

#제켄도르프 분해해서 가장 작은 피보나치 수를 구함
def z(n):
    
    fib = [1,1]

    i = 2

    while 1:
        
        x = fib[i-1] + fib[i-2]

        if x <= n:

            fib.append(x)
            i += 1
        
        else:
            
            break
    
    len_f = len(fib)

    while n > 0:
        
        for i in range(len_f-1,-1,-1):
            
            if n >= fib[i]:
                
                n -= fib[i]
                break
    
    return fib[i]


n = int(stdin.readline())

#피보나치 수이면, 이길 수 없고
if is_fib(n):
    
    print(-1)

#피보나치 수가 아니라면, 제켄도르프 분해해서 나타나는 가장 작은 피보나치 수를 집는다
else:

    print(z(n))