말랑말랑 수학문제 #1

앞으로 개인적으로 재미있게 생각했던 수학 문제들을 공유할 생각입니다. elementary 한 방법론을 가지고 풀 수 있는 문제들을 위주로 다룰 것이기에 재밌게 봐주셨으면 좋겠습니다!!

 

<문제>

$n \times n$ 의 격자판에 $1$ 부터 $n$ 까지의 숫자를 $n$ 개씩 임의의 방식으로 써놓았다. 이때, 적어도 서로 다른 $ \sqrt n$ 개 이상의 수를 가지고 있는 행 또는 열이 존재함을 보여라. 

 

$1$	$1$	$1$	$5$	$5$
$1$	$1$	$5$	$5$	$5$
$3$	$2$	$2$	$2$	$4$
$3$	$3$	$2$	$4$	$4$
$3$	$3$	$2$	$4$	$4$

 

예를 들어, 다음과 같은 $5 \times 5$ 의 격자에는 $3$ 개의 서로 다른 숫자를 가지고 있는 행 또는 열이 존재한다. 

 

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

 

 

 

 

 

 

 

 

 

 

<풀이>

이 문제를 해결하기 위해선 간단한 '더블카운팅(double counting)'을 활용하면 된다. 

먼저 귀류법을 이용할 건데 모든 행과 열의 숫자 종류가 $\sqrt n$ 보다 작다고 가정 하자.

$1$ 부터 $n$ 까지의 숫자 중 임의의 숫자 $k$ 를 생각하자. 그리고 $k$ 가 속하는 행의 개수를 $a_k$ 개, 열의 개수를 $b_k$ 개라고 하자.

$k$ 가 속한 행들 집합과 열들 집합의 교집합을 생각해보자. 총 $a_kb_k$ 개의 격자들이 선택될 것인데, $k$ 는 정의에 의해 무조건 $a_kb_k$ 개의 격자들에 속해야 한다. 따라서 $n \leq a_kb_k$ 라는 부등식이 성립한다.$(\because$ $k$ 가 총 $n$ 개 존재$)$

 

산술기하 부등식에 의해 $4a_kb_k$ $\leq$ $(a_k+b_k)^2$ 이므로 위 두 부등식에 의해 다음과 같은 결론을 얻는다.

 

$$2\sqrt n \leq a_k+b_k$$

 

숫자 $k$ 는 임의로 선택한 것이므로 $1$ 부터 $n$ 각각 속한 행과 열의 개수 총합이 $2n \sqrt n$ 개 이상 존재한다.

 

이젠 반대의 관점에서 카운팅 해보면, 각각의 행과 열이 가지고 있는 숫자의 종류를 생각해보자.

귀류법 가정에 의해 모든 행과 열이 $\sqrt n$ 개 보다 적은 개수를 가지고 있으므로 모든 행과 열을 더해보면 $2n \sqrt n$ 개 미만 존재한다. 

 

같은 값을 카운팅 했는데 $2n \sqrt n$ 이상, 미만을 둘 다 만족하므로 모순이다. 

따라서 적어도 어떤 행 또는 열은 서로 다른 $ \sqrt n$ 개의 수를 가지고 있게 된다. $\blacksquare$