의예과 3번

(3-1) 주어진 조건 (i), (ii)에 의해 다음과 같은 부등식을 얻는다.$\displaystyle 0\le S(0,m]<S(m,2m]<\cdots<S(m^2,m^2+m]\le m$ -----------------(1)이 부등식에는 $\displaystyle m+1$개의 서로 다른 정수가 등장하고 이들은 0 이상 $\displaystyle m$ 이하이므로, $\displaystyle 0\le k\le m$일 때 $\displaystyle S(km,(k+1)m]=k$가 성립한다.

(a) 먼저 $\displaystyle k-1$번째 $\displaystyle m$-토막과 $\displaystyle k$번째 $\displaystyle m$-토막을 살펴보면 다음과 같다.$\displaystyle (\underbrace{0,\cdots,0}_{m-k+1},\underbrace{1,1,\cdots,1}_{k-1})(\underbrace{0,\cdots,0}_{\ell-1},1,\ast,\cdots,\ast)$ --------------------(2)여기서 $\displaystyle k-1$번째 $\displaystyle m$-토막의 $\displaystyle \ell+1$번째 항부터 $\displaystyle k$번째 $\displaystyle m$-토막의 $\displaystyle \ell$번째 항까지의 합인 $\displaystyle S(\ell+(k-1)m,\ell+km]$의 값은 $\displaystyle k$가 되고 결국 다음과 같은 부등식이 성립한다.$\displaystyle k=S(\ell+(k-1)m,\ell+km]<S(\ell+km,\ell+(k+1)m]<\cdots<S(\ell+(n-1)m,\ell+m^2]\le m$Correction. 마지막 토막의 합은 $\displaystyle S(\ell+(m-1)m,\ell+m^2]$이므로 여기의 $\displaystyle n$은 $\displaystyle m$의 오기다. 그러나 원칙에 따라 원문 표기를 그대로 실었다.

이 부등식에는 $\displaystyle m-k+1$개의 서로 다른 정수가 등장하고 이들은 $\displaystyle k$ 이상 $\displaystyle m$ 이하이므로, 등식$\displaystyle S(\ell+(j-1)m,\ell+jm]=j$가 성립한다.

(b) $\displaystyle k=0$일 때 성립함은 자명하다. $\displaystyle k-1$번째 $\displaystyle m$-토막에 대하여 성립한다고 가정하자. 이제 $\displaystyle k$번째 $\displaystyle m$-토막이 다음과 같은 꼴임을 보이면 된다.$\displaystyle \underbrace{0,\cdots,0}_{m-k},\underbrace{1,1,\cdots,1}_{k}$$\displaystyle k$번째 $\displaystyle m$-토막에서 처음 1이 나오는 것이 $\displaystyle \ell$번째 항이라 가정하고, 등식 $\displaystyle \ell=m-k+1$이 성립함을 보이면 증명이 완성된다.

$\displaystyle k-1$번째 $\displaystyle m$-토막부터 $\displaystyle m$번째 $\displaystyle m$-토막을 나열해 놓고 항들의 합 $\displaystyle \Sigma$를 생각해 보자. 우선, (3-1)의 결과에 의해 $\displaystyle \Sigma=(k-1)+k+(k+1)+\cdots+m$이다. $\displaystyle \Sigma$를 다른 방법으로 구해보면 다음과 같다. $\displaystyle k-1$번째 $\displaystyle m$-토막의 처음 $\displaystyle \ell$개의 항은 모두 0이고, 그 다음 항부터 마지막 $\displaystyle m$번째 $\displaystyle m$-토막의 $\displaystyle \ell$번째 항까지의 합을 (3-2)(a)의 결과인 $\displaystyle S(\ell+(j-1)m,\ell+jm]=j$를 이용해 구해 보면 $\displaystyle k+(k+1)+\cdots+m$이고, (3-1)의 결과에 의해 $\displaystyle m$번째 $\displaystyle m$-토막의 모든 항은 1이므로, 이것에 $\displaystyle m$번째 $\displaystyle m$-토막의 나머지 항들의 합 $\displaystyle m-\ell$을 더하면 $\displaystyle \Sigma=k+(k+1)+\cdots+m+(m-\ell)$이 된다. 이 두 결과를 비교해 보면$\displaystyle (k-1)+k+(k+1)+\cdots+(m-1)=k+(k+1)+\cdots+m+(m-\ell)$Correction. 바로 앞에서 구한 합과 비교하면 이 등식의 왼쪽 마지막 항은 $\displaystyle m-1$이 아니라 $\displaystyle m$이다. 그때 다음 줄의 결론 $\displaystyle k-1=m-\ell$이 나온다. 그러나 원칙에 따라 원문 표기를 그대로 실었다.이 되므로 등식 $\displaystyle k-1=m-\ell$을 얻고, 결국 $\displaystyle \ell=m-k+1$이 되어 증명이 완성되었다.