이 문제는 흥미로운 수학적 퍼즐입니다. 결론부터 말씀드리면, 101명과 같은 홀수 명의 총잡이가 있을 때 모든 총잡이가 죽는 것은 불가능합니다. 따라서 모든 총잡이가 죽기 위한 배치는 존재하지 않습니다.
그 이유는 다음과 같습니다.
총잡이와 총격 관계를 그래프로 모델링:
각 총잡이를 점(node)으로 생각합니다.
총잡이 A가 가장 가까운 총잡이 B를 쏜다면, A에서 B로 향하는 화살표(directed edge)를 그립니다.
문제의 조건에 따라, 각 총잡이는 정확히 한 명에게 총을 쏘므로, 모든 점(총잡이)은 정확히 하나의 나가는 화살표(outgoing edge)를 갖습니다.
모든 총잡이가 죽는다는 조건:
모든 총잡이가 죽으려면, 모든 총잡이는 다른 누군가로부터 총을 맞아야 합니다.
그래프 관점에서 이는 모든 점(총잡이)이 적어도 하나의 들어오는 화살표(incoming edge)를 가져야 함을 의미합니다.
그래프의 구조:
모든 점이 나가는 화살표를 하나만 갖고 (out-degree = 1), 들어오는 화살표를 하나 이상 갖는 (in-degree ≥ 1) 그래프를 생각해 봅시다.
그래프 전체에서 나가는 화살표의 총 개수와 들어오는 화살표의 총 개수는 항상 같습니다. (총 N = 101개)
모든 점의 out-degree가 1이므로 나가는 화살표의 총 개수는 N입니다.
모든 점의 in-degree가 1 이상이면, 들어오는 화살표의 총 개수는 N 이상입니다.
따라서 모든 점의 in-degree는 정확히 1이어야 합니다.
모든 점의 in-degree와 out-degree가 정확히 1인 그래프는 반드시 서로소인 순환(disjoint cycles)들의 합집합 형태가 됩니다.
순환(Cycle)의 길이:
길이 2인 순환: A -> B 이고 B -> A 인 경우입니다. 이는 A와 B가 서로에게 가장 가까운 총잡이인 '상호 최근접 이웃(mutual nearest neighbors)' 쌍을 의미합니다. 이 경우 A와 B는 서로를 쏘아 죽입니다.
길이 3 이상인 순환: P1 -> P2 -> ... -> Pk -> P1 (k ≥ 3) 형태의 순환이 가능할까요?
P1이 P2를 쏜다는 것은 d(P1, P2) < d(P1, Pk) 임을 의미합니다. (P1에게는 P2가 Pk보다 가깝다)
P2가 P3를 쏜다는 것은 d(P2, P3) < d(P2, P1) 임을 의미합니다. (P2에게는 P3가 P1보다 가깝다)
...
Pk가 P1을 쏜다는 것은 d(Pk, P1) < d(Pk, Pk-1) 임을 의미합니다. (Pk에게는 P1이 Pk-1보다 가깝다)
이 부등식들을 모두 더하면:
d(P1, P2) + d(P2, P3) + ... + d(Pk, P1) < d(P1, Pk) + d(P2, P1) + ... + d(Pk, Pk-1)좌변은 순환 경로를 따라가는 거리의 합입니다. 우변은 순환 경로를 역방향으로 따라가는 거리의 합입니다. 거리 함수는 대칭적이므로 (d(X, Y) = d(Y, X)), 좌변과 우변은 정확히 같은 값이어야 합니다.
하지만 부등식은 좌변이 우변보다 '작다'고 말하므로 모순이 발생합니다.
따라서 길이가 3 이상인 순환은 존재할 수 없습니다.
최종 결론:
모든 총잡이가 죽으려면 그래프는 서로소인 순환들의 합집합이어야 합니다.
순환의 길이는 3 이상일 수 없으므로, 모든 순환은 반드시 길이가 2여야 합니다.
즉, 모든 총잡이는 서로를 쏘는 쌍(pair)으로 존재해야 합니다.
이는 총 총잡이의 수(N)가 짝수여야만 가능하다는 것을 의미합니다.
문제에서는 총잡이가 N = 101명 (홀수)입니다. 홀수 명의 총잡이를 모두 쌍으로 묶는 것은 불가능합니다.
따라서, 101명의 총잡이가 문제의 규칙에 따라 서로 총을 쏠 때, 모든 총잡이가 죽는 배치는 존재하지 않습니다. 최소한 한 명은 반드시 살아남게 됩니다.
알못이라 맞는 풀이인진 몰루
어려운 문제 가져와서 ai 한계론 증명하려는 애들은... 본인의 존재가치를 어려운 문제로 치환해서 증명하려는 노력 같아서 뭔가 안타까움..
이건 맞음~~