SET을 외칠 수 없는 카드는 최대 몇 장인가

역시 좋아했던 수학 채널 PBS Infinite Series(지금은 연재 종료)의 SET 게임에 대한 영상.

SET은 총 81장의 카드를 가지고 하는 게임으로, 그림처럼 카드에는 문양의 모양, 개수, 색깔, 얼마나 채워져있는가의 4가지 속성이 있다. 이 4가지 속성은 각각 3가지 경우로 나뉘고, 네 속성이 전부 동일한 카드 쌍은 존재하지 않는다. (그래서 81=3^4개) 이 때 어떤 세 장의 카드가 있어 각각의 속성마다 모두 동일한 경우이거나 모두 서로 다른 경우라면 이 셋을 SET이라 부르고, 카드를 한 장씩 놓으며 SET을 빨리 많이 찾아내는 게임이다. 예컨대 위 그림의 경우 맨 윗줄의 왼쪽과 가운데, 맨 아랫줄의 가운데 카드를 보면 모양은 전부 같고, 개수는 전부 다르고, 색은 전부 다르고, 셋 다 속이 비어있으므로 SET을 이룬다. 스팀에서 이걸 아주 약간 변형한 비디오게임화한 Mindsight이란 게임도 나와있다.

학부 신입생 때 SET을 처음 접하고서, SET을 선언할 수 없는 카드의 장수의 최댓값이 어떻게 나올지에 대해 생각을 해보았다. 각각의 카드를 \mathbb{F}_3^4의 원소로 대응시키면 (각각의 속성을 좌표에 대응) a+b+c=0a,b,c \in \mathbb{F}_3^4가 SET을 이룬다는 것까진 쉽게 확인할 수 있었고 최댓값이 20일 것이라고 추측까진 했지만 증명은 못했었다. 영상에서도 이 문제에 대해 다루는데, 의외로 어렵지 않게 double counting으로 증명하는 방법이 있었다. [1]

\mathbb{F}_3^d에서 a+b+c=0a,b,c(직선을 의미하기도 함)를 포함하지 않는 집합을 d-cap이라고 할 때, 이 d-cap의 원소 개수의 최댓값은 d=1,2,3,4,5일 때 각각 2,4,9,20,45가 된다고 한다.

d \leq 5일 때의 d-cap들의 예시
Source: https://doi.org/10.1007/BF02984846


d=1인 경우는 자명하고, d=2일 때는 만약 5개의 원소가 있다고 할 때 위 그림처럼 \mathbb{F}_3^2의 원소를 3 \times 3으로 배열하면 2개의 가로줄에서 2개의 원소를 가져야 하고 1개의 가로줄엔 1개의 원소를 갖는데 이 원소를 지나는 4개의 직선 중 가로줄에 해당하는 1개를 제외하고 생각하면 비둘기 집 원리에 의해 어떤 직선에는 또 다른 2개의 원소가 있어야 해 모순이 되어 귀류법으로 증명된다.

이 결과를 응용해 3-cap C의 원소가 최대 9개임을 보인다. 10개의 원소를 갖는다고 가정. \mathbb{F}_3^3을 3개의 평행한 평면 H_1,H_2,H_3으로 분할한다면, 각각의 층은 2-cap이어야 하므로 각각 최대 4개의 원소를 가질 수 있어서, multiset \{ |C \cap H_1|,|C \cap H_2|,|C \cap H_3| \}\{4,4,2\}이거나 \{4,3,3\}이 된다. 전자와 후자에 해당하도록 3개의 층으로 분할하는 경우의 수를 각각 a,b로 둔다. \mathbb{F}_3^3을 3개의 평행한 평면으로 분할하는 경우의 수는 곧 그들과 수직한 벡터를 (up to scaling) 구하는 경우의 수와 같아 \frac{3^3-1}{2}=13개이므로 a+b=13이어야 한다.

이제 평면 H와 서로 다른 x,y의 집합으로 이루어진 순서쌍의 집합 S = \{(H, \{x,y\}):x,y \in H \cap C\}을 생각한다. \{x,y\}를 택할 때마다 그들을 지나는 평면의 개수는 4개이므로 |S| = 4\binom{10}{2}=180이다. 한 편, \{ |C \cap H_1|,|C \cap H_2|,|C \cap H_3| \} = \{4,4,2\}H_1,H_2,H_3을 택할 때마다 H의 원소가 \binom{4}{2}+\binom{4}{2}+\binom{2}{2}=13개 등장하고, 나머지 경우는 \binom{4}{2}+\binom{3}{2}+\binom{3}{2}=12개 등장한다. 즉 |S| = 13a+12b가 된다. 이로부터 13a+12b=180을 얻어 연립방정식을 풀면 a=24,b=-11이 되어 모순을 얻는다.

