맨위로가기

님버

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

님버는 두 명의 플레이어가 번갈아 가며 물건을 제거하는 게임인 님 게임과 관련된 수학적 개념이다. 각 더미의 물건 수를 나타내는 님버는 님 덧셈과 님 곱셈이라는 연산을 통해 분석되며, 이러한 연산은 님 게임의 승리 전략을 결정하는 데 사용된다. 님버는 크램, 노스콧 게임, 해켄부쉬 등 다양한 게임의 분석에도 활용되며, 대수적으로 닫힌 체를 형성하는 등 흥미로운 수학적 구조를 갖는다.

더 읽어볼만한 페이지

  • 순서수 - 초한수
    초한수는 게오르크 칸토어가 도입한 무한 개념을 확장한 수로, 집합의 크기를 나타내는 기수와 정렬된 집합 내의 위치를 나타내는 서수로 나뉘며, 무한에도 여러 종류가 있음을 밝혀 현대 수학의 기초를 다졌다.
  • 순서수 - 자연수
    자연수는 수를 세는 데 사용되는 가장 기본적인 수로, 덧셈과 곱셈에 닫혀 있고, 페아노 공리계를 통해 정의되며, 수학적 귀납법으로 명제를 증명하는 데 활용된다.
  • 조합론적 게임 이론 - 젠가
    젠가는 54개의 나무 블록으로 타워를 쌓아 블록을 제거하고 위에 올려 타워를 무너뜨리지 않고 버티는 게임이며, 마지막으로 턴을 완료한 플레이어가 승리한다.
  • 조합론적 게임 이론 - 게임 복잡도
    게임 복잡도는 상태 공간, 게임 트리 크기, 결정 복잡성, 게임 트리 복잡도, 계산 복잡성과 같은 척도를 사용하여 게임의 난이도와 경우의 수를 정량적으로 측정하는 개념이다.
  • 유한체 - 이산 로그
    이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
  • 유한체 - 순환 중복 검사
    순환 중복 검사(CRC)는 데이터 전송 또는 저장 시 오류 검출을 위해 데이터를 다항식으로 간주하고 생성 다항식으로 나눈 나머지를 검사 값으로 사용하여 오류를 감지하는 기술이다.
님버
기본 정보
유형수
분야조합론적 게임 이론
발명가리처드 가이
발견 연도1976년
수학적 특성
연산덧셈
곱셈
항등원덧셈: 0
곱셈: 1
역원덧셈: 각 님버는 덧셈에 대한 자신의 역원임
곱셈: 0을 제외한 각 님버는 곱셈에 대한 역원을 가짐
순서잘 정렬됨
예시
예시 목록0, 1, 2, 3, ... ω, ω+1, ...
관련 개념
관련 항목기수
순서수

2. 님 게임

님(Nim)은 두 명의 플레이어가 번갈아 가며 여러 개의 더미에서 물건을 제거하는 수학 게임이다. 님 게임의 핵심은 각 더미의 물건 개수를 님버로 표현하고, 님 덧셈을 통해 전체 게임의 님버 값을 계산하여 필승 전략을 찾는 것이다.[2]

2. 1. 님 게임의 규칙

님은 두 명의 플레이어가 서로 번갈아 가며 서로 다른 더미에서 물건을 제거하는 방식으로 진행되는 수학 게임이다. 님은 두 플레이어 중 누가 현재 움직이는지에 관계없이 움직임이 위치에만 의존하고 보상이 대칭적이므로 공정한 게임이다. 각 차례에 플레이어는 최소한 하나의 물건을 제거해야 하며, 모두 같은 더미에서 가져온다면 원하는 만큼의 물건을 제거할 수 있다. 게임의 목표는 마지막 물건을 제거하는 플레이어가 되는 것이다.[2]

더미의 님버(nimber)는 해당 더미에 있는 물건의 수이다. 님 덧셈을 사용하면 전체 게임의 님버를 계산할 수 있다. 승리 전략은 상대방 차례에 게임의 님버를 0으로 만드는 것이다.[2]

2. 2. 님 덧셈

님 덧셈은 님 게임에서 여러 더미의 님버를 계산하여 하나의 더미로 나타낼 때 사용하는 연산이다. 님 덧셈은 다음과 같이 재귀적으로 정의된다.[2]

: α ⊕ β = mex({α' ⊕ β : α' < α} ∪ {α ⊕ β' : β' < β})

여기서 최소 제외수(mex)는 집합에 속하지 않는 가장 작은 수를 의미한다.

