경고 : 최신판이 아닙니다. 이 문서의 오래된 판을 편집하고 있습니다. 이것을 저장하면, 이 판 이후로 바뀐 모든 편집이 사라집니다. 로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!{{학술}} == 개요 == '''필승 전략 게임'''이란, 이름 그대로 어느 한 쪽이 반드시 이길 수 있는 전략을 가진 게임을 말한다. 중요한 것은, 운이나 실력이 아닌 철저한 '''수학적 계산'''만을 사용하여 이기는 게임만을 다룬다. 이 때문에 확률 놀음인 [[포커]]나 실력이 중요한 [[바둑]]은 이 범위에서 제외된다. 또한, 무수히 많은 [[경우의 수]]를 사용한 승리 전략이나 승패가 결졍되지 않는 게임 역시 제외된다. 전자의 예로는 [[오목]]이 있으며,<ref>아무런 규칙도 택하지 않을 경우, 먼저 두는 흑에게 필승 전략이 있기는 하지만 경우의 수가 너무 많다.</ref> 후자의 예는 [[틱택토]]가 있다.<ref>두 사람이 모두 전략적으로만 플레이하면 비기게 된다.</ref> 마지막으로, 여러명이 하는 게임이 아닌 일대일 대결 게임만을 다룬다. 어떤 게임의 필승 전략을 찾는 것은 소위 말하는 창의력 수학의 단골 소재. [[수학 경시대회]]에 나오는 경우도 간혹 있다. 대부분의 경우는 방법을 찾는 것만으로 끝나게 되지만, 게임에 따라서는 그 방법이 왜 필승 전략인지 [[증명]]을 해야하는 경우도 있다. 하지만 문제 유형이 거기서 거기라 몇 가지 유형을 풀어봤다면 "아, 이거는 이 방법이구나"하고 감이 온다. 가장 많이 알려진 필승 전략 게임은 "배스킨 라빈스 31"이라는 게임일 것이다. 31을 부르면 지는<ref>규칙에 따라서는 이기는</ref> 게임으로, 초등학교 수준의 필승 전략이 존재하지만 이 사실을 모르는 사람이 매우 많다. 그러나 필승 전략을 사용하여 상대방을 농락하는 짓은 착한 위키러라면 하지 말자. 더욱이 필승 전략 게임에 '''돈'''을 건다면... {{ㅊ|사기죄}} == 목록 == === NIM 게임 === 가장 대표적인 유형으로, 개요에서 예시로 들은 배스킨 라빈스 31도 님 게임의 일종이다. 이름의 NIM의 어원은 알려지지 않았으며, 훔치다라는 뜻의 영어 동사 nim에서 왔다는 설,<ref>nim은 현재는 사어(死語)다.</ref> 가지고 가다라는 뜻의 독일어 nimm에서 왔다는 설, NIM을 뒤집으면 WIN이기 때문에 NIM이라는 설 등이 있다. 이름 뿐만 아니라 게임 자체의 기원도 명확하지 않은데, 고대 중국의 돌 줍기 게임에서 왔다는 설,<ref>Yaglom, I. M. (2001), "Two games with matchsticks", in Tabachnikov, Serge, Kvant Selecta: Combinatorics, I, Volume 1, Mathematical world 17, American Mathematical Society, p. 1–8</ref> 유럽의 선술집에서 하던 성냥개비 게임에서 왔다는 설 등이 있다. 어느 쪽이든 확실한 증거는 없다. {{ㅊ|그럼 도대체 뭐야 이 게임}} 기본적인 룰은 여러개의 돌 더미 중 하나를 골라 그 더미 안의 돌을 가져가는 것이며, 가장 마지막 돌을 가져가는 사람이 지는 게임이다. 규칙에 따라서는 마지막 돌을 가져가는 사람이 이기게 만들 수도 있으며, 수학적인 필승 전략과 그 원리는 동일하다. 아래 내용은 특별한 말이 없는한 마지막 돌을 가져가는 사람이 패배하는 규칙을 따른다. ==== 한 더미 ==== 배스킨 라빈스 31이 바로 이 유형. 돌 더미가 하나인 경우, 가져가는 돌의 개수에 제한을 두지 않으면 먼저하는 사람이 반드시 이기게 되어 게임의 의미가 없다.<ref>먼저 하는 사람이 돌 한 개만 남기고 다 가져가면 되기 때문</ref> 그래서 한 번에 가져갈 수 있는 돌의 수에 제한을 두게 된다. 아래 게임의 필승 전략을 스스로 한번 생각해 보자. {{인용문2|두 사람이 1부터 번갈아 숫자를 부른다. 한 번에 세 숫자까지 부를 수 있으며, 31을 부르면 진다. 당신이 이기기 위해서 먼저 숫자를 불러야 할까 나중에 불러야 할까? 필승 전략은?}} {{숨기기|힌트|30을 부르면 반드시 이길 수 있습니다. 30을 부르려면 어떤 수를 불러야 할까요?}} {{숨기기|풀이|30을 부르면 당신의 승리가 보장됩니다. 한 번에 숫자를 세 개까지 부를 수 있으므로, 30-(3+1)<nowiki>=</nowiki>26을 당신이 부르면 상대방이 몇 개의 숫자를 부르든 당신은 30을 부를 수 있습니다. 26을 부르기 위해서는 22를 부르면 되고, 22를 부르기 위해서는 18, 이런 식으로 쭉 내려가면 2를 불렀을 때 승리가 보장됩니다. 따라서 당신이 '''먼저''' 수를 2까지 부르면 승리합니다.}} 위 문제를 해결했으면, 일반적인 경우에 도전해 보자. {{인용문2|두 사람이 1부터 번갈아 숫자를 부른다. 한 번에 x개의 숫자를 부를 수 있으며, n을 부르면 진다. 필승 전략은 무엇일까?}} {{숨기기|풀이|n-1을 부르면 이긴다. n-1을 부르기 위해서는 n-1-(x+1)<nowiki>=</nowiki>n-x-2을 부르면 된다. 이 과정을 계속 반복하여 최초에 불러야 하는 수를 부르면 된다.}} 마지막으로, n을 부르면 '''이기는''' 경우의 필승 전략도 생각해 보자. {{숨기기|풀이|상대방이 n을 부를 수 없게 할려면, 자신이 n-(x+1)<nowiki>=</nowiki>n-x-1을 부르면 된다. 그러면 상대방이 몇 개의 수를 부르든, n은 x개의 안에 있으므로 당신은 항상 n을 부를 수 있다. 이 과정을 반복하면 된다.}} ==== 두 더미 ==== ==== 세 더미 이상 ==== ==== 변형 NIM ==== === 그룬디 게임 === === 숫자 지우기 === === 기타 === == 관련 항목 == {{각주}} [[분류:수학]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:ㅊ (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:글 숨김 (원본 보기) (준보호됨)틀:글 숨김 끝 (원본 보기) (준보호됨)틀:글 숨김 시작 (원본 보기) (준보호됨)틀:숨기기 (원본 보기) (준보호됨)틀:알림바 (원본 보기) (보호됨)틀:인용문2 (원본 보기) (준보호됨)틀:추천 문서 (편집) 틀:취소선 (원본 보기) (준보호됨)