거위, 거위, 오리들? timer 20s memory 1024MB

첫 번째 국제 거위 컨퍼런스가 막 끝났다. 행복한 행사여야 했지만, 씁쓸함이 남았다. 주최 측이 오리들의 침투 계획이 자세히 적힌 문서를 발견했기 때문이다. 이제 그들은 참석자들 중 침투한 무리를 찾아내려 한다.

발견된 문서에는 정수 3개로 이루어진 \mathbf{M}개의 목록 (\mathbf{X_i}, \mathbf{Y_i}, \mathbf{C_i})가 있었다. 이는 컨퍼런스 시작 후 정확히 \mathbf{C_i}초에 오리들이 점 (\mathbf{X_i}, \mathbf{Y_i})에서 만난다는 뜻이다. 이 점은 컨퍼런스 바닥의 중심에서 동쪽으로 \mathbf{X_i}미터, 북쪽으로 \mathbf{Y_i}미터 떨어져 있다. 각 거위는 그 시각 그 장소에 있었을 수도 있고 아닐 수도 있지만, 모든 오리는 확실히 그 시각 그 장소에 있었다.

오리와 거위는 모두 최대 속도가 초당 1미터이다. 즉, 어떤 참석자가 시간 t에 점 (x, y)에 있었다면, {\Delta_{x}}^2 + {\Delta_{y}}^2 \le {\Delta_{t}}^2를 만족하는 한 시간 t + \Delta_{t}까지 점 (x + \Delta_{x}, y + \Delta_{y})로 갈 수 있다. 각 참석자의 시간 0에서의 위치는, 서로 독립적으로, 임의의 점이 될 수 있다.

문서가 발견된 뒤, 그들은 오리들을 찾아내기 위해 질의응답 시간을 가졌다. 그 시간 동안 참석자들은 차례대로 진술을 하나씩 했다. 발표된 순서대로 j번째 진술은 참석자 \mathbf{A_j}가 했고, 자신과 참석자 \mathbf{B_j}가 모두 컨퍼런스 시작 후 정확히 \mathbf{D_j}초에 점 (\mathbf{U_j}, \mathbf{V_j})에 있었다고 주장했다. 진술에 등장하는 점은 오리 모임이 열렸던 점일 수도 있고 아닐 수도 있다.

거위의 진술은 항상 참이지만, 오리는 거짓말을 할 수 있다. 또한 오리들은 누가 오리이고 누가 거위인지 알고 있다. 쉽게 들키지 않기 위해, 오리들은 이전에 거위들이 했던 모든 진술과 양립할 수 있는 진술만 한다. 거위가 한 진술들은 모든 오리가 모든 오리 모임에 참석했다는 사실과도 양립함에 유의하라.

주어진 정보만으로 모든 오리를 확정할 수 없을 수도 있다. 하지만 오리의 최소 인원수라도 알 수 있다면, 오리 활동 수준에 대한 하한을 얻을 수 있다. 적어도 한 마리 이상의 오리가 있었음은 보장된다. 가능한 가설들 중 오리의 최소 인원수를 구하라.

형식적으로, 가설 H는 모든 참석자를 오리의 집합(이를 H-오리라 부른다)과 거위의 집합(이를 H-거위라 부른다)으로 나눈 분할이다. H가 진술 집합 S와 일관적(consistent)이라는 것은, 각 참석자마다 초당 1미터 이하로 움직이는 어떤 경로가 존재하여 다음을 모두 만족하는 것을 뜻한다:

• 모든 H-오리는 모든 오리 모임에 참석했고,
• S 안의 각 진술이 시간 T에 점 P에서 A가 B를 보았다고 주장한다면, A와 B의 경로는 모두 시간 T에 점 P를 지난다.

가설 H는 진술 집합 S에 대해 다음을 모두 만족할 때 가능(feasible)하다고 한다:

• H-오리 집합이 비어 있지 않다 (즉, 적어도 한 마리 이상의 오리가 있었다),
• S 중에서 H-거위가 한 진술들의 부분집합은 H와 일관적이다 (즉, 거위의 진술은 항상 참이다), 그리고
• H-오리가 한 각 진술 s \in S에 대해, P \subseteq S를 s보다 먼저 나온 H-거위의 진술들의 집합이라고 하자. 그러면 어떤 가설 H' (이는 H와 같을 수도 있고 아닐 수도 있다)가 존재하여 \{ s \} \cup P가 H'와 일관적이다 (즉, 오리는 이전에 나온 거위의 진술을 모순시키지 않는다).

모든 참석자를 H-오리로 두는 가설 H는 항상 가능함에 유의하라.

가능한 모든 가설 H에 대해 H-오리의 크기의 최솟값을 구하라.