여러 칸을 가린 표, 합계만 보고 숨긴 값을 알 수 있을까요?

각 행과 열에서 두 칸 이상을 가리면, 합계를 보고도 그 값은 알 수 없을까요? 서랍 네 개에 든 네 색 구슬의 개수를 세었다는 자체 표를 볼까요? □와 x는 가린 칸이며, 0과 합계는 정확하게 공개해요. 가능한 표에는 0 이상의 정수만 허용해요.

모든 행과 열에 가림칸이 두 개 이상이에요. 그래도 첫 두 서랍의 합은 6이고, 색 A·B의 합은 4입니다. 두 합에서 같은 구슬들은 지워지고 x만 남아요.

다른 칸을 모두 알 필요도 없어요. 왼쪽 네 가림칸은 모두 1일 수도, 대각선 두 칸이 2이고 나머지가 0일 수도 있어요. 합계는 같지만 x는 어느 경우에도 2입니다. ‘표 전체가 하나로 정해지지 않는다’와 ‘어느 칸도 정해지지 않는다’는 다른 주장이에요.

이제 어떤 가림칸이 정해지는지 일반 표에서 판정하자. 이미 보이는 칸의 값을 행·열 합계에서 먼저 빼요. 행 이름과 열 이름을 서로 다른 점으로 놓고, 가림칸 하나마다 해당 행·열 두 점을 선으로 이어요. 선에 적힌 수가 그 가림칸의 값이에요. 점에 모인 선의 수들이 합쳐져 그 행 또는 열의 남은 합계를 만들어요.

이번 분류는 모든 가림칸의 실제 기준값이 1 이상인 표에 적용해요. 비교할 다른 표의 값은 계속 0 이상의 정수까지 허용해요. 기준표의 양수성은 아래에서 값을 1씩 줄이는 표를 만들기 위한 가정이며, 비교표에도 양수만 허용한다는 뜻은 아니에요.

선을 하나 없앨 때 그 연결 묶음이 둘로 갈라지면 그 선을 브리지라고 부를게요. 이 경우 가림값은 정해져요. 갈라진 한쪽에 있는 행의 남은 합계를 모두 더하고 열의 남은 합계를 모두 빼면, 그 안의 선은 한 번 더해지고 한 번 빠져 사라져요. 바깥과 연결된 선은 방금 없앤 선 하나뿐이라 그 값, 또는 그 값의 음수만 남아요. 앞 표에서는 서랍 1·2와 색 A·B를 한쪽으로 잡은 거예요.

반대로 브리지가 아닌 선의 두 끝은 그 선을 빼도 다른 길로 연결돼요. 그 길과 원래 선을 합치면 순환이 돼요. 행과 열을 번갈아 지나므로 순환 길이는 짝수예요. 순환의 선들에 1을 더하고 1을 빼는 조작을 교대로 해 볼까요?

각 점에서는 두 변화량이 상쇄되므로 모든 합계가 그대로예요. 기준값이 모두 1 이상이어서 1을 뺀 값도 0 이상이에요. 해당 칸의 값이 달라지는 다른 허용 표를 실제로 만들었으므로 그 칸은 하나로 정해지지 않아요.

따라서 이 가정 아래에서는 가림칸의 값이 하나로 정해질 필요충분조건이 그 선이 브리지인 거예요. 가림 연결 그림에 순환이 하나도 없을 때만 표 전체가 유일해요. 가림값에 0이 있는 기준표에는 역방향 증명을 그대로 적용하지 않아요. 예를 들어 네 칸을 모두 가린 2×2 표의 행·열 합계가 모두 0이면, 순환이 있어도 네 값은 모두 0뿐이에요.

ONS는 합계에서 차를 내어 가린 값을 알아낼 가능성과 추가 가림을 설명해요. 여기서는 실제 통계 대신 구슬 표를 만들고, 빈칸 수보다 연결 구조를 보는 수학 조건을 증명했어요. 교사는 각 줄의 빈칸 개수만 세는 답에 ‘여러 행의 합과 여러 열의 합을 한꺼번에 빼면 무엇이 남는가’를 물어요. 실제 개인정보 공개 절차를 설계하거나 개인 기록을 복원한 결과는 아니에요.

착안: ONS, §4.2–4.3, 용어 정의: MathWorld, Graph Bridge. 표·문항·기준 양수/비교 비음수 조건과 판정 증명은 자체 교육용으로 작성했어요.