모서리로만 이어진 색점, 몇 칸까지 칠할 수 있을까요?

사진을 크게 확대하면 대각선으로 닿은 색점들이 길처럼 보여요. 그런데 옆면으로는 어느 두 색점도 붙어 있지 않아요. 이 그림을 한 덩어리라고 볼까, 떨어진 여러 점이라고 볼까요?

ImageMagick의 공식 설명은 이미지의 이웃을 4 방향 또는 8 방향으로 정할 수 있다고 설명해요. 기본적으로는 색이 정확히 같은 이웃을 같은 영역으로 묶어요. 이웃에 모서리 방향을 포함하는지가 연결의 뜻을 바꿔요. 여기서는 프로그램의 실제 처리 결과 대신, 검은색·흰색 두 가지 칸으로 정한 자체 모형을 탐구해요.

가로 3 칸, 세로 4 칸을 볼까요? ●는 검은 칸, ·는 흰 칸이에요.

검은 칸 네 개는 모서리를 따라 하나의 길로 이어져요. 서로 변을 공유하는 쌍은 없어요. 8 방향 이웃으로는 한 덩어리지만, 변을 공유하는 4 방향 이웃으로는 네 개의 덩어리예요. 이름을 먼저 정하는 대신, 어떤 길을 허용하는지 정한 결과예요.

그림의 가로·세로 범위도 확인해 볼까요? 검은 칸이 첫 열과 마지막 열, 첫 행과 마지막 행에 있으므로 범위는 정확히 가로 3·세로 4 칸이에요. 열두 칸을 전부 검게 채운다는 뜻은 아니에요.

이 범위를 유지하며 옆면은 붙이지 않고, 모서리로는 전부 이어지게 해 볼까요? 검은 칸 수는 4 개부터 6 개까지 모두 가능해요. 표에서 셋째 행·첫 열을 더 칠하면 5 개가 되고, 다시 첫째 행·셋째 열을 더 칠하면 6 개예요. 새 칸은 대각선의 검은 칸과 이어지면서도 옆면은 공유하지 않아요. 7 개는 만들 수 없어요.

왜 7 개는 안 될까요? 행 번호와 열 번호를 더해 볼까요? 모서리 이웃으로 한 걸음 갈 때 두 번호가 각각 1만큼 변해요. 그 합의 홀짝은 그대로예요. 모두 이어진 검은 칸은 같은 홀짝만 사용해요. 직사각형을 체스판처럼 두 무리로 나누면 각각 6 칸이어서, 한 무리 안에 7 칸을 넣을 수 없어요.

이번에는 3 개만으로 가로 3·세로 4 칸을 차지할 수 있을까요? 첫 행에서 마지막 행까지 검은 길이 이어지려면, 한 걸음에서 행을 건너뛰지 못해 네 행을 모두 지나야 해요. 적어도 4 개가 필요해요. 가로 범위에서도 같은 논증을 해요.

모든 양의 정수 m,n 에 대해 세로 m·가로 n 칸으로 넓히자. 검은 칸끼리 변을 공유하지 않고 모서리로는 모두 이어지며, 검은 그림의 범위가 정확히 이 직사각형이어야 해요. 양쪽 치수가 2 이상이면 가능한 검은 칸 수 k 는

사이의 모든 정수예요. ⌈x⌉는 x 이상인 가장 작은 정수예요. 아래쪽 한계는 각 행·열을 지나야 한다는 조건이고, 위쪽 한계는 같은 홀짝의 칸만 쓴다는 조건이에요.

중간 개수에는 빠지는 수가 없을까요? 세로가 더 길다고 해 볼까요? 먼저 한 행에 하나씩 칠해 대각선으로 오른쪽 끝까지 간 뒤, 남은 행에서는 마지막 두 열을 번갈아 써요. 최소 개수로 모든 범위를 차지하는 검은 길이에요. 가로가 더 길면 행과 열을 바꿔요.

이 길은 한 홀짝 집합 안에 있어요. 그 홀짝의 전체 칸도 모서리로 이어져 있어요. 이웃한 두 행을 보면 그 칸들이 위아래를 번갈아 지나는 한 줄이고, 다음 두 행의 줄과도 공통 행에서 만나요. 현재 그림 바깥으로 이어지는 첫 칸을 하나씩 더하면 돼요. 연결·홀짝·끝 범위를 모두 유지하며 개수가 1씩 늘어나요. 이것이 양 끝뿐 아니라 그 사이의 모든 개수를 만드는 이유예요.

가장 많을 때의 그림은 체스판의 한 홀짝 칸을 전부 칠한 것뿐이에요. 전체 칸 수 mn 이 홀수이면 한 칸 더 많은 무리 하나만 최대예요. 짝수이면 두 무리의 크기가 같아 둘 다 최대예요. 칸 위치를 다르게 칠한 두 배치는 이 문제에서 따로 세어요.

가장 적을 때는 그림이 모두 같은 모양일까요? 세로 m 이 가로 n 이상이면 각 행에 정확히 하나씩 있어야 해요. 그 열 번호가 매번 1씩 왼쪽 또는 오른쪽으로 움직이고, 첫 열과 마지막 열을 둘 다 방문하는 목록이 모든 최소 배치예요.

정사각형에서는 주어진 걸음 수 안에 양 끝을 지나려면 한 방향으로만 가야 하므로 두 대각선뿐이에요. 세로 4·가로 3에서는 앞 표 말고도 세 가지 최소 배치가 더 있어요. 풀이에 네 목록을 모두 적었어요.

한 줄짜리 그림은 따로 보아야 해요. 세로 1 칸이나 가로 1 칸에서는 모서리 방향의 이웃이 없어지고, 연결하려면 변을 공유해야 해요. 그것을 금지했으니 검은 칸 하나만 남아요. 정확한 가로·세로 범위까지 맞는 것은 1×1뿐이에요.

제공 교재의 부분집합·여집합은 전체 칸에서 일부를 고르고 두 무리로 나누는 기초 언어예요. 픽셀의 이웃 정의, 모든 개수의 구성, 최소·최대 배치의 분류까지 그 교재에 실린 정리라는 뜻은 아니에요. 알려진 디지털 연결 규칙이나 체스판 홀짝 자체를 새 발견이라고 소개하지 않아요.

교사는 ‘이어져 보인다’는 답 옆에 실제로 밟을 검은 칸의 길을 적게 해요. 가능한 개수에는 실제 배치를, 불가능한 개수에는 행·열 또는 홀짝의 이유를 붙여요. 픽셀의 개수, 연결 덩어리의 개수, 그림이 차지한 범위는 서로 다른 양이에요. 실제 타일의 강도나 사진의 색상 측정 정확도를 판단한 활동은 아니에요.

착안: ImageMagick, Connected Components Labeling의 전체 본문에서 4·8 이웃과 정확한 색 일치 기준을 읽었어요. 격자의 색·변 공유 금지·정확한 가로세로 범위·예시와 전범위 증명은 자체 교육용으로 작성했어요. 원문 예시 이미지·통계표·명령이나 프로그램 코드를 옮기지 않았어요.