문제1 https://arca.live/b/math/77270761 기하 / 최단경로
난이도: ★ ★ ★ ☆ ☆
문제2 https://arca.live/b/math/77332999 조합론적 기하
난이도: ★ ★ ★ ★ ☆
문제3 https://arca.live/b/math/77413458 유향그래프
난이도: ★ ★ ☆ ☆ ☆
문제4 https://arca.live/b/math/77481685 게임이론 / imo 기출
난이도: ★ ★ ★ ☆ ☆
문제1 풀이: https://arca.live/b/math/77332918
문제2 풀이
n=1, 2, 3, 4: 각각 0, 1, 3, 6이다.
n >= 5
점 전체의 집합을 X라 하자.
n개의 점 중 일부로 이루어져 있고, 모든 점을 포함하는 볼록포함체를 생각하고, 이 볼록포함체를 이루는 점의 집합을 L1,
X - L1에서 다시 볼록포함체를 만들어 이를 이루는 점의 집합을 L2라 하고,
L3 = X - L1 - L2라 하자.
n(L1) = x, n(L2) = y라 하고, "캐르릉"의 개수를 집합별로 counting 할것이다.
L2 - L2, L2 - L3, L3 - L3사이에 "캐르릉"이 존재할 경우, "캐르릉"을 만족하게 하는 직선은 L1으로 이루어진 다각형와 닿지 않아야 하는데, 이럴 경우 두 점만 분리되지 않으므로 모순. 즉 가능한 경우는 L1 - L1, L1 - L2, L1 - L3만 있다.
i) L1 - L3이 가능하다고 가정하자.
주황색 직선이 L1 - L3의 "캐르릉"을 만족하게 한다고 가정하자.
이때 주황색 선 위에 L2의 원소가 있으면 안되고, 즉 L2는 X - L1을 제외한 모든 점을 포함하는 볼록다면체를 이룬다는 가정에 모순이므로 불가능하다.
즉 L1 - L2, L1 - L1만 가능하고, 우리는 최댓값을 구하므로 n(L3) = 0, y = n-x라 해도 무방하다.
ii) L1 - L1 : 자명히 x개이다.
iii) L1 - L2: 의 개수의 최댓값을 증명하기 전 우리는 다음의 보조정리를 증명하고 갈 것이다.
(lemma 1) 만약 어떤 L2의 원소가 두 개의 L1의 원소와 "캐르릉"을 이룬다면, 이 두 L1의 원소는 연속하다.
증명: 어떤 L1의 원소에 대해 L2의 원소와 "캐르릉"을 이루는 경우, L2의 원소는 파란색 점선 위에 있는 삼각형 내부에 있어야 한다.
만약 그렇지 않다면, 이러한 L2의 원소와 파란색 점을 이은 선분은 파란색 점선과 만나므로 어떻게 해도 "캐르릉"을 이루게 직선을 그을 수 없다.
만약 연속하지 않은 L1의 두 원소가 하나의 L2의 원소와 "캐르릉"을 이룬다면, 저러한 삼각형의 공통 영역이 없으므로 모순이다.
lemma 1에 의해, 자명히 어떤 L2의 원소에 대해 최대 두 개의 L1의 원소와만 "캐르릉"을 이룬다는 것을 알 수 있다.
L1의 원소를 A1, A2.... Ax라 하고, Ak, Ak+1과 "캐르릉"을 이루는 L2의 원소를 Bk라 하자.
(lemma 2) Bk는 두개 이상 존재할 수 없다.
증명:
두 A와 두 B는 (AAB) 사이 B가 존재하거나 볼록4각형을 이룰 수있다.
(1) 볼록사각형인 경우: 두 대각선이 "캐르릉"이 못되므로 모순 (그림의 오른쪽)
(2) (AAB) 사이 B 존재: 보라색 + 빨간색 영역 중 한 곳에 또다른 A가 존재해야 하는데, 보라색 영역에 존재할 경우 초록색으로 동그라미친 두 (A, B)가 "캐르릉"을 이룰 수 없으므로 빨간색 영역에 존재해야 한다. 이때 빨간색 영역의 또다른 A 때문에 하늘색으로 연결된 선분이 "캐르릉"이 아니므로 모순 (그림의 왼쪽)
즉, Bk는 하나로 일정하며, 이제 경우를 나누어 최대 개수를 구하자.
(1) x >= y인 경우, 모든 L2의 원소가 B가 될 수 있으므로 2y개이다.
(2) x < y인 경우, x개의 L2의 원소만 B가 되고, 나머지 L2의 원소는 하나의 L1의 원소와만 "캐르릉"을 이루므로
2x + (y-x) = x + y = n
즉, 최대 개수는
n = 2k일때 3k
n = 2k +1일때 3k + 1 이고. 실례는 다음과 같다.
문제3 풀이
i) p >= 8
8마리의 캬루를 k1, k2... k8이라 하자.
(k1, k2, k3), (k2, k4, k6), (k1, k6, k7), (k3, k5, k7), (k4, k7, k8), (k2, k5, k8), (k3, k6, k8), (k1, k4, k5) 끼리 3-cycle을 이룬다면
최소 8번 이상의 교환이 필요하다.
ii) p <= 8
(시작하기 전, a에서 b로 방향이 가해졌다면 a는 b를 이겼음을 뜻한다)
먼저, 완전 유향 그래프에서 cycle이 없다는 것과 모든 점의 출차수가 다르다는 것은 동치임을 증명하자.
q->p: 모든 점의 출차수가 다르다면, 점이 n개인 경우 출차수의 개수를 점의 번호로 지정할 수 있다, 즉 점의 번호는 0~n-1이 된다.
n-1번 점은 모두를 이겼고, n-2번 점은 n-1번에게만 지고.... 반복하면 수학적 귀납법으로 i > j일때 i가 j를 이김을 알 수 있다.
cycle이 존재한다는 것은 i > j > i라는 뜻이므로 모순.
p->q: 만약 출차수가 같은 두 점 v, w가 있다 가정하고, v는 w를 이겼다 가정하자.
w가 이긴 xi는 반드시 v에게 져야 하므로(3 cycle이 없어야 함) v의 승리 횟수는 반드시 w보다 많다.
즉, 위의 증명에 의해 각 캬루는 (7, 6, 5, 4, 3, 2, 1, 0)번 이긴 것으로 조작되어야 한다.
처음에 각 캬루가 (a1, a2, a3, a4, a5, a6, a7, a8)번 이겼다 하자. (i > j면 ai >= aj)
H = a1 + ... + a4, L = a5 + ... + a8이라 하자.
모든 캬루가 이긴 횟수는 28번이고, a4의 값에 따라 경우를 분류하자.
i) a4 >= 4: H >=16, 즉 L <= 12
ii) a4 <= 3: L <= 12, 즉 H>= 16
화살표를 1번 바꾸면 H의 값은 최대 1 늘어나므로
16에서 22가 되므로 6번의 조작을 가하고, a1~a4, a5~a8 내부에서 1번의 조작만 가하면 조건을 만족하게 할 수 있다.(이는 자명하므로 여러분이 해보세요)
문제4 풀이
본 문제는 imo 2018 4번 문제이며, 상당히 쉽고 재밌어서 가져와봤습니다.
문제2 풀이를 쓰는데 모든 에너지를 쓴 캬루는 aops에서 캡쳐본을 가져왔습니다.
이로서 모든 풀이를 마칩니다.
