말랑말랑 수학문제 #15

<문제>

다음 식을 만족하는 자연수 $n$ 을 모두 구하시오.

 

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\left[ \frac{ij}{n+1} \right] = \frac{n^2(n-1)}{4}$$

 

(단, $[x]$ 는 $x$ 를 넘지 않는 최대의 정수를 나타내는 기호이다.)

 

-----풀이 스포를 주의하세요-----

 

 

 

 

 

 

 

 

 

 

<풀이>

case1) $n$ 이 짝수인 경우

왼쪽의 식을 보면 그냥 더하는 것은 어려워 보이므로 약간의 트릭을 사용한다. $[\;]$ 기호 안에 있는 수들의 합이 정수가 된다면 계산이 편리해지기 때문에 아래와 같이 대칭적으로 항들을 더하게 된다.

 

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\left[ \frac{ij}{n+1} \right] = \sum_{i=1}^{n}\sum_{j=1}^{\frac{n}{2}}\left[ \frac{ij}{n+1} \right]+\left[ \frac{i(n+1-j)}{n+1} \right]$$

 

$[x]$ 는 $x$ 를 넘지 않는 최대의 정수를 나타내는 기호로 정의했기 때문에 $x-1 < [x] \leq x$ 의 관계를 만족한다. 이러한 관계를 통해 다음과 같은 결과를 얻을 수 있다.

 

$$i-2 = \frac{ij + i(n+1-j)}{n+1} - 2 < \left[ \frac{ij}{n+1} \right]+\left[ \frac{i(n+1-j)}{n+1} \right] \leq \frac{ij + i(n+1-j)}{n+1} = i$$

 

$\left[ \frac{ij}{n+1} \right] + \left[ \frac{i(n+1-j)}{n+1} \right]$ 값은 정수이므로 $i-1, i$ 만 가능하다.

 

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\left[ \frac{ij}{n+1} \right] = \sum_{i=1}^{n}\sum_{j=1}^{\frac{n}{2}}\left[ \frac{ij}{n+1} \right]+\left[ \frac{i(n+1-j)}{n+1} \right] \geq \sum_{i=1}^{n}\sum_{j=1}^{\frac{n}{2}} (i-1) = \sum_{i=1}^{n} \frac{n(i-1)}{2} = \frac{n}{2} \cdot \frac{n(n-1)}{2} = \frac{n^2(n-1)}{4} $$

 

그리하여 위와 같은 부등식을 얻게 되는데 이 부등식의 등호조건이 우리가 원하는 경우이므로 모든 $1 \leq j \leq \frac{n}{2}$ 에 대해 $\left[ \frac{ij}{n+1} \right] + \left[ \frac{i(n+1-j)}{n+1} \right] = i-1$ 을 만족해야 한다. 그리고 $x-1 < [x] \leq x$ 에 의해 $\left[ \frac{ij}{n+1} \right] + \left[ \frac{i(n+1-j)}{n+1} \right] = i$ 이려면 $\left[ \frac{ij}{n+1} \right] \, ,$ $\, \left[ \frac{i(n+1-j)}{n+1} \right]$ 둘 다 정수이어야 성립한다. 즉, 하나라도 두 값이 정수가 되는 $i, j$ 가 생기면 문제의 식을 만족하지 않는 것이다.

 

$n+1$ 이 소수가 아닌 이상 $1 \leq i \leq n \, , \, 1 \leq j \leq \frac{n}{2}$ 인 $i, j$ 에 대해 $ij = n+1$ 인 $i, j$ 가 무조건 존재하여 문제의 식을 만족할 수가 없다. 따라서 이 경우 $n+1$ 이 소수여야 한다.

 

$(i, j$ 가 무조건 존재하는 이유 : $n+1$ 을 나누는 가장 작은 소수 $p$ 를 생각하자. 만약 $p > \frac{n}{2}$ 라면 $\frac{n+1}{p} < 2+\frac{1}{p} <3$ 이 되어 $\frac{n+1}{p} = 2 \, or \, 1$ 이 된다. $n+1$ 은 홀수이므로 $2$ 인 경우 모순이고 $n+1$ 은 소수가 아니라고 가정했으므로 $1$ 도 모순이 되어 $p \leq \frac{n}{2}$ 가 된다. 따라서 $i = \frac{n+1}{p} \, , \, j=p$ 로 고르면 된다.$)$

 

case2) $n$ 이 홀수인 경우 $(n \geq 3)$

위와 유사한 방식으로 더해보면 아래와 같이 나온다.

 

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\left[ \frac{ij}{n+1} \right] = \sum_{i=1}^{n}(\sum_{j=1}^{\frac{n-1}{2}}\left[ \frac{ij}{n+1} \right]+\left[ \frac{i(n+1-j)}{n+1} \right]) + \left[ \frac{i}{2} \right]$$

 

마찬가지로 $\left[ \frac{ij}{n+1} \right]+\left[ \frac{i(n+1-j)}{n+1} \right] \geq i-1$ 이므로 

 

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\left[ \frac{ij}{n+1} \right] \geq \sum_{i=1}^{n} \frac{(n-1)(i-1)}{2} + \left[ \frac{i}{2} \right] = \frac{n-1}{2} \cdot \frac{n(n-1)}{2} + (1+1+2+2+\cdots+\frac{n-1}{2}+\frac{n-1}{2})$$

 

을 만족한다. 하지만

 

$$\frac{n-1}{2} \cdot \frac{n(n-1)}{2} + (1+1+2+2+\cdots+\frac{n-1}{2}+\frac{n-1}{2}) = \frac{n(n-1)^2}{4} + 2 \cdot \frac{\frac{n-1}{2} \cdot \frac{n+1}{2}}{2} = \frac{n^3-n^2+n-1}{4} > \frac{n^2(n-1)}{4}$$

 

이므로 $n=1$ 인 경우를 제외한 $n$ 이 홀수인 경우 문제의 식을 만족하지 않는다. $n=1$ 도 $n+1$ 이 소수이므로 답은 아래와 같이 작성된다.

답) $n+1$ 이 소수