텃밭 열두 칸에 A·B·C·D 작물군을 각각4·4·2·2칸씩 배치해요. 매년 같은 칸 수만큼 분류 이름을 옮겨 적어요. 모든 칸에서 처음과 같은 작물군이 처음 다시 나오는 해를 같게 만들 수 있을까요? 그 공통 복귀를 최대 몇 년까지 늦출 수 있을까요?
실제 재배 일정 대신 번호0,…,n−1인 원형 칸들의 자체 계획을 정해요. n≥2이며, r종류의 작물군이 차지하는 칸 수 h₁,…,hᵣ은 양의 정수이고 합이 n입니다. 작물군은 미리 붙인 분류 이름이에요. 같은 군의 서로 다른 칸을 비교할 때 개별 식물의 동일성까지 비교하지 않아요. 모든 칸에는 군 이름 하나가 있어요.
처음 배치는 이 칸 수를 지키며 고를 수 있어요. d는1≤d≤n−1인 정수이고, 해마다 모든 이름을 번호가 커지는 방향으로 d칸씩 옮겨요. 끝을 넘으면0부터 세어요. y년째 k번 칸에 적힌 이름을 aᵧ(k)라 해요.
공통 최초 복귀 T란 모든 칸이 T년째에는 처음의 군 이름으로 돌아오며, 어느 칸도1,…,T−1년째에는 자기 처음 군 이름을 다시 갖지 않는다는 뜻이에요. T는2 이상인 정수예요. 첫 칸 하나만 검사하는 조건이 아니에요.
고정된 d와 후보 T에서 그런 초기 배치가 존재할 필요충분조건을 구하고, 가능할 때 배치를 구성해 보세요. d도 고를 수 있을 때 가능한 T 전체와 최댓값을 구해 볼까요? 칸을 도는 주기와 같은 작물군의 첫 복귀가 항상 같은지도 열두 칸 예에서 확인해 볼까요? 실제 식물을 옮기는 방법이나 병해충 효과를 판정하는 문제가 아니에요.
열두 칸 예의 답은 최대3년이에요. d=4로 정하고 번호0부터의 이름을 AAAACCDDBBBB로 놓아요. 1년 뒤에는 BBBBAAAACCDD, 2년 뒤에는 CCDDBBBBAAAA, 3년 뒤에는 처음 이름 목록이에요. 각 칸의 세 해 이름은 서로 달라서 어느 칸도1·2년째에 자기 처음 군으로 돌아오지 않아요. 이름 수는 언제나4·4·2·2입니다.
왜 가능한지, 다른 n과 칸 수에서도 어디까지 되는지 볼까요? 한 칸에서 d칸 이동을 반복하여 만나는 칸들을 한 묶음으로 잡아요. g를 n과 d의 최대공약수, L을 n/g라 하면 묶음은 g개이고 각각 L칸이에요. s번 이동해 원래 칸으로 돌아오려면 sd가 n의 배수여야 해요. n/g와 d/g가 서로소이므로 최초의 양의 s는 L입니다. 이 위치 순환 계산 자체는 알려진 도구예요.
한 묶음의 이름을 이동 순서로 읽으면 원형 이름 목록이에요. 모든 칸의 최초 복귀가 T이면 어느 시작 칸에서든 T칸 뒤의 이름이 같고, 더 이른 같은 이름은 없어요. 먼저 T가 L을 나누어야 해요. L을 T로 나눈 나머지를 b라 해 볼까요? T칸 이동으로 이름이 같고 L칸은 원래 위치이므로 b칸 이동으로도 같아요. 0<b<T라면 더 이른 복귀가 되어 모순이에요.
또한 연속한 T개 이름은 모두 달라야 해요. 두 자리에 같은 군이 있다면 앞자리에서 그보다 짧은 간격으로 돌아오기 때문이에요. 따라서 한 묶음은 서로 다른 T개 이름을 q=L/T번 반복한 모양일 때, 그리고 그때에만 모든 칸의 첫 복귀가 T입니다. 한 군은 한 묶음에 없거나 정확히 q번 들어가요.
이것이 고정된 d에서의 필요충분조건이에요. 기호 u∣v는 v가 u의 정수배라는 뜻이에요. T는2 이상이에요. 필요성은 방금 보았어요. 각 군의 총 칸 수 hᵢ는 q의 배수여야 하고, 그 군은 g개 묶음 중 hᵢ/q개에 한 번씩 들어가야 하므로 hᵢ/q≤g입니다.
충분성은 실제 배치로 확인해 볼까요? cᵢ=hᵢ/q라 두고 각 군 이름을 cᵢ개씩 종이에 써요. 같은 이름끼리 이어진 목록을 만들고, 그 목록을 g개 묶음에 차례로 하나씩 돌려 나누어 줘요. 전체 이름 표는 gT개이므로 각 묶음은 T개를 받아요. 같은 군의 표는 cᵢ≤g개라 한 바퀴를 넘지 않아 같은 묶음에 두 번 들어가지 않아요. 그래서 각 묶음은 서로 다른 T개 이름을 받아요.
받은 순서대로 이름을 놓고 그 T개 목록을 q번 반복하여 L칸을 채워요. 실제 칸은 번호가 가장 작은 칸부터 d칸씩 거꾸로 따라가며 채우면, 고정 칸이 보는 연도 순서와 일치해요. 묶음마다 모든 군의 첫 복귀가 T이며, 각 군의 전체 수는 q·cᵢ=hᵢ입니다. 필요한 칸 수와 첫 복귀 조건을 동시에 만드는 구성이에요. 필요조건만 적고 존재를 추측한 것이 아니에요.
이제 d도 고르면 답을 더 간단히 쓸 수 있어요. M은 가장 많은 군의 칸 수예요. 가능한 T의 전체 집합은 다음과 같아요.
고정 d 조건에서 T는 L의 약수라 n의 약수다. 또한 hᵢ≤gq=n/T이므로 TM≤n이 필요해요. 반대로 이 두 조건을 만족하면 d=n/T로 골라요. 이는1 이상 n−1 이하이며, 묶음 수가 n/T개, 묶음 길이가 T, q=1이 돼요. 각 hᵢ≤n/T이므로 위 구성을 바로 적용할 수 있어요. 따라서 집합 안의 모든 T가 가능해요. 집합이 비어 있으면 지금의 공통 최초 복귀 조건을 만족하는 계획은 없어요. 비어 있지 않으면 그 안의 가장 큰 약수가 최댓값이에요.
열두 칸에서는 M=4라 T≤3이어야 해요. 12의2 이상 약수 중 조건을 만족하는 것은2와3뿐이에요. 앞의 d=4 배치는 최대3을 이뤄요. d=3이면 묶음이3개이고 길이는4입니다. 두 묶음에 ABAB, 다른 묶음에 CDCD를 놓으면 각 군 수4·4·2·2를 지키며 첫 군 복귀는2년이에요. 칸의 이동은4년 만에 한 바퀴지만 이름은2년 만에 먼저 돌아와요. 모든 칸을 다 채웠다고 이 두 주기까지 같은 것은 아니에요.
반면 d=1은 묶음이 하나예요. 같은 군 수가 서로 다르면 공통 최초 복귀 T≥2를 만들 수 없어요. 그 한 묶음에서 모든 사용 군은 같은 q번씩 나타나야 하기 때문이에요. 원래 칸으로는12년 뒤 돌아와도, 모든 군 이름의 첫 복귀를 같은 해로 맞추었다는 결론은 나오지 않아요.
예외도 식에 남아요. 한 군만 있으면 매년 이미 같은 군이라 T≥2는 없어요. 모든 군을 한 칸씩만 쓰면 T=n이 가능해요. n이 소수이고 어떤 군을 두 칸 이상 쓰면 n의2 이상 약수가 n뿐인데 T=n은 모든 hᵢ=1을 요구하므로 공통 T≥2가 없어요. 이것은 자체 이동 규칙의 한계이며, 일반적인 돌려짓기가 불가능하다는 뜻은 아니에요.
교사는 ‘칸이 돌아오는 해’와 ‘같은 분류 이름이 처음 돌아오는 해’를 따로 적게 해요. 군 이름이 여러 칸에 쓰이면 위치 한 바퀴만 계산한 답은 충분하지 않아요. 제공 교재의 일대일 대응과 합성함수는 해마다 반복하는 번호 이동을 설명하는 기초 용어예요. 모든 칸의 첫 군 복귀·빈도 조건·구성·최대값은 이 글의 자체 질문과 증명이며 교재 정리라는 주장은 하지 않아요.
착안: Royal Horticultural Society, Crop rotation. 원문의 같은 크기 구역에서 작물군을 해마다 다른 구역으로 옮겨 배치한다는 관점만 참고했어요. 원문의 채소 목록·3년/4년 재배표·사진을 옮기지 않았어요. 숫자·분류 이름·같은 d칸 이동·공통 최초 복귀 조건은 자체 교육용이며 실제 재배 주기나 병해충 감소 효과를 권하는 글이 아니에요.