일단 문제의 그림처럼 배치하면 교점 n개는 무조건 만들 수 있겠네요. 이것보다 교점을 더 줄이는 걸 목표로 잡읍시다.

같은 간격으로 놓여있다는 조건은 없는거죠...?

만약 n개보다 교점 수가 적어지는 경우가 존재한다면, 그런 모든 경우 중 n이 최소일 때의 임의의 경우를 잡으면 한 칸만 떨어진 두 점이 연결되는 경우가 없음을 증명했습니다.

지금 좀 바빠서 증명은 이따가 올리려고 하는데 우선 사용해주세요.

음... 제가 실력이 안되서 관전만 하다가 차음 글 써봅니다...

아이디어만 좀 끄적여 보자면 파란점 빨간점이 원 위에 일정한 간격으로 있을 때 우리는 정2n각형을 생각할 수 있습니다

이때 정2n각형의 대각선을 그렸을 때, 대각선이 2개 이하로 만나는 교점들을 찾아봐도 좋을 것 같습니다

라는 의견을 조심스럽게 내놓아 봅니다

문제 풀이를 위한 Lemma를 올립니다.

Lemma 1) 점 개수의 1/4개보다 교점 수가 적어지는 경우가 존재한다고 가정하고, 그 중 점 개수가 최소인 때를 골랐을 때, 그 경우에서 한 칸만 떨어진 두 점을 잇는 선분이 존재하지 않는다.

proof) 위 댓글에서 증명

Lemma 2) 점 개수의 1/4개보다 교점 수가 적어지는 경우가 존재한다고 가정하고, 그 중 점 개수가 최소인 때를 골랐을 때, 그 경우에서 인접한 두 점(다른 색의 점) 에서 그은 현은 만나지 않는다.

proof) 점 개수의 1/4개보다 교점 수가 적어지는 경우가 존재한다고 가정하고, 그 중 점 개수가 최소인 때를 고릅니다. 그 경우에서 인접한 두 점에서 그은 현이 만난다고 가정합니다. 두 점 중 빨간 점을 R, 파란 점을 B라 하고, RR', BB'이 각각 빨간 현과 파란 현으로 연결되어 있으며 이들의 교점이 존재한다고 가정합니다. R에서 B 방향으로 원주를 돌 때 B 이후 최초로 만나는 빨간 점을 R1이라 합니다. Lemma 1에 의해 R은 R1과 연결되어 있지 않습니다. 그러므로 R1과 연결된 점 R1'을 잡으면 R, R', R1, R1'은 모두 다른 점입니다.

R과 R1 사이에는 점이 B뿐이므로, R과 R1을 잇는 빨간 현을 그으면 서로 다른 색끼리의 교점이 딱 1개 늘어납니다. 그 뒤, 현 RR', R1R1', RR1을 지우고 현 R'R1'을 긋습니다. R'R1'을 잇는 현과 만나는 모든 파란 현은 양 끝점이 하나는 호 R' R1'(R 반대쪽)에 있고 나머지 하나는 호 R' R R1' 위에 있으므로, R'R1'을 잇는 현과 만나는 모든 파란 현은 R1'R1 또는 RR1 또는 RR'과 만납니다.

또한, 파란 현 BB'는 RR'과 1개, RR1과 1개의 교점을 가집니다. 만약 BB'이 R'R1'과 교점을 갖는다면 B'은 현 RR' 기준으로 B 반대편에 있으며 호 R'R1' 위에 놓이게 되는데, 이때 이것은 R1 또한 현 RR' 기준으로 B 반대편에 있어야 가능합니다. 이런 위치관계에서 B'은 현R1R1' 기준으로도 B 반대편에 놓이게 됩니다. 즉, BB'이 R'R1'과 교점을 갖는다면 R1R1'과도 교점을 갖습니다. 따라서 현 RR', R1R1', RR1을 지우고 현 R'R1'을 긋는 과정에서 교점은 2개 이상 줄어듭니다.

이제 다시 현 RR1을 긋습니다. 이 과정에서 다시 교점이 하나 늘어나며, 이 과정까지 마치고 나면 다시 모든 빨간 점과 파란 점이 현에 의해 두 개씩 연결되어 있는 상황이 됩니다. 전체 과정에서 교점은 2개 늘어나고 2개 이상 줄어들었으므로, 결과적으로 교점의 수는 줄어들었거나 일정합니다. 즉 이 경우도 점 개수의 1/4보다 교점 수가 적어지는 경우이며 여전히 점 개수는 최소입니다. 그런데 이때 인접한 두 점인 R, R1이 연결되었으므로 Lemma 1에 모순입니다.

올린 Lemma의 증명이 모두 맞다는 가정하에 풀이를 올립니다.

먼저 답은 n개가 최소인 것으로 나왔습니다. 구머님께서 위에서 말씀하셨듯 교점의 개수가 n개인 경우가 존재합니다.

원주 위의 두 점 사이의 '거리' 를 두 점 사이의 점의 개수의 최솟값으로 정의합니다. 즉, 한 점에서 출발하여 원주를 한 방향으로 돌아 다른 점까지 가는 방법이 2가지가 있는데, 이 중 더 적은 점을 만난 방법에서 점의 개수로 정의합니다.

점 개수의 1/4개보다 교점 수가 적어지는 경우가 존재한다고 가정하고, 그 중 점 개수가 최소인 때를 고릅니다. 이때 현으로 연결된 두 점 중 그 두 점 사이의 거리가 최소인 두 점을 잡고, A, B라 합니다. 또한, 호 AB 중 더 적거나 같은 개수의 점을 포함하는 호를 잡고, 그 호에서 점 A,B를 제외한 부분을 a라 합니다. a의 임의의 두 점은 A, B보다 점들 사이의 거리가 짧습니다.

