토큰 색을 바꾸는 놀이, 선 하나를 더 그으면 풀릴까요?

두 색 동시 전환에서 전체가 아니라 연결 묶음별 파랑 수의 홀짝이 목표 도달을 결정함을 증명해요.

어두운 바닥에 나란히 놓인 여러 색의 나무 색연필 끝

사진: Dietmar Rabich · CC BY-SA 4.0 · 원본 출처

네 토큰을 줄 세워 1,2,3,4번이라 하고 처음 색은 파랑·빨강·파랑·빨강이에요. 선으로 연결된 두 토큰을 고르면 그 두 색을 동시에 반대로 바꿔요. 연결선이 {1,2},{3,4}뿐일 때 모두 빨강으로 만들 수 있나요? 연결선 {2,3}을 하나 더 허용하면 달라지나요?

(B,R,B,R),E0={{1,2},{3,4}}.(B,R,B,R),\qquad E_0=\{\{1,2\},\{3,4\}\}.

처음 파란 토큰은 두 개라 전체 홀짝 검사는 통과해요. 그런데 끊어진 두 묶음에는 각각 파랑이 한 개예요. 묶음 안의 두 색을 함께 바꾸면 그 묶음의 파랑 수는 2만큼 늘거나 줄거나 그대로예요. 각 묶음의 홀짝은 바뀌지 않아요. 모두 빨강인 목표는 두 묶음 모두 파랑0개라 도달할 수 없어요.

가운데 연결선을 허용하면 다음 두 조작으로 목표를 얻어요.

(B,R,B,R)→{1,2}(R,B,B,R)→{2,3}(R,R,R,R).(B,R,B,R)\xrightarrow{\{1,2\}}(R,B,B,R)\xrightarrow{\{2,3\}}(R,R,R,R).

전체 파랑 수의 짝수성만 보는 것과 서로 오갈 수 있는 연결 묶음별로 그 수를 보는 것은 다른 검사예요. 새 선은 색 바꾸기 규칙 자체를 바꾸지 않고 두 묶음을 연결해요.

일반적인 유한 연결 그림에서도 각 연결 묶음의 파랑 수가 짝수이면 모두 빨강으로 만들 수 있어요. 같은 묶음의 파랑 두 점을 잇는 같은 점을 반복해서 지나지 않는 경로 하나를 택해 그 경로의 선을 각각 한 번 조작해요. 양 끝점은 한 번, 중간점은 두 번 바뀌어 끝의 파랑 둘만 빨강이 돼요. 짝들을 반복해서 없애면 돼요. 따라서 묶음별 짝수성이 필요조건이며 충분조건이에요.

전체 파랑 수가 같다는 정보만으로 두 연결 그림의 도달 가능성을 같게 보았는지 확인해 봐요. 실제 대상의 모습보다 어느 쌍에 조작을 허용했는지가 불변량의 단위를 정해요.

착안 원문: Chameleon Island: Two Colors. 원문의 두 색 전환 규칙에서 연결선과 목표 도달 조건을 새로 구성했어요. 원문에 일반 필요충분조건의 증명이 제시되어 있다고 주장하지 않아요.

이 글 공유하기

개인정보 및 방문 통계 안내