나머지 합이 10보다 작아요? 다 계산하지 않아도 반박할 수 있어요

R(10)을 10을 1부터 10까지의 각 정수로 나눈 나머지의 합으로 정의해요. 계산표를 모두 만들지 않고 R(10)<10이라는 주장이 불가능함을 설명해 볼까요? 일반적으로 R(2m)의 하한도 찾아봐요.

점이 찍힌 실제 도미노 조각

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

R(10)을 10을 1부터 10까지의 각 정수로 나눈 나머지의 합으로 정의해요. 계산표를 모두 만들지 않고 R(10)<10이라는 주장이 불가능함을 설명해 볼까요? 일반적으로 R(2m)의 하한도 찾아봐요. m은 양의 정수예요.

10을 6,7,8,9,10으로 나누면 몫은 모두 1이에요. 따라서 이 다섯 나머지는 각각 4,3,2,1,0이며 합이 이미 10이에요.

나머지의 다른 항은 모두 0 이상이므로 전체 합은 이 부분합보다 작을 수 없어요. 따라서 R(10)≥10이에요. 전부 계산하면 R(10)=13이지만, 주장을 반박하는 데 13이라는 정확한 값까지는 필요하지 않아요.

같은 논리를 짝수 2m에 적용해요. 등차수열의 합으로 이 부분의 나머지를 더할 수 있어요. 나누는 수가 m+1부터 2m이면 몫이 1이어서 나머지는 m−1부터 0까지예요.

R(2m)≥0+1+⋯+(m−1)=m(m−1)2.R(2m)\ge0+1+\cdots+(m-1)=\frac{m(m-1)}2.

HBCSE 해설은 큰 수의 나머지 합에서 이런 부분합을 이용해 가능한 범위를 줄여요. 이 글의 목표는 원문의 최종 정답을 옮기는 대신, 정확한 전체 계산보다 하한이 더 빨리 결론을 주는 장면을 새 질문으로 드러내는 거예요. ‘≥’를 ‘=’로 바꾸려면 남은 나머지에 어떤 조건이 필요한지도 확인해 볼 수 있어요.

출처·착안: RMO 2024 Official Solutions Problem 2. 문항과 풀이, 도식은 새로 작성했다.

이 글 공유하기

개인정보 및 방문 통계 안내