이제 a에서 A와 인접한 점을 하나 잡습니다(모든 현으로 연결된 점은 Lemma 1에 의해 세 칸 이상 떨어져 있으므로 이런 점이 존재합니다). 즉, A에서 호 A쪽으로 원주를 돌아 최초로 만나는 점 C를 잡습니다. C는 A와 다른 색이며 A와 인접하므로, Lemma 2에 의해 C와 연결된 현은 현 AB와 만나지 않습니다. 따라서 C와 현을 통해 연결된 점 D는 현 AB를 기준으로 C와 같은 쪽에 있습니다. 즉, C, D는 a 위의 연결된 두 점이며, C와 D 사이의 거리가 A와 B의 거리보다 짧으므로 A, B가 현으로 연결된 두 점 중 두 점 사이의 거리가 최소인 두 점임에 모순입니다.

즉, 교점의 개수가 점 개수의 1/4개보다 적어지는 경우는 존재하지 않고, 교점의 개수의 최솟값은 n입니다.

답 : n개
[증명]

먼저 이 문제를 해결하기 위해 위와 같은 상황을 생각해 봅시다.
빨강 현과 닿지 않으며 파랑 현을 그릴 수 있는 방법이 있을까요?

정답은 위와 같이 연결하는 것입니다.

하지만 위와 같이 연결할 경우 파란 점 사이에 빨강 점이 위치하여야 합니다.
그리고 초록색으로 표시된 곳을 보시면 처음과 같음을 알 수 있습니다.

결국 한 현은 색이 다른 현과 반드시 한점 이상 접한다는 결론을 내일 수 있습니다.
그럼으로 교점은 ((파랑색 현의 개수) + (빨강 현의 개수)) / (한 교점을 지나는 현의 개수) 이상입니다.
이때 파랑 현과 빨강 현의 개수는 각각 n개이고 한 교점을 지나는 현의 개수는 2개임으로 교점은 항상 n개 이상입니다.
하지만 교점이 최소 2n개여도 n + 1개여도 위의 조건을 만족하기 때문에 '어떤 n의 값이든 관계없이 교점을 n개 만드는 배치가 존재한다.'를 증명하여야 합니다.
저는 저는 위에서 나온 방법 대신 응용이 가능한 다른 방법을 생각하여 보았습니다.

제가 생각한 방법은 연속한 점 4개를 1개의 조각으로 보는 방법입니다.
1. 연속한 점들은 4개당 한 덩어리로 생각하고 나눈다.
2. 각 덩어리에서 위와 같이 연결한다.
그럼 어떤 n이든 관계없이 교점이 n개가 나옵니다.

증명에 오류가 있다면 댓글로 지적해 주세요 ^^

[응용]
답 : n * x / 2
저는 위의 문제를 확장하여 색이 x개일 떄의 증명을 해보았습니다.
(각 색갈 점들의 개수는 2n입니다.)

빠른 이해를 위하여 x = 3이라 가정하겠습니다.
먼저 위의 문제처럼 파랑을 무시하고 초록 - 빨강 조합을 생각하여 보겠습니다.

다음과 같은 상황에서 빨강과 초록은 위의 제 풀이와 같이 무조건 한 점에서 만납니다.
이 방식을 빨-파, 초-파 조합에 대입해도 같은 결과가 나옵니다.
빨간색 현 1개는 (x - 1)개의 다른 색갈의 현 과 각각 1개 이상 만나야 합니다.
그럼으로 총 교점의 개수는 (n * x) / 2개 이상입니다.

또한 연속한 점 2x개를 한 덩어리로 잡고 원을 여러 덩어리로 나눈 후 각 덩어리를 위와 같이 연결하면 항상 교점 n * x / 2개를 만들 수 있습니다.

네이스

푼것 같습니다. 대53 처럼 천천히 풀이 올릴게요.

풀?이)

우선 정답은 모두가 예상하셨듯, 빨간 현과 파란 현이 만나는 최소 횟수는 "회" 입니다. 해당 명제를 명제-F 라고 합시다.

명제-F 는 귀납법을 활용하여 증명할 수 있습니다. 구체적으로는, 일 때 명제-F가 성립한다고 가정하고,  일때 명제-F가 성립함을 보이면 됩니다.

-풀?이!-

0) 초기 조건 에서 명제-F가 성립한다.

  자명하게 딱 1회 교차하므로 명제가 성립합니다.

1) 모든  에 대해 명제-F가 성립한다면,  일때 명제-F가 성립한다.

  풀이의 핵심입니다. 증명을 위해 수학적 귀류법을 사용합시다. 즉,

 "일 때, 빨간 현과 파란 현이 만나는 횟수가 보다 작은 현의 배치가 존재한다!"

라고 가정하고, 모순을 찾을 것입니다. 편의상 해당 배치를 가상배치로 합시다.

가상배치에서 빨간 현과 파란 현이 만나는 횟수가 

n <= k-1일 때 문제가 성립한다고 가정하자.(귀납법) 또, 귀류법으로 n=k일 때 빨파 교점 개수가 k보다 작은 배치가 있다고 가정하자. 이때, 그 어느 빨간 현과도 만나지 않는 파란 현이 존재한다. 이 파란 선을 B라고 하자.

(수시로 업데이트됩니다)