20101106 - 정삼각형의 개수

전에 실은 모저의 원 문제에 대하여 수업 중에 언급하다보니 그 풀이에 대하여 고민하던 것이 생각이 났다. 그러던 중 송영준 선생이 그 풀이를 비교적 간단하게 해결한 것을 알게 되었다. 그 후 책을 보다보니 그에 대한 다른 접근과 다른 풀이가 나왔다.

<모저의 원 문제; 원 위의 [eqn: n]개의 점을 서로 직선으로 연결할 때 생기는 영역의 최대개수를 구하라.>

이 답이  답; [eqn: pmatrix {n# 0 } +pmatrix {n# 2 } +pmatrix {n# 4 }]    이다.

그런데, <존 콘웨이, 리처드 가이, 수의 바이블(The Book of Numbers),  한승, 2003>에는 다른 풀이가 소개되어 있다.

[eqn: pmatrix {n-1 # 0 } +pmatrix {n-1# 1 } +pmatrix {n-1# 2 } +pmatrix {n-1# 3 } +pmatrix {n-1# 4 }]

물론 계산하면 결과는 같다. 접근 방법이 달라서 그렇지.

이 책에서 정수론의 잉여류를 그림으로 이해하기 쉽게 설명해 놓았다. 10년 전 쯤 원서를 보고 새로운 접근에 자극 받았던 기억이 난다. 영어로 써져 있어 다른 것은 잊어버리고 있었는데, 번역본이 나와 보다 쉽게 읽을 수 있어 좋았다.

책을 계속 읽다 보니 재미있는 문제가 눈이 띤다.

그것은 삼각형의 개수를 묻는 문제이다.

<길이가 [eqn: n]인 정삼각형을 길이가 1인 정삼각형으로 잘랐을 때,

생기는 정삼각형의 개수 [eqn: a_n]을 구하라.>

[eqn: sum _{ } ^{ }]를 써야 하니 중학생에게는 어렵겠군요. 중학생은  [eqn: a_10]을 구하면 될 것이다.

<탐구> 먼저  [eqn: a_10]의 경우를 생각하자.

길이가 1인 바른 정삼각형의 개수는  [eqn: sum _{k=1 } ^{10 } k], 길이가 1인 역삼각형의 개수는  [eqn: sum _{k=1 } ^{9 } k]

길이가 2인 바른 정삼각형의 개수는  [eqn: sum _{k=1 } ^{9 } k], 길이가 2인 역삼각형의 개수는  [eqn: sum _{k=1 } ^{7 } k]

길이가 3인 바른 정삼각형의 개수는  [eqn: sum _{k=1 } ^{8 } k], 길이가 3인 역삼각형의 개수는  [eqn: sum _{k=1 } ^{5 } k]

길이가 4인 바른 정삼각형의 개수는  [eqn: sum _{k=1 } ^{7 } k], 길이가 4인 역삼각형의 개수는  [eqn: sum _{k=1 } ^{3 } k]

길이가 5인 바른 정삼각형의 개수는  [eqn: sum _{k=1 } ^{6 } k], 길이가 5인 역삼각형의 개수는  [eqn: sum _{k=1 } ^{1 } k =1]

길이가 6인 바른 정삼각형의 개수는  [eqn: sum _{k=1 } ^{5 } k],

길이가 7인 바른 정삼각형의 개수는  [eqn: sum _{k=1 } ^{4 } k] [eqn: cdots cdots]

이와 같이 계속하면 [eqn: n=10]일 때,  [eqn: sum _{l=1 } ^{ n } ( sum _{k=1 } ^{l }k ) + sum _{l=1 } ^{ n over 2 } ( sum _{k=1 } ^{2l -1 } k )]

이제  [eqn: a_9]의 경우를 생각하자.

길이가 1인 바른 정삼각형의 개수는 [eqn: sum _{k=1 } ^{9 } k] , 길이가 1인 역삼각형의 개수는  [eqn: sum _{k=1 } ^{8 } k]

길이가 2인 바른 정삼각형의 개수는 [eqn: sum _{k=1 } ^{8 } k] , 길이가 2인 역삼각형의 개수는  [eqn: sum _{k=1 } ^{6 } k]

길이가 3인 바른 정삼각형의 개수는 [eqn: sum _{k=1 } ^{7 } k] , 길이가 3인 역삼각형의 개수는  [eqn: sum _{k=1 } ^{4 } k]

길이가 4인 바른 정삼각형의 개수는 [eqn: sum _{k=1 } ^{6 } k] , 길이가 4인 역삼각형의 개수는  [eqn: sum _{k=1 } ^{2 } k]

길이가 5인 바른 정삼각형의 개수는 [eqn: sum _{k=1 } ^{5 } k] ,

길이가 6인 바른 정삼각형의 개수는 [eqn: sum _{k=1 } ^{4 } k] ,

길이가 7인 바른 정삼각형의 개수는  [eqn: sum _{k=1 } ^{43} k] [eqn: cdots cdots]

이와 같이 계속하면 [eqn: n=9]일 때,  [eqn: sum _{l=1 } ^{ n } ( sum _{k=1 } ^{l }k ) + sum _{l=1 } ^{ n-1 over 2 } ( sum _{k=1 } ^{2l } k )]

(풀이1) [eqn: n]이 짝수일 때와 홀수 일 때로 나누어 생각한다.

(ⅰ) [eqn: n]이 짝수일 때

바르게 된 정삼각형의 개수는

[eqn: sum _{l=1 } ^{n } ( sum _{k=1 } ^{l } k ) = { n(n+1)(n+2) } over { 2 cdot 3} = { n(n+1)(n+2) } over 6]

역삼각형의 개수는

[eqn: sum _{l=1 } ^{ n over 2 } ( sum _{k=1 } ^{2l -1 } k ) = sum _{l=1 } ^{ n over 2 } l(2l-1)= { n(n+2)(2n-1) } over { 24}]

이를 더하면

[eqn: { n(n+1)(n+2) } over { 6} + { n(n+2)(2n-1) } over 24 = {n(n+2)(2n+1) } over 8]

(ⅱ) [eqn: n]이 홀수일 때

바르게 된 정삼각형의 개수는

[eqn: sum _{l=1 } ^{n } ( sum _{k=1 } ^{l } k ) = { n(n+1)(n+2) } over { 2 cdot 3} = { n(n+1)(n+2) } over 6]

역삼각형의 개수는

[eqn: sum _{l=1 } ^{ n-1 over 2 } ( sum _{k=1 } ^{2l } k ) = sum _{l=1 } ^{ n-1 over 2 } l(2l+1)= { (n-1)(n+1)(2n+3) } over { 24}]

이를 더하면

[eqn: { n(n+1)(n+2) } over { 6} + { (n-1)(n+1)(2n+3) } over 24 = {(n+1)(2n^2 +3n -1) } over 8]

(풀이2)  계차수열을 이용한다.

[eqn: a_1 =1], [eqn: a_2 = 5], [eqn: a_3 =13], [eqn: a_4 = 27], [eqn: a_5 = 48], [eqn: a_6 = 78], [eqn: a_7 =118], [eqn: a_8 =170], [eqn: a_9 =235], [eqn: cdots cdots]

4,       8,       14,     21,       30,     40,       52,        65,   [eqn: cdots cdots]

4,	6,	7,	9,	10,	12,	13, [eqn: cdots cdots]

2,	1,   2,	1,	2,	1, [eqn: cdots cdots]

3번째 계차에서 2와 1이 교대로 나타난다.

이제 홀수 번째, 수열을 기준으로 생각해보자.

[eqn: a_1 =1],  [eqn: a_3 =13],  [eqn: a_5 = 48],  [eqn: a_7 =118],  [eqn: a_9 =235], [eqn: cdots cdots]

12,	35,	70,	117, [eqn: cdots cdots]

23,     35,    47,  [eqn: cdots cdots]  여기서 [eqn: d_n = 11+ 12n]

12,	35,	70,	117, [eqn: cdots cdots]에서

[eqn: c_n = 12+ sum _{ k=1} ^{n-1 }( 11+ 12k) = 12+ 11(n-1)+ 12 cdot {n(n-1) over 2 }= 6n^2 +5n+1]

이제 [eqn: b_n = 1+ sum _{ k=1} ^{n-1 }( 6k^2 +5k+1 ) = n over 2 (4n^2 -n-1) = a_2n-1]

[eqn: 2n-1=k]에서 [eqn: n = 1 over 2 (k+1)]를 대입하면

[eqn: a_k = k+1 over 4 left{ 4 ( k+1 over 2 )^2 - ( k+1 over 2 ) -1 right}= 1 over 8 (k+1)(2k^2 +3k -1)]