역시 좋아했던 수학 채널 PBS Infinite Series(지금은 연재 종료)의 SET 게임에 대한 영상.
SET은 총 81장의 카드를 가지고 하는 게임으로, 그림처럼 카드에는 문양의 모양, 개수, 색깔, 얼마나 채워져있는가의 4가지 속성이 있다. 이 4가지 속성은 각각 3가지 경우로 나뉘고, 네 속성이 전부 동일한 카드 쌍은 존재하지 않는다. (그래서 개) 이 때 어떤 세 장의 카드가 있어 각각의 속성마다 모두 동일한 경우이거나 모두 서로 다른 경우라면 이 셋을 SET이라 부르고, 카드를 한 장씩 놓으며 SET을 빨리 많이 찾아내는 게임이다. 예컨대 위 그림의 경우 맨 윗줄의 왼쪽과 가운데, 맨 아랫줄의 가운데 카드를 보면 모양은 전부 같고, 개수는 전부 다르고, 색은 전부 다르고, 셋 다 속이 비어있으므로 SET을 이룬다. 스팀에서 이걸 아주 약간 변형한 비디오게임화한 Mindsight이란 게임도 나와있다.
학부 신입생 때 SET을 처음 접하고서, SET을 선언할 수 없는 카드의 장수의 최댓값이 어떻게 나올지에 대해 생각을 해보았다. 각각의 카드를 의 원소로 대응시키면 (각각의 속성을 좌표에 대응) 인 가 SET을 이룬다는 것까진 쉽게 확인할 수 있었고 최댓값이 20일 것이라고 추측까진 했지만 증명은 못했었다. 영상에서도 이 문제에 대해 다루는데, 의외로 어렵지 않게 double counting으로 증명하는 방법이 있었다. [1]
에서 인 (직선을 의미하기도 함)를 포함하지 않는 집합을 -cap이라고 할 때, 이 -cap의 원소 개수의 최댓값은 일 때 각각 2,4,9,20,45가 된다고 한다.
인 경우는 자명하고, 일 때는 만약 5개의 원소가 있다고 할 때 위 그림처럼 의 원소를 으로 배열하면 2개의 가로줄에서 2개의 원소를 가져야 하고 1개의 가로줄엔 1개의 원소를 갖는데 이 원소를 지나는 4개의 직선 중 가로줄에 해당하는 1개를 제외하고 생각하면 비둘기 집 원리에 의해 어떤 직선에는 또 다른 2개의 원소가 있어야 해 모순이 되어 귀류법으로 증명된다.
이 결과를 응용해 3-cap 의 원소가 최대 9개임을 보인다. 10개의 원소를 갖는다고 가정. 을 3개의 평행한 평면 으로 분할한다면, 각각의 층은 2-cap이어야 하므로 각각 최대 4개의 원소를 가질 수 있어서, multiset 은 이거나 이 된다. 전자와 후자에 해당하도록 3개의 층으로 분할하는 경우의 수를 각각 로 둔다. 을 3개의 평행한 평면으로 분할하는 경우의 수는 곧 그들과 수직한 벡터를 (up to scaling) 구하는 경우의 수와 같아 개이므로 이어야 한다.
이제 평면 와 서로 다른 의 집합으로 이루어진 순서쌍의 집합 을 생각한다. 를 택할 때마다 그들을 지나는 평면의 개수는 4개이므로 이다. 한 편, 인 을 택할 때마다 의 원소가 개 등장하고, 나머지 경우는 개 등장한다. 즉 가 된다. 이로부터 을 얻어 연립방정식을 풀면 이 되어 모순을 얻는다.
4-cap의 경우도 이 증명을 적용할 수 있다. 증명을 진행하기에 앞서, “주어진 affine subspace를 포함하는 hyperplane의 개수”를 명확히 구한다. (바로 앞 문단에서도 등장함) 에서 차원 affine subspace 가 주어져있을 때, natural map 을 통해서 조건을 만족시키는 hyperplane의 개수는 곧 의 원점을 지나는 hyperplane의 개수이고, 이는 0이 아닌 벡터의 개수(up to scaling)이므로 가 된다.
4-cap 가 21개의 원소를 갖는다고 가정한다. 4-cap을 3개의 hyperplane으로 분할할 때마다 앞에서처럼 각각의 층 안에 있는 의 원소의 개수를 센 multiset을 따지면 합이 21인 9 이하의 정수들, 즉 가 된다. 에 해당하는 hyperplane 분할법의 개수를 로 둔다. 4-cap을 3개의 hyperplane으로 분할하는 것은 원점을 지나는 hyperplane을 잡는 것과 동일하고 앞 문단에 의해 그 경우의 수는 개가 되어 다음 식을 얻는다.
이번에도 3-cap에서처럼, hyperplane 와 서로 다른 원소 의 집합으로 이루어진 순서쌍의 집합 을 생각한다. 를 택할 때마다 그들을 지나는 hyperplane의 개수는 개이므로 이다. 또한 앞에서와 같은 논리로
을 얻고, 에 의해
을 얻는다.
비슷하게 hyperplane 와 서로 다른 원소 의 집합으로 이루어진 순서쌍의 집합 을 생각한다. 이런 는 4-cap 의 원소이므로 직선을 이룰 수 없어 무조건 2차원 평면을 이룬다. 앞에서처럼 double counting을 하면 과
을 얻어
을 얻는다. 세 식을 각각 (1), (2), (3)으로 두면 은 이 되어 이 다섯 변수는 0이 되어야 하고, 따라서 에서부터 을 얻어 모순이 된다. 따라서 4-cap의 원소는 최대 20개가 된다.
[2]에서는 finite field의 Fourier transform으로 -cap 가 어떤 hyperplane과도 최대 개의 교점을 가지면 임을 증명했고, 이를 이용해서 5-cap의 원소 개수가 최대 45임도 증명할 수 있다. 이는 [1]을 참조.
일 때의 
![\displaystyle |S| = \left[ \binom{9}{2}+\binom{9}{2}+\binom{3}{2} \right] x_{993} + \cdots + \left[ \binom{7}{2}+\binom{7}{2}+\binom{7}{2} \right]x_{777}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%7CS%7C+%3D+%5Cleft%5B+%5Cbinom%7B9%7D%7B2%7D%2B%5Cbinom%7B9%7D%7B2%7D%2B%5Cbinom%7B3%7D%7B2%7D+%5Cright%5D+x_%7B993%7D+%2B+%5Ccdots+%2B+%5Cleft%5B+%5Cbinom%7B7%7D%7B2%7D%2B%5Cbinom%7B7%7D%7B2%7D%2B%5Cbinom%7B7%7D%7B2%7D+%5Cright%5Dx_%7B777%7D&bg=ffffff&fg=000000&s=0&c=20201002)
![\displaystyle |T| = \left[ \binom{9}{3}+\binom{9}{3}+\binom{3}{3} \right] x_{993} + \cdots + \left[ \binom{7}{3}+\binom{7}{3}+\binom{7}{3} \right]x_{777}](https://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%7CT%7C+%3D+%5Cleft%5B+%5Cbinom%7B9%7D%7B3%7D%2B%5Cbinom%7B9%7D%7B3%7D%2B%5Cbinom%7B3%7D%7B3%7D+%5Cright%5D+x_%7B993%7D+%2B+%5Ccdots+%2B+%5Cleft%5B+%5Cbinom%7B7%7D%7B3%7D%2B%5Cbinom%7B7%7D%7B3%7D%2B%5Cbinom%7B7%7D%7B3%7D+%5Cright%5Dx_%7B777%7D&bg=ffffff&fg=000000&s=0&c=20201002)
udaqueness 