파스칼 삼각형의 행번호 n은 0~15 중 하나예요. n 행의 k번째 계수는 C(n,k), k=0,…,n이고 k>n이면 0으로 정해요. 홀수 계수가 8개라는 기록만으로 n을 찾을 수 있나요? 다음 네 위치의 나머지도 확인했다면 n을 결정해 보세요.
| k | 1 | 2 | 4 | 8 |
|---|---|---|---|---|
| C(n,k)를2로 나눈 나머지 | 1 | 0 | 1 | 1 |
다항식 계수의 홀짝만 보면 제곱의 중간항 2AB는 사라져요. 이를 반복하여 (1+x)^(2^j)의 홀수 항은 1과 x^(2^j)만 남아요. 따라서 n의 이진 표기에서 1인 자리마다 인수 1+x^(2^j)를 하나씩 곱한 식이 (1+x)^n과 같은 계수 홀짝을 가져요. 서로 다른 자리의 부분합은 이진 표기의 유일성 때문에 겹치지 않아요.
1인 자리가 r개이면 부분집합 선택 2^r개가 모두 홀수 계수 위치가 돼요. 홀수 8개는 r=3만 알려 주므로 범위 안에서 n=7,11,13,14가 모두 가능해요. 반면 지수 2^j는 더 작은 서로 다른 거듭제곱들의 합으로 만들 수 없어 해당 자리 인수를 선택해야만 얻어요. 표가 바로 a₀=1, a₁=0, a₂=1, a₃=1을 주므로 n=1+4+8=13입니다. 이 행의 홀수 위치는 0,1,4,5,8,9,12,13으로 8개예요.
Cameron의 조합론 원문은 Lucas 정리로 파스칼 삼각형의 홀짝 구조를 설명해요. 여기는 원문의 별표 그림이나 연습문제를 옮기지 않고, 전체 개수 기록과 네 지정 위치 기록이 숨겨진 행번호를 얼마나 구별하는지 새 질문으로 정했어요. 19세기 Lucas 원전 전체를 읽었다고 주장하지 않아요.
교사는 관찰 수가 네 개면 언제나 충분하다는 결론을 내리지 않아요. 어떤 위치를 골랐는지가 각 이진 자릿값과 연결되어야 해요. 전체 홀수 개수는 위치를 버린 요약이어서 같은 요약의 네 행을 실제 반례로 남겨요.
착안 원문: Peter J. Cameron, Notes on Combinatorics: congruences and proof of Lucas’ theorem. 행번호 범위와 네 위치의 관측 표·복원 계산은 자체 문항이며 원문의 별표 그림이나 연습문제를 옮긴 것이 아니에요.