말랑말랑 수학문제 #16

<문제>

자연수 $a, b$ 에 대하여 $a! + b!$ 이 $a!b!$ 을 나눌 때 다음 부등식이 성립함을 보여라.

 

$$3a \geq 2b+2$$

 

$($단, $n! = 1 \cdot 2 \cdots (n-1) \cdot n$ 이다.$)$

 

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

 

 

 

 

 

 

 

 

 

 

<풀이>

(풀이에 앞서 $|$ 라는 기호를 사용할텐데 이는 '나눈다'라는 뜻이다. 예를들어 $2 | 4$ 는 $2$ 는 $4$ 를 나눈다는 뜻이다.)

 

우선 $a$ 와 $b$ 의 대소관계를 살펴보자. 만약 $a > b$ 라면 $3a > 3b \geq 2b+1$ 이므로 $3a \geq 2b+2$ 가 성립한다. 즉 $a \leq b$ 인 경우만 고려하면 충분하다.

 

case1) $a=b$ 인 경우

만약 $a=b=1$ 이면 $a! + b! = 1+1=2$ 이고 $a!b! = 1$ 이므로 $2$ 는 $1$ 을 나눌수 없어서 모순이다. 따라서 $a=b \geq 2$ 를 만족하여 $3a \geq 2b+2$ 가 성립하게 된다.

 

case2) $a < b$ 인 경우

$b>a$ 이므로 $a! | b!$ 을 만족하여 $a! + b! | a!b!$ 은 두 항을 $a!$ 으로 나눠 $1 + b(b-1)\cdots(a+1) | b!$ 으로 변형할 수 있다. 

$a+1 \leq i \leq b$ 인 $i$ 에 대해 $1+b(b-1)\cdots(a+1)$ 을 $i$ 로 나눈 나머지가 1이므로 $i$ 와 $1+b(b-1)\cdots(a+1)$ 은 서로소이다. 즉, $1 + b(b-1)\cdots(a+1) | b!$ 은 $1 + b(b-1)\cdots(a+1) | a!$ 과 동치가 된다.

 

$b, b-1, \cdots, a+1$ 은 숫자가 총 $b-a$ 개이므로 $1 \leq p \leq b-a$ 인 $p$ 에 대해 $p|v$ 인 $v \in \{ b, b-1, \cdots, a+1 \}$ 가 적어도 하나 이상은 존재한다. 즉 $p$ 와 $1+b(b-1)\cdots(a+1)$ 은 서로소이므로 만약 $b-a \geq a$ 이면 $1 + b(b-1)\cdots(a+1) | a!$ 는 $1 + b(b-1)\cdots(a+1) | 1$ 을 나누는 것과 동치가 되어 모순이다. 따라서 $b-a < a$ 임을 알 수 있고 다음과 같은 관계를 얻어낼 수 있다.

 

$$1+b(b-1)\cdots(a+1) | a(a-1)\cdots(b-a+1)$$

 

좌변이 우변을 나누면 당연히 좌변의 값은 우변의 값보다 작거나 같아야 하므로

 

$$1+b(b-1)\cdots(a+1) \leq a(a-1)\cdots(b-a+1)...(1)$$

 

이 성립하고 $A = \{b, b-1, \cdots, a+1\}$ 는 $b-a$ 개, $B = \{a, a-1. \cdots, b-a+1\}$ 는 $2a-b$ 개다. 그러므로 $b-a < 2a-b$ 가 되어 $3a \geq 2b+1$ 이 성립한다.$(\because$ $A$ 의 원소들은 모두 $B$ 의 원소들보다 크므로 (1) 부등식이 만족하려면 $B$ 의 원소 개수가 더 많아야 한다.) 

 

만약 $3a = 2b+1$ 이라면, $2b+1$ 이 홀수여서 $a$ 도 홀수가 된다. 그 말은 $a+1$ 이 짝수이므로 

 

$$1+ b(b-1)\cdots(a+1) = 1+b(2b-2)\cdots(\frac{a+1}{2})$$

 

이렇게 적을 수 있고 $2b-2 = 3(a-1)$ 이므로 $a-1$ 은 $1+b(b-1)\cdots(a+1)$ 과 서로소가 된다. 즉, 다음과 같은 관계를 이끌어낼 수 있다.

 

$$1+b(b-1)\cdots(a+1) | a(a-2)\cdots(b-a+1)$$

 

우변에 곱해진 수는 총 $2a-b-1$ 개이고 좌변은 $b-a$ 개이므로 $b-a < 2a-b-1$ 이 성립하여 $3a > 2b+1$ 이 성립한다. 따라서 $3a = 2b+1$ 이라는 가정에 모순이기 때문에 자연스레 $3a \geq 2b+2$ 를 얻어낼 수 있다. $\blacksquare$