티스토리 뷰

수학/이산수학

그들 사이의 거리

leejseo 2017. 9. 18. 17:25

문제. 평면 상에 놓인 $n$개의 점들로 구성된 집합 $A$가 있다. 다음을 증명하여라.

$$ | \left \{ (a, b) \in A^2 : d(a, b) = 1 \right \} | \leq O(n^{3/2}) $$


풀이.

각각의 $a \in A$에 대하여 $a$로 부터 거리가 1인 점의 수를 $f(a)$로 정의하자. 그러면, 평면상에서 (서로 다른 두 점으로 부터) 거리가 모두 1인 점의 수가 많아야 2개라는 사실에 착안하여 다음의 부등식을 얻을 수 있다.

$$ \sum_{a \in A} {f(a) \choose 2} \leq {n \choose 2} $$

따라서,

$$ \sum_{a \in A} f(a)^2 \leq n(n-1) + \sum_{a \in A} f(a)$$

를 얻게 되고, 코시-슈바르츠 부등식을 적용하여

$$ (\sum_{a \in A} f(a))^2 \leq n \sum_{a \in A} f(a)^2 \leq n^2(n-1) + n \sum_{a \in A} f(a) $$

를 얻는다. 따라서, 다음이 성립한다.

$$ | \left \{ (a, b) \in A^2 : d(a, b) = 1 \right \} | \leq O(n^{3/2}) $$


Comment. 이 문제의 경우 Relation을 정의하면 조금 더 아이디어를 떠올리기 좋다.

'수학 > 이산수학' 카테고리의 다른 글

고정된 크기의 클릭의 수  (0) 2018.04.11
Projective Plane의 Blocking Set의 크기  (0) 2018.02.03
2N개의 점들  (0) 2018.01.01
그들 사이의 거리  (0) 2017.09.18
Erdős–Ko–Rado 정리  (0) 2017.07.29
간단한 poset을 이용하는 문제  (0) 2017.07.27
댓글
댓글쓰기 폼