3번 풀이)

평면 상에 배열되어있는 [eqn: n]개 점들의 집합을 [eqn: P]라고 하자. 그리고 각각의 점 [eqn: x in P]에 대해 집합 [eqn: P]의 모든 원소를 [eqn: x]를 중심으로 반시계방향으로 [eqn: pi/3] 회전한 점들의 집합을 [eqn: R_x (P)]라 할 때, 다음과 같은 집합 [eqn: A_x = P SMALLINTERR_x (P) RSLANTleft{ x right}]을 정의한다. 그러면 [eqn: |A_x |]는 [eqn: x]가 들어간 정삼각형의 개수라는 사실을 알 수 있고, 이 값을 [eqn: tr(x)]라고 표기하자. 우리는 proof에서 다음을 보일 것이다.

[eqn: FORALL P, Exist w ````` s.t.`````tr(w) leq left[ {n-1}over2 right]]. (단 [eqn: [·]]는 내림함수)

이것이 증명된다면 [eqn: T(n) leq left[ (n-1)^2 over 4 right]]임이 자명하다.

proof)

먼저 [eqn: d(x,y)= rm diam itP]인 [eqn: x,y in P]를 택하자. 그리고 삼각형 [eqn: xyz]가 정삼각형이 되는 점 [eqn: z in P]의 존재 유무에 대해 두 가지 경우로 나누자.

1) [eqn: z]가 존재 하는 경우.

이 때 가정에 의해 [eqn: P]의 모든 원소는 반드시 [eqn: x], [eqn: y], [eqn: z]를 꼭지점으로 하는 볼록삼각형 내부(또는 경계)에 있어야 한다. (그림을 참고하라.)

또한 그림과 같이 영역 [eqn: X], [eqn: Y], [eqn: Z]를 잡으면

[eqn: A_x SUBSET X], [eqn: A_y SUBSET Y], [eqn: A_z subset Z]이므로 [eqn: A_x], [eqn: A_y], [eqn: A_z]는 쌍마다 서로소이다. 따라서

[eqn: tr(x)+tr(y)+tr(z) = |A_x |+|A_y |+|A_z | leq |P|=n]

[eqn: therefore tr(w) leq left[ n over 3 right] leq left[ {n-1}over2 right]]. ([eqn: w]는 [eqn: x], [eqn: y], [eqn: z]중 하나)

2) [eqn: z]가 존재 하지 않는 경우.

다음을 증명하는 것을 목표로 한다. [eqn: |A_x SMALLINTER A_y | leq1]. 그러면

[eqn: tr(x)+tr(y)=|A_x |+|A_y |=|A_x SMALLINTER A_y | + |A_x SMALLUNION A_y | leq 1+ |A_x SMALLUNION A_y | leq 1+ |P/left{x,y right}|=n-1]

[eqn: therefore tr(w) leq left[ {n-1}over2 right]]. ([eqn: w]는 [eqn: x], [eqn: y]중 하나)

가 되어 증명이 끝난다.

귀류법으로, [eqn: |A_x SMALLINTER A_y | geq 2]를 가정하자. 그리고 [eqn: a,`b in A_x SMALLINTER A_y]를 생각하자.

그러면, 자명히, 다음 그림과 같이 [eqn: a'], [eqn: b'], [eqn: a''], [eqn: b'']가 존재하여야 할 것이다.

(단, [eqn: xaa'], [eqn: xbb''], [eqn: ybb'], [eqn: yaa'']는 정삼각형이다.)

이제 선분 [eqn: xy]를 [eqn: b]를 중심으로 [eqn: pi/3]회전시키면 정확히 선분 [eqn: b'b'']와 같아진다. 마찬가지로 [eqn: a]를 중심으로 [eqn: pi/3]회전시키면 선분 [eqn: a'a'']와 같아진다.

그런데 평행사변형 [eqn: a'a''b'b'']를 보면 대각선 [eqn: a''b'']의 길이는 한 변의 길이 [eqn: a'a'']나 [eqn: b'b'']보다 길고, 즉 선분 [eqn: xy]의 길이 [eqn: d(x,y)= rm diam it P]보다 길다. 이것은 가정에 모순이다. 따라서 [eqn: |A_x SMALLINTER A_y | leq1]이다. ■