| [ QuizWit ] in KIDS 글 쓴 이(By): ilusion (luVthYsouL맧) 날 짜 (Date): 1997년10월31일(금) 22시02분20초 ROK 제 목(Title): 돌줍기 2디멘셔날 리커션이군요. A(m,n) 을 m 번째 턴에서 값이 n개의 돌멩이중에서 뽑아야 할 돌멩이의 갯수라고 하면 물론 에이는 자기가 생각하는 최고의 전략에 따라서. B(m,n) be the number of stones to be picked by the player B such that it might optimize his chance of wining. 그럼 처음에 에이가 A(1,n) 만큼 돌멩이를 뽑았을때 이번엔 비가 B(2, n - A(1,n)) 만큼 돌멩이를 뽑아야 하고 에이나 비나 똑같은 전략을 쓸거니까 만약 에이가 이길수 있는 전략이 어떠한 n 에 대해서 항상 존재한다면 이말은 n - A(1,n) 의 돌멩이를 가지고 처음시작하는걸로 생각해서 비가 반드시 진다는 소리. 자그렇다면 만약 에이가 반드시 이길수 있는 n 이 존재한다면 마찬가지로 n- A(1,n) 의 돌로는 에이가 반드시 지게 되어있으니까 문제 출제자가 낸 두개의 문제는 한개만 풀면 다른 나머지는 자동으로 풀린다는 소리군요. 낄낄... 위의 리커션을 한번만 더 이용하면 A 에 대한 리커션으로 나타낼수 있고 B 에 관련된 리커션이퀴션도 위에서 보여준거랑 비슷하게 나오니까. 풀리겠군요. 바운다리 콘디션들이 A(m,n) >= 1/2*B(m+1,n) >= 1/2*A(m+2,n) >=1 이니까 역시 에이에 대한 바운다리 컨디션만으로도 나타낼수 있고.. 결국 에이에 대한 일차 리커션 풀면 답이 나옵니다. 그리고 초기조건 A(1,n) 을 어떻게 결정하는가 하는거는 맨마지막에 에이가 뽑아야하니까 n = A(1,n) + B(2,n) + ... + B(k-1,n) + A(k,n) 에서 구해질껍니다. 뭐 대충 보였으니까 노가다는 다른분들이 하시겠지요. 히히... 2명이서 턴을 주고받거니 하는 일반적 게임에서 (님,체커) 등등에서 컴퓨터 프로그램짤레 에발류에이션 함수를 짜는 테크닉이기도 하고요. 위의 리커션 테크닉이 이문제에선 좀 복잡하게도 느껴질수 있는데 가장 일반화한 문제풀이 테크닉이니까. 근데 제 풀이방법보다 더 쉬운 방법도 생각해볼수는 있겠군. 낄낄..근데 n 이 얼마루 나옵니까? iLUSiON chung@math.mcgill.ca chung@math.toronto.edu |