편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
34번째 줄: | 34번째 줄: | ||
{{숨기기|풀이|똑같은 방법으로, 두 줄의 돌의 개수를 같게 맞춰주면 됩니다. 2, 2가 아닌 1, 1을 만드는 것을 목표로 하면 됩니다. 상대방이 한 줄 전체를 비우면 비웃어 주세요.}} | {{숨기기|풀이|똑같은 방법으로, 두 줄의 돌의 개수를 같게 맞춰주면 됩니다. 2, 2가 아닌 1, 1을 만드는 것을 목표로 하면 됩니다. 상대방이 한 줄 전체를 비우면 비웃어 주세요.}} | ||
똑같은 방법으로 일반화 된 전략을 세울 수 있으니 일반적인 경우의 해결법은 생략한다. 하지만 중요한 것은, 어째서 위 전략이 '''항상''' 성립하는지 모른다는 것이다. 문제의 답을 알지만 풀이는 모르는 그런 경우. 이 필승 전략에 대한 증명은 아랫 문단을 참조하자. | 똑같은 방법으로 일반화 된 전략을 세울 수 있으니 일반적인 경우의 해결법은 생략한다. 하지만 중요한 것은, 어째서 위 전략이 '''항상''' 성립하는지 모른다는 것이다. 문제의 답을 알지만 풀이는 모르는 그런 경우. 이 필승 전략에 대한 증명은 아랫 문단을 참조하자. | ||
==== 수학적 이론 ==== | ==== 수학적 이론 ==== | ||
91번째 줄: | 85번째 줄: | ||
#이제 <math>s\neq0</math>이라 가정하자. <math>s</math>를 2진법으로 나타내었을 때, 제일 왼쪽에 존재하는 1의 자리를 <math>d</math>라 하자.<ref>만약 <math>s</math>가 00101101이면, <math>d=6</math>이다.</ref> 또한, <math>s\neq0</math>이기 때문에 <math>d</math>의 존재가 보장된다. 이제 2진법으로 나타냈을 때, <math>d</math>번째 자리의 수가 0이 아닌 <math>x_k</math>를 고른다. 만약 이런 <math>x_k</math>가 존재하지 않는다면, 모든 <math>x_i</math>의 <math>d</math>번째 자리는 0이고, 님 합을 구하면 <math>s</math>의 <math>d</math>번째 자리는 0이 되어 모순이다. 이제 <math>y_k=s\oplus x_k</math>라 하자. <math>x_k> y_k</math>임을 보일 것이다. <math>x_k</math>와 <math>y_k</math>의 <math>d</math>자리 왼쪽은 전부 똑같고,<ref><math>s</math>의 <math>d</math>자리 왼쪽은 전부 0이므로</ref> <math>d</math>자리의 수는 1에서 0으로 줄어든다. 이 차이는 10진법으로 <math>2^d</math>이고, <math>d</math>자리 오른쪽의 수는 아무리 차이나 봤자 <math>2^d-1</math>이다. 따라서 <math>x_k</math>는 <math>y_k</math>보다 적어도 1 크다. 이는 곧 <math>x_k-y_k</math>개의 돌을 <math>k</math>번째 더미에서 가져갈 수 있음을 보장한다. 또한, (*)에서, <math>t=s\oplus x_k\oplus y_k=s\oplus x_k\oplus\left(s\oplus x_k\right)=0</math>이다. | #이제 <math>s\neq0</math>이라 가정하자. <math>s</math>를 2진법으로 나타내었을 때, 제일 왼쪽에 존재하는 1의 자리를 <math>d</math>라 하자.<ref>만약 <math>s</math>가 00101101이면, <math>d=6</math>이다.</ref> 또한, <math>s\neq0</math>이기 때문에 <math>d</math>의 존재가 보장된다. 이제 2진법으로 나타냈을 때, <math>d</math>번째 자리의 수가 0이 아닌 <math>x_k</math>를 고른다. 만약 이런 <math>x_k</math>가 존재하지 않는다면, 모든 <math>x_i</math>의 <math>d</math>번째 자리는 0이고, 님 합을 구하면 <math>s</math>의 <math>d</math>번째 자리는 0이 되어 모순이다. 이제 <math>y_k=s\oplus x_k</math>라 하자. <math>x_k> y_k</math>임을 보일 것이다. <math>x_k</math>와 <math>y_k</math>의 <math>d</math>자리 왼쪽은 전부 똑같고,<ref><math>s</math>의 <math>d</math>자리 왼쪽은 전부 0이므로</ref> <math>d</math>자리의 수는 1에서 0으로 줄어든다. 이 차이는 10진법으로 <math>2^d</math>이고, <math>d</math>자리 오른쪽의 수는 아무리 차이나 봤자 <math>2^d-1</math>이다. 따라서 <math>x_k</math>는 <math>y_k</math>보다 적어도 1 크다. 이는 곧 <math>x_k-y_k</math>개의 돌을 <math>k</math>번째 더미에서 가져갈 수 있음을 보장한다. 또한, (*)에서, <math>t=s\oplus x_k\oplus y_k=s\oplus x_k\oplus\left(s\oplus x_k\right)=0</math>이다. | ||
돌 더미가 한 개인 경우의 님 게임과 비슷하지만, 돌들이 '''원형'''으로 놓여있는 경우. 한 번에 가져갈 수 있는 돌의 개수에 제한이 있는 것 까지는 같지만, 가져가는 돌들은 서로 '''인접'''해야 한다. 원조 님 게임과 비슷한 이론을 쓰긴 하지만 이 게임 만의 독특한 수학 이론이 많이 필요하다.<ref>[http://web.calstatela.edu/faculty/sheubac/presentations/SLOtalk.pdf 1], [http://arxiv.org/pdf/1211.0091.pdf 2] 참조</ref> | 돌 더미가 한 개인 경우의 님 게임과 비슷하지만, 돌들이 '''원형'''으로 놓여있는 경우. 한 번에 가져갈 수 있는 돌의 개수에 제한이 있는 것 까지는 같지만, 가져가는 돌들은 서로 '''인접'''해야 한다. 원조 님 게임과 비슷한 이론을 쓰긴 하지만 이 게임 만의 독특한 수학 이론이 많이 필요하다.<ref>[http://web.calstatela.edu/faculty/sheubac/presentations/SLOtalk.pdf 1], [http://arxiv.org/pdf/1211.0091.pdf 2] 참조</ref> | ||
*슈퍼 님 (Super Nim) | *슈퍼 님 (Super Nim) | ||
131번째 줄: | 123번째 줄: | ||
{{인용문2|칠판에 1부터 n까지의 자연수가 있다. 번갈아 가면서 두 수를 골라 지우고, 칠판에 두 수의 합, 또는 차를 새로 적는다. 최후에 남은 숫자가 짝수면 선공의 승리, 홀수면 후공의 승리일 때, 당신의 필승 전략은?}} | {{인용문2|칠판에 1부터 n까지의 자연수가 있다. 번갈아 가면서 두 수를 골라 지우고, 칠판에 두 수의 합, 또는 차를 새로 적는다. 최후에 남은 숫자가 짝수면 선공의 승리, 홀수면 후공의 승리일 때, 당신의 필승 전략은?}} | ||
{{숨기기|힌트|''' | {{숨기기|힌트|'''짠! 너무 쉬워서 힌트가 필요 없어요!''' <s>뭐 임마?</s>}} | ||
{{숨기기|풀이|끝까지 해보면 결국 칠판의 모든 수를 다 더한 것과 결과가 같습니다. 중간에 두 수의 차를 구해도, 결과의 기우성에는 변함이 없죠. n을 4로 나눴을 때 나머지가 1, 2면 최후에 홀수가 남기 때문에 후공을, n을 4로 나눴을 때 나머지가 0, 3이면 최후에 짝수가 남기 때문에 선공을 하면 됩니다. 전략은 필요 없고, 아무 생각없이 숫자를 지우기만 하면 됩니다.}} | {{숨기기|풀이|끝까지 해보면 결국 칠판의 모든 수를 다 더한 것과 결과가 같습니다. 중간에 두 수의 차를 구해도, 결과의 기우성에는 변함이 없죠. n을 4로 나눴을 때 나머지가 1, 2면 최후에 홀수가 남기 때문에 후공을, n을 4로 나눴을 때 나머지가 0, 3이면 최후에 짝수가 남기 때문에 선공을 하면 됩니다. 전략은 필요 없고, 아무 생각없이 숫자를 지우기만 하면 됩니다.}} | ||