유한한 크기의 님 더미에서는 님 덧셈을 비트별 배타적 논리합(XOR, ⊕)으로 간단하게 계산할 수 있다. 예를 들어, 님버가 7인 더미와 14인 더미의 님 덧셈 결과는 다음과 같다. 7은 이진수로 111이고, 14는 1110이다. 각 자릿수를 XOR 연산하면 1001이 되는데, 이는 십진수로 9이다. 즉, 7과 14의 님 덧셈 결과는 9이다.

님 덧셈은 교환 법칙과 결합 법칙이 성립하며, 0은 덧셈에 대한 항등원이다. 또한, 어떤 님버는 자기 자신을 더하면 0이 된다. 즉, α ⊕ β = 0 이면 α = β 이다.[4]

3. 님버의 활용

님버는 님 게임뿐만 아니라 다른 공정한 게임들을 분석하는 데에도 활용된다. 공정한 게임이란 두 플레이어에게 동일한 움직임이 가능한 게임을 의미한다. 이러한 게임들은 님버 값을 통해 분석될 수 있다.

크램, 노스콧 게임, 해켄부쉬 등이 님버를 활용하여 분석할 수 있는 대표적인 공정한 게임들이다.

3. 1. 크램 (Cram)

크램은 플레이어들이 가로 또는 세로로 도미노를 번갈아 놓는 게임으로, 더 이상 놓을 수 없을 때까지 진행된다. 주로 직사각형 보드에서 진행되며, 더 이상 움직일 수 없는 첫 번째 플레이어가 패배한다. 두 플레이어 모두에게 가능한 움직임이 동일하므로 공정한 게임이며 님버 값을 가질 수 있다. 예를 들어, 짝수 크기의 보드는 님버 값이 0이다. 짝수 x 홀수 보드는 0이 아닌 님버 값을 갖는다. 보드는 모든 짝수 에 대해 님버 값이 0이고, 모든 홀수 에 대해 님버 값이 1이다.

