[문제/풀이] 삼각형 개수의 최댓값 풀이

[익명(118.235)]

저 개수가 왜 최대치인가를 증명하려면,
직선들에 의해 나눠진 모든 선분이
'중복 없이' 삼각형의 변을 구성하는 경우를 생각해보면 됨.

n개의 직선이 있을 때
각 직선은 n-1개의 직선에 의해 n-2개의 선분으로 나뉘므로,
이 경우 삼각형 개수에 대한 상계 (upper bound)로
[n(n - 2)/3]을 얻음. 단, [x]는 x보다 크지 않은 최대 정수.

n = 6, 7, 8, 9를 대입하면 상계로 각각 8, 11, 16, 21을 얻음.

근데 n = 6k, 6k+2 (k는 자연수)일 때는
저 상계만큼의 삼각형을 만드는게 불가능함을 보일 수 있음.
이 증명이 궁금하다면 시간 날 때 추가 풀이 써볼게.

따라서, 더 타이트한 상계는 각각 7, 11, 15, 21이고,
그림에서 저만큼의 개수를 이미 얻었으니
저 상계가 최대치라는게 증명이 됨.

참고로 n = 10일 때는 상계가 26인데, 25개인 경우까지만 발견됨.
아직 26개인 경우를 찾거나,
26개인 경우가 불가능하다고 증명한 사람이 없어서 미해결 문제임.

일반화된 식이 없을 뿐만 아니라
n이 커질수록 삼각형 개수 세기도 어려워서
10뿐만이 아니라 대부분의 n에 대해서 미해결 상태라 보면 됨.