[백준] 2437번 문제 증명

https://www.acmicpc.net/problem/2437

2437번: 저울

정렬 후 배열은 $a1,a2...$라고 했을 때, $a1$이 $1$이 아닐 때와 $a1$일 때 이렇게 두 가지 경우가 있다. 전자에는 바로 $1$로 출력하면 된다.

후자의 경우 논리적 과정을 명확하게 하기 위해 몇 가지를 설명하겠다.

​

식 $e:a_{n+1}\le sum(n)+1(sum(n)는a_1부터a_n까지의합)$

명제 $p:a_1=1$이고, $n$이 $1$ 부터 $k$일 때, 식 $e$ 를 만족한다면, $a_1$부터 $a_{k+1}$ 사이의 어떤 수의 조합으로 $sum(k+1)$ 이하의 모든 자연수를 표현하는 것이 가능하다.

​

$k=1$일 때는 자명하다.

​

​$k=m$일 때 명제 $p$ 가 성립한다고 가정하면, $sum(m+1)$ 이하의 모든 자연수는 표현이 가능하다.

 

$k=m+1$일 때, $x\le sum(m+2)$ 즉 $x\le sum(m+1)+a(m+2)$ 이하의 모든 자연수가 표현이 가능한지를 판단해야한다.

여기서 $k=m$ 일 때 성립한다고 했으니 범위를 좁히면 $sum(m+1)+1\le x\le sum(m+1)+a(m+2)$ 로 만들 수 있고,$k=m+1$ 일 때, 식$e$ 를 만족하므로 $a_{m+2}\le x\le sum(m+1)+a_{m+2}$ 이하의 수들이 표현 가능한지만 판단하면 된다.이 수들을 표현할 때, 기본으로  $a_{m+2}$ 를 항상 선택하면 $a_1$ 부터 $a_{m+1}$ 를 $0$ 개부터 $m+1$ 사이의 어떤 수  $p$ 개를 이용하여 $sum(m+1)$ 이하의 모든 수를 표현할 수 있으므로 귀납법으로 증명이 된다.

​

이 과정을 예시로 들면 $a_1=1,a_2=2$라고 했을 때,$sum(2)=3$ 이니 $2$가지를 이용하여 $1,2,3$이라는 숫자를 만드는 게 가능하다. 그 때 여기에 $a_3=4$ 라고 한다면 $4$단독으로도 가능하고, $4$에 각각 $1,2,3$을 더 한 것도 가능하니 $7$까지 표현이 가능하다. 이런 식으로 계속 확장해 나아가는 것이다. 한 마디로 식 $e$를 설정하는 것이 $4$와 같은 연결 부분을 만들 수 있다는 것이다.