3. 2. 노스콧 게임 (Northcott's game)

노스콧 게임에서 각 플레이어의 말(pegs)은 유한한 수의 공간을 가진 열을 따라 배치된다. 각 턴마다 각 플레이어는 열을 따라 말을 위 또는 아래로 움직여야 하지만, 상대방의 말을 지나칠 수는 없다. 여러 열이 함께 쌓여 복잡성을 더한다. 더 이상 움직일 수 없는 플레이어가 패배한다. 다른 님버 관련 게임과 달리, 각 행에서 두 말 사이의 공간 수는 님 힙(Nim heaps)의 크기이다. 상대방이 두 말 사이의 공간 수를 늘리면, 다음 차례에 줄이기만 하면 된다. 그렇지 않으면, 님 게임을 플레이하고 각 행에서 말 사이의 공간 수의 님-합(Nim-sum)이 0이 되도록 만든다.[3]

3. 3. 해켄부쉬 (Hackenbush)

해켄부쉬는 존 호턴 콘웨이가 발명한 게임이다. 색깔이 있는 선분들이 서로 끝점끼리 연결되어 있고, "지면" 선과 연결된 모든 형태에서 플레이할 수 있다. 플레이어는 교대로 선분을 제거하며, 지면 선에 연결하기 위해 새로 제거된 선분에 의존하는 모든 선분도 함께 제거된다. 님버를 사용하여 분석할 수 있는 공정한 게임 버전은 선의 구분을 없애고, 두 플레이어 모두 어떤 가지든 제거할 수 있도록 하는 것이다. 이런 방식으로, 지면에 대한 각 연결은 님버 값을 가진 님 더미로 간주될 수 있으며, 지면 선에 대한 모든 개별 연결도 게임 상태의 님버를 위해 합산될 수 있다.[1]

4. 님버의 연산

님버 곱셈('''님-곱셈''')은 다음과 같이 재귀적으로 정의된다.

: \alpha \, \beta = \operatorname{mex} \! \bigl(\{\alpha' \beta \oplus \alpha \, \beta' \oplus \alpha' \beta' : \alpha' < \alpha, \beta' < \beta \} \bigr).

님버 곱셈은 결합 법칙과 교환 법칙이 성립하며, 서수 1을 곱셈의 항등원으로 갖는다. 또한, 님버 곱셈은 님버 덧셈에 대해 분배 법칙을 만족한다.[4]

님버의 집합은 님버가 고유 집합을 형성하고 집합이 아니라는 사실을 제외하면 환을 형성한다. 님버는 대수적으로 닫힌 체를 결정하며 표수는 2이다. 0이 아닌 서수 α의 님버 곱셈 역원은 다음과 같다.

:\alpha^{-1} = \operatorname{mex}(S),

여기서 S는 다음과 같은 조건을 만족하는 최소의 서수(님버) 집합이다.

# 0은 S의 원소이다.

# 0 < α' < α이고 β'가 S의 원소라면, \tfrac{1 + (\alpha' \oplus \alpha) \beta'}{\alpha'} 또한 S의 원소이다.

모든 자연수 n에 대해, 2^{2^n}보다 작은 님버의 집합은 갈루아 체 GF(2^{2^n})를 형성하며, 그 차수는 2^{2^n}이다. 유한한 님버의 집합은 n → ∞일 때 체 GF(2^{2^n})의 직접 극한과 동형이다. 이 부분 체는 대수적으로 닫혀 있지 않다. k가 2의 거듭제곱이 아닌 체 GF(2^k)는 그러한 체의 어느 곳에도 포함되지 않기 때문에 직접 극한에도 포함되지 않기 때문이다. 예를 들어, 다항식 x^3 + x + 1은 GF(2^3)에서 근을 가지지만, 유한한 님버 집합에서는 근을 갖지 않는다.

유한 서수의 님버 곱을 계산하는 방법은 다음 규칙에 따른다.

# 페르마 2의 거듭제곱(2^{2^n} 형태의 숫자)과 더 작은 숫자의 님버 곱은 일반적인 곱과 같다.

# 페르마 2의 거듭제곱 x의 님버 제곱은 자연수의 일반적인 곱셈으로 계산된 3x/2와 같다.

님버의 가장 작은 대수적으로 닫힌 체는 서수 \omega^{\omega^\omega}보다 작은 님버의 집합이며, 여기서 ω는 가장 작은 무한 서수이다. 님버로서 \omega^{\omega^\omega}는 체에 대해 초월수이다.[5]

2의 거듭제곱의 님버 곱셈

4. 1. 님버 덧셈 (Nim-addition)

님 덧셈은 님 더미들의 집합과 동일한 단일 님 더미의 크기를 계산하는 데 사용될 수 있다. 님 덧셈은 다음과 같이 재귀적으로 정의된다.

: α ⊕ β = mex({α' ⊕ β : α' < α} ∪ {α ⊕ β' : β' < β})

여기서 최소 제외수(mex)는 순서수 집합 ''S''의 원소가 "아닌" 가장 작은 순서수로 정의된다.

유한 순서수에 대해, 님-합은 컴퓨터에서 해당 숫자의 비트별 배타적 논리합(XOR, ⊕로 표시)을 수행하여 쉽게 계산할 수 있다. 예를 들어, 7과 14의 님-합은 7을 이진수 111로, 14를 이진수 1110으로 작성하여 찾을 수 있다. 각 자리수를 XOR 연산하면, 1001이 되고, 이는 십진수로 9이다.

이러한 덧셈의 속성은 mex와 XOR 모두 님 게임에 대한 승리 전략을 산출하고 그러한 전략은 하나만 있을 수 있다는 사실에서 비롯된다. 또는 귀납법으로 직접적으로 보여줄 수 있다. α와 β를 두 개의 유한 순서수라고 하고, 이 중 하나가 감소된 모든 쌍의 님-합이 이미 정의되어 있다고 가정한다. α와 XOR 연산을 수행하여 α ⊕ β 가 되는 유일한 숫자는 β이며, 반대의 경우도 마찬가지이다. 따라서 α ⊕ β는 제외된다.

: ζ := α ⊕ β ⊕ γ

반면에, 모든 순서수 γ < α ⊕ β에 대해 ξ와 α, β 및 γ를 XOR하면 이 중 하나를 줄여야 한다 (ξ의 선행 1은 세 개 중 적어도 하나에 있어야 하기 때문). 왜냐하면

: ζ ⊕ γ = α ⊕ β > γ,

따라서 다음 중 하나가 있어야 한다.

: α > ζ ⊕ α = β ⊕ γ,

: β > ζ ⊕ β = α ⊕ γ;

따라서 γ는 다음 중 하나로 포함된다.

: (β ⊕ γ) ⊕ β,

: α ⊕ (α ⊕ γ);

따라서 α ⊕ β는 최소 제외 순서수이다.

님버 덧셈은 결합 법칙과 교환 법칙을 가지며, 0을 덧셈의 항등원으로 한다. 또한, 님버는 자체 덧셈 역원이다.[4] 따라서 α ⊕ β = 0 오직 그리고 만약에만 α = β이다.

4. 2. 님버 곱셈 (Nim-multiplication)

님버 곱셈(님-곱셈)은 다음과 같이 재귀적으로 정의된다.

:

님버 곱셈은 결합 법칙과 교환 법칙이 성립하며, 서수 1을 곱셈의 항등원으로 갖는다. 또한, 님버 곱셈은 님버 덧셈에 대해 분배 법칙을 만족한다.[4]

따라서, 님버가 고유 집합을 형성하고 집합이 아니라는 사실을 제외하면, 님버의 집합은 환을 형성한다. 사실, 님버는 심지어 대수적으로 닫힌 체를 결정하며 표수는 2이다. 0이 아닌 서수 α의 님버 곱셈 역원은 다음과 같다.

:

여기서 S는 다음과 같은 조건을 만족하는 최소의 서수(님버) 집합이다.

# 0은 S의 원소이다.

# 만약 0 < α' < α이고 β'가 S의 원소라면, 또한 S의 원소이다.

모든 자연수 n에 대해, 보다 작은 님버의 집합은 갈루아 체 를 형성하며, 그 차수는 이다. 따라서, 유한한 님버의 집합은 n → ∞일 때 체 의 직접 극한과 동형이다. 이 부분 체는 대수적으로 닫혀 있지 않다. 왜냐하면 k가 2의 거듭제곱이 아닌 체 는 그러한 체의 어느 곳에도 포함되지 않기 때문에 직접 극한에도 포함되지 않기 때문이다. 예를 들어, 다항식 은 에서 근을 가지지만, 유한한 님버 집합에서는 근을 갖지 않는다.

님버 덧셈의 경우와 마찬가지로, 유한 서수의 님버 곱을 계산하는 방법이 있다. 이는 다음 규칙에 의해 결정된다.

# 페르마 2의 거듭제곱( 형태의 숫자)과 더 작은 숫자의 님버 곱은 일반적인 곱과 같다.

# 페르마 2의 거듭제곱 x의 님버 제곱은 자연수의 일반적인 곱셈으로 계산된 와 같다.

님버의 가장 작은 대수적으로 닫힌 체는 서수 보다 작은 님버의 집합이며, 여기서 ω는 가장 작은 무한 서수이다. 결과적으로, 님버로서 는 체에 대해 초월수이다.[5]

4. 3. 덧셈과 곱셈 표

님버 덧셈
+0123456789101112131415
00123456789101112131415
11032547698111013121514
22301674510118914151213
33210765411109815141312
44567012312131415891011
55476103213121514981110
66745230114151213101189
77654321015141312111098
88910111213141501234567
99811101312151410325476
101011891415121323016745
111110981514131232107654
121213141589101145670123
131312151498111054761032
141415121310118967452301
151514131211109876543210



님버 곱셈
*0123456789101112131415
00000000000000000
10123456789101112131415
20231810119121415134675
30312121513144756811910
40481262141011153713951
50510152781336912141114
60611131485371121091524
70791410133415861521211
80812411371513519614102
90914715618512112103413
100101553912611114428137
110111367121019241514538
120124813195610214117153
130136119415214385710112
140147951121210413315186
150155101144112137831269



처음 16개의 님버(0~15)에 대한 덧셈과 곱셈 표이다. 이 집합은 두 연산(덧셈, 곱셈) 모두에 대해 닫혀있다. 16은 22n 형태이기 때문이다.

님버 덧셈 표. 작은 행렬은 이진수의 단일 숫자를 보여준다.


님버 곱셈 표. 작은 행렬은 순열된 이진 왈시 행렬이다.


5. 님버의 대수적 구조

님버의 집합은 표수 2의 대수적으로 닫힌 체를 이룬다.[1] 님버 덧셈과 님버 곱셈은 갈루아 체 ${\displaystyle \mathbb {F} _{2^{2^{n}}}}$의 연산과 같다. 님버의 가장 작은 대수적으로 닫힌 체는 ${\displaystyle \omega ^{\omega ^{\omega }}}$보다 작은 님버들의 집합이다.[2] (여기서 ${\displaystyle \omega }$는 최소 무한 순서수이다.)

참조

[1] 서적 Advances in computer games : 14th International Conference, ACG 2015, Leiden, the Netherlands, July 1-3, 2015, Revised selected papers 2015-12-24
[2] 서적 Introduction to the design & analysis of algorithms Pearson 2012
[3] 웹사이트 Theory of Impartial Games http://web.mit.edu/s[...] 2009-02-03
[4] 서적 The Unity of Combinatorics American Mathematical Society
[5] 서적 Conway 1976


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com