4-cap의 경우도 이 증명을 적용할 수 있다. 증명을 진행하기에 앞서, “주어진 affine subspace를 포함하는 hyperplane의 개수”를 명확히 구한다. (바로 앞 문단에서도 등장함) \mathbb{F}_3^d에서 k차원 affine subspace K가 주어져있을 때, natural map \mathbb{F}_3^d \rightarrow \mathbb{F}_3^d/K \simeq \mathbb{F}_3^{d-k}을 통해서 조건을 만족시키는 hyperplane의 개수는 곧 \mathbb{F}_3^{d-k}의 원점을 지나는 hyperplane의 개수이고, 이는 0이 아닌 벡터의 개수(up to scaling)이므로 \frac{3^{d-k}-1}{2}가 된다.

4-cap C가 21개의 원소를 갖는다고 가정한다. 4-cap을 3개의 hyperplane으로 분할할 때마다 앞에서처럼 각각의 층 안에 있는 C의 원소의 개수를 센 multiset을 따지면 합이 21인 9 이하의 정수들, 즉 \{9,9,3\},\{9,8,4\},\{9,7,5\},\{9,6,6\},\{8,8,5\},\{8,7,6\},\{7,7,7\}가 된다. \{i,j,k\}에 해당하는 hyperplane 분할법의 개수를 x_{i,j,k}로 둔다. 4-cap을 3개의 hyperplane으로 분할하는 것은 원점을 지나는 hyperplane을 잡는 것과 동일하고 앞 문단에 의해 그 경우의 수는 \frac{3^4-1}{2}=40개가 되어 다음 식을 얻는다.

\displaystyle x_{993}+x_{984}+x_{975}+x_{966}+x_{885}+x_{876}+x_{777}=40

이번에도 3-cap에서처럼, hyperplane H와 서로 다른 원소 x,y의 집합으로 이루어진 순서쌍의 집합 S = \{(H, \{x,y\}):x,y \in H \cap C\}을 생각한다. \{x,y\}를 택할 때마다 그들을 지나는 hyperplane의 개수는 \frac{3^3-1}{2}=13개이므로 |S| =  13\binom{21}{2}=2730이다. 또한 앞에서와 같은 논리로

\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}

을 얻고, |S|=2730에 의해

\displaystyle 75x_{993}+70x_{984}+67x_{975}+66x_{966}+66x_{885}+64x_{876}+63x_{777}=2730

을 얻는다.

비슷하게 hyperplane H와 서로 다른 원소 x,y,z의 집합으로 이루어진 순서쌍의 집합 T = \{(H, \{x,y,z\}):x,y,z \in H \cap C\}을 생각한다. 이런 x,y,z는 4-cap C의 원소이므로 직선을 이룰 수 없어 무조건 2차원 평면을 이룬다. 앞에서처럼 double counting을 하면 |T|=4\binom{21}{3}=5320

\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}

을 얻어

\displaystyle 169x_{993}+144x_{984}+129x_{975}+124x_{966}+122x_{885}+111x_{876}+105x_{777}=5320

을 얻는다. 세 식을 각각 (1), (2), (3)으로 두면 693(1)+3(3)-6(2)5x_{984}+8x_{975}+9x_{966}+3x_{885}+2x_{876}=0이 되어 이 다섯 변수는 0이 되어야 하고, 따라서 (2)-63(1)에서부터 12x_{993}=210을 얻어 모순이 된다. 따라서 4-cap의 원소는 최대 20개가 된다.

[2]에서는 finite field의 Fourier transform으로 d-cap C가 어떤 hyperplane과도 최대 h개의 교점을 가지면 \displaystyle |C| \leq \frac{1+3h}{1+\frac{h}{3^{d-1}}}임을 증명했고, 이를 이용해서 5-cap의 원소 개수가 최대 45임도 증명할 수 있다. 이는 [1]을 참조.

트윗 타래를 정리. (2018/03/16)

References

[1] B. L. Davis and D. Maclagan, “The card game set” The Mathematical Intelligencer (2003) 25: 33. DOI: 10.1007/BF02984846

[2] J. Bierbrauer and Y. Edel, “Bounds on affine caps” J. Combin. Des., 10(2):111-115, 2002, DOI: 10.1002/jcd.10000

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중