말랑말랑 수학문제 #3

<문제>

$2 \times N$ 격 좌표 안에 각 열의 두 수의 합이 모두 $1$ 이 되도록 실수가 적혀있다. 각 열의 두 수중 한 수를 제거할 때, 두 행에 적힌 모든 수들의 합이 각각 $\frac{N+1}{4}$ 을 넘지 않도록 제거할 수 있음을 보여라. 

아래 예시를 보면 첫 번째 행에선 $(0.5, 0.4, 0.5, 0.3, 0.1)$ 을 고르고, 두 번째 행에선 $(0.3, 0.7, 0.2)$ 을 고르면 각 행의 합이 모두 $2$ 이하여서 성립한다.

 

$0.5$	$0.4$	$0.7$	$0.5$	$0.3$	$0.1$	$0.8$
$0.5$	$0.6$	$0.3$	$0.5$	$0.7$	$0.9$	$0.2$

 

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

 

 

 

 

 

 

 

 

 

 

<풀이>

아래의 부등식들은 첫 번째 행의 숫자 $N$ 개 들을 작은 순서로 배열한 것이다. 

 

$$ \alpha_1 \leq \alpha_2 \leq \cdots \leq \alpha_N$$

 

만약 $\alpha_1$ 이 $\frac{N+1}{4}$ 보다 크다면, $1 = \sum_{i=1}^{N} \alpha_i \geq N \cdot \alpha_1 > \frac{N(N+1)}{4}$ 을 만족한다. 하지만, $N$ 은 자연수이므로 모순이다.

따라서 $1$ 부터 $N$ 사이 어떤 자연수 $k$ 가 존재하여 다음과 같은 관계를 만족한다.

 

$$\alpha_1+\cdots+\alpha_k \leq \frac{N+1}{4} \;,\; \alpha_1+\cdots+\alpha_{k+1} \geq \frac{N+1}{4}$$

 

위 식 두 번째 부등식에 다음과 같은 관계를 이끌어낼 수 있다.

 

$$(k+1)\alpha_{k+1} \geq \alpha_1+\cdots+\alpha_{k+1} > \frac{N+1}{4} \, \Rightarrow \, \alpha_{k+1} > \frac{N+1}{4(k+1)}   (1)$$

 

첫 번째 행들의 숫자 $\alpha_i$ 에 대응하는 두 번째 행들의 숫자를 $\beta_i$ 라 하자. ($\alpha_i$ 와 $\beta_i$ 는 같은 열)

$\beta_{k+1}+\cdots+\beta_{N} \leq \frac {N+1}{4}$ 이 관계가 성립하면 문제가 증명되므로 귀류법 적용을 위해 $\beta_{k+1}+\cdots+\beta_{N}>\frac{N+1}{4}$ 가 성립한다고 가정하자.

$\alpha$ 와 $\beta$ 의 관계에 의해 $\beta_{k+1} \geq \beta_{k+2} \geq \cdots \beta_{N}$ 이므로 아래와 같은 부등식을 이끌어 낼 수 있다.

 

$$(N-k)\beta_{k+1} \geq \beta_{k+1}+\cdots+\beta_{N} > \frac{N+1}{4}$$

 

따라서 $\beta_{k+1} > \frac{N+1}{4(N-k)}$ 가 성립한다. $\alpha_{k+1}+\beta_{k+1} = 1$ 이므로 (1) 부등식과 위 식에 의해 다음과 같은 결과가 나온다.

 

$$\frac{N+1}{4(k+1)} < \alpha_{k+1} = 1-\beta_{k+1} < 1-\frac{N+1}{4(N-k)} = \frac{3N-1-4k}{4(N-k)}$$

 

이 부등식을 정리해보면 다음과 같이 나온다.

 

$$N^2+N-kN-k < 3Nk+3N-k-1$$

$$N^2-2N-4Nk+4k+4k^2+1 < 0$$

$$(N-2k-1)^2 < 0$$

 

따라서 모순이므로 귀류법 가정에 모순이어서 증명되었다. $\; \blacksquare$