격자점 두 점 선택

[출제의도] 조합을 활용하여 문제해결하기 집합 $\displaystyle D = \left\{ \left( x , y \right) \left| 0 \leq x \leq n , 0 \leq y \leq \sqrt{x} \right\} \right.$라 하면 $D$의 원소 중 $x$좌표와 $y$좌표가 모두 정수인 점을 다음과 같은 $4$개의 집합으로 분류할 수 있다. $S _{1} = \left\{ ( x , y ) \left| x \right. \right.$, $y$는 홀수$$ $S _{2} = \left\{ ( x , y ) \left| x \right. \right.$는 홀수, $y$는 짝수 또는 $0 \}$ $S _{3} = \left\{ ( x , y ) \left| x \right. \right.$는 짝수 또는 $0$, $y$는 홀수$$ $S _{4} = \left\{ ( x , y ) \left| x \right. \right.$, $y$는 짝수 또는 $0 \}$ 서로 다른 두 점의 중점의 $x$좌표와 $y$좌표가 모두 정수이기 위해서는 위의 $4$개의 집합 중 하나에서 서로 다른 두 원소를 선택해야 한다.

$\displaystyle y = \sqrt{x}$

$f ( 2 ) = 1$, $f ( 3 ) = 3$, $f ( 4 ) = 9$, $\cdots$ $f ( 9 )$를 구하면 (ⅰ) 집합 $S _{1}$에서 선택하는 경우 $( 1 , 1 )$, $( 3 , 1 )$, $( 5 , 1 )$, $( 7 , 1 )$, $( 9 , 1 )$, $( 9 , 3 )$ 중 서로 다른 두 점을 선택해야 하므로 ${} _{6} \mathrm{C} \mathit{_{2}} = 15$ (ⅱ) 집합 $S _{2}$에서 선택하는 경우 $( 1 , 0 )$, $( 3 , 0 )$, $( 5 , 0 )$, $( 5 , 2 )$, $( 7 , 0 )$, $( 7 , 2 )$, $( 9 , 0 )$, $( 9 , 2 )$ 중 서로 다른 두 점을 선택해야 하므로 ${} _{8} \mathrm{C} \mathit{\mathrm{_{2}}} = 28$ (ⅲ) 집합 $S _{3}$에서 선택하는 경우 $( 2 , 1 )$, $( 4 , 1 )$, $( 6 , 1 )$, $( 8 , 1 )$ 중 서로 다른 두 점을 선택해야 하므로 ${} _{4} \mathrm{C} \mathit{\mathrm{_{2}}} = 6$ (ⅳ) 집합 $S _{4}$에서 선택하는 경우 $( 0 , 0 )$, $( 2 , 0 )$, $( 4 , 0 )$, $( 4 , 2 )$, $( 6 , 0 )$, $( 6 , 2 )$, $( 8 , 0 )$, $( 8 , 2 )$ 중 서로 다른 두 점을 선택해야 하므로 ${} _{8} \mathrm{C} \mathit{_{2}} = 28$ (ⅰ), (ⅱ), (ⅲ), (ⅳ) 에 의하여 $f ( 9 ) = 15 + 28 + 6 + 28 = 77$ 같은 방법으로 $f ( 10 ) = _{6} \mathrm{C} \mathit{\mathrm{_{2}}} + _{8} \mathrm{C} \mathit{\mathrm{_{2}}} + _{6} \mathrm{C} \mathit{\mathrm{_{2}}} + _{10} \mathrm{C} \mathit{\mathrm{_{2}}} = 103$ $f ( n ) < f ( n + 1 )$이므로 $n$의 최댓값은 $9$ (참고) $2$이상의 자연수 $n$에 대하여 각 집합의 원소의 개수는 다음과 같다.

따라서 $f ( n )$은 다음과 같다. $f ( 2 ) = _{2} \mathrm{C} _{2} = 1$ $f ( 3 ) = _{2} \mathrm{C} _{2} + _{2} C _{2} + _{2} C _{2} = 3$ $f ( 4 ) = _{2} \mathrm{C} _{2} + _{2} C _{2} + _{2} C _{2} + _{4} C _{2} = 9$ $f ( 5 ) = _{3} \mathrm{C} _{2} + _{4} C _{2} + _{2} C _{2} + _{4} C _{2} = 16$ $f ( 6 ) = _{3} \mathrm{C} _{2} + _{4} C _{2} + _{3} C _{2} + _{6} C _{2} = 27$ $f ( 7 ) = _{4} \mathrm{C} _{2} + _{6} C _{2} + _{3} C _{2} + _{6} C _{2} = 39$ $f ( 8 ) = _{4} \mathrm{C} _{2} + _{6} C _{2} + _{4} C _{2} + _{8} C _{2} = 55$ $f ( 9 ) = _{6} \mathrm{C} _{2} + _{8} C _{2} + _{4} C _{2} + _{8} C _{2} = 77$ $f ( 10 ) = _{6} \mathrm{C} _{2} + _{8} C _{2} + _{6} C _{2} + _{10} C _{2} = 103$