Mex(수학)

수학에서 잘 정렬된 집합의 부분 집합의 mex는 부분 집합에 속하지 않는 전체 집합에서 가장 작은 값이다. 즉, 그것은 보완 집합의 최소값이다. mex라는 이름은 "최소 제외" 값의 속칭이다.

집합 이상으로, 잘 정렬된 클래스의 하위 클래스는 최소 제외 값을 가진다. 순서 번호의 하위 클래스의 최소 제외 값은 조합 게임 이론에 사용되어 공정한 게임에 민첩한 값을 부여한다. 스프래그-그룬디 정리에 따르면, 게임 포지션의 님-값은 주어진 포지션에서 한 번의 움직임으로 도달할 수 있는 포지션 가치 등급의 최소 제외 값이다.^[1]

최소 제외 값은 또한 그래프 이론, 탐욕스러운 컬러링 알고리즘에서도 사용된다. 이러한 알고리즘은 일반적으로 그래프의 정점 순서를 선택하고 사용 가능한 정점 색상의 번호 지정을 선택한다. 그런 다음, 그들은 정점을 순서대로 고려한다. 정점의 색상을 선택하는 각 정점들이 이미 이웃에 할당된 색상 집합의 최소 제외 값이다.^[2]

예

다음 예제는 모두 주어진 집합이 서수 번호 클래스의 하위 집합이라고 가정한다.

${\displaystyle \vmsname {mex}(\emptyset )=0}$

${\displaystyle \designname {mex}(\{1,2,3\}=0})$

${\displaystyle \desname {mex}(\{0,2,4,6,\ldots \}=1}$

${\displaystyle \designname {mex}(\{0,1,4,7,12\}=2}$

${\displaystyle \desname {mex}(\{0,1,2,3,\ldots \}=\omega })$

${\displaystyle \exname {mex}(\{0,1,2,3,\ldots,\omega \}=\omega +1})$

여기서 Ω은 자연수에 대한 한계 서수이다.

게임 이론

스프래그-그룬디 이론에서 최소 제외 서수식은 정상 플레이 공정 게임의 민첩성을 결정하는 데 사용된다. 이런 경기에서는 두 선수 모두 포지션별로 같은 움직임을 보이고, 마지막으로 움직이는 선수가 승리한다. 첫 번째 선수가 바로 패한 경기에서는 민첩성이 0과 같으며, 다른 경기에서는 가능한 모든 다음 포지션의 민첩성과 같다.

예를 들어, 님을 1마일 버전에서 게임은 n개의 돌무더기로 시작하며, 움직일 플레이어는 어떤 양의 돌멩이도 가져갈 수 있다. n이 0석이라면, 법적 움직임의 빈 집합의 mex가 0이 되기 때문에 민첩성이 0이다. n이 1스톤이면 움직일 플레이어는 0스톤을 남기고, mex({0}) = 1은 이 경우에 민첩성을 부여한다. n이 2 스톤이면 움직일 플레이어가 0 또는 1 스톤을 남길 수 있어 민첩한 2를 민첩한 {0, 1}의 멕스로 준다. 일반적으로 n개의 돌무더기를 가지고 움직이는 플레이어는 0부터 n-1의 돌무더기까지 어디든 떠날 수 있다.; {0, 1, …, n-1}의 곱셈은 항상 더 민첩한 n이다. 첫 번째 선수는 님에서 0이 아닌 경우에만 승리하기 때문에, 이 분석에서 우리는 님의 1마일 경기에서 첫 번째 선수가 0이 아닌 경우에만 승리한다고 결론 내릴 수 있다. 승자는 모든 돌을 가져가는 것이다.

이동할 플레이어가 최대 3개의 스톤만 차지할 수 있도록 경기를 바꾸면 n = 4개의 스톤으로 후임 국가는 민첩한 {1, 2, 3}을(를) 부여한다. 4개의 스톤을 위한 민첩성이 0이기 때문에 첫 번째 선수는 진다. 두 번째 선수의 전략은 첫 번째 선수가 하는 동작이 무엇이든 나머지 스톤을 가져가서 대응한다는 것이다. n = 5스톤의 경우, 후계국 2, 3, 4스톤의 민첩성은 2, 3, 0(지금 계산한 대로), 민첩한 {0, 2, 3} 세트의 mex는 민첩한 1이므로 이 게임에서 5스톤부터 시작하는 것이 첫 번째 선수의 승리다.

더 빠른 값의 의미에 대한 자세한 내용은 민첩성을 참조하십시오.

참조