한 날짜의 기록에 01:10, 01:20이 이 순서로 남았다. 시계가 그날 한 번, 02:00에서 01:00으로 돌아갔다면 두 사건 사이에 실제로는 몇 분이 지났을까? 기록에는 되돌리기 전인지 뒤인지 표시가 없다. 10분과 70분 중 어느 하나를 정할 수 있을까?
실제 도시의 시간 규칙 대신, 시계가 한 번만 되돌아가는 정확한 자체 모형을 정한다. J,τ,D는 분 단위의 수이며 0<J<τ<D다. 시작부터 실제로 흐른 시간을 t라 하고 0≤t<D+J로 제한한다. 표시 시각 w(t)는 다음과 같다. 시계가 뒤로 움직여도 실제 시간 t는 계속 증가한다.
m≥2개의 사건이 실제 시간순으로 일어났다는 정보는 남아 있다. 남은 표시 값은 x₁,…,xₘ이며 각 값은 0 이상 D 미만이다. 실제 사건 시각은 t₁<…<tₘ를 만족해야 한다. 표시 값을 크기순으로 다시 정렬하지 않는다. 반올림·시계 오차·날짜 넘어감·두 번째 되돌림은 없다.
임의의 기록에서 가능한 실제 시각 목록을 전부 구하라. 양립 여부, 전체 목록의 개수, 첫 사건부터 마지막 사건까지의 경과 시간 집합을 나누어 답한다. 모든 사건 시각이 정해지지 않아도 경과 시간 하나는 정해질 수 있는지 확인하라.
처음 예는 J=60,τ=120,D=1440이고 표시 값은 70,80이다. 두 사건이 모두 되돌리기 전이면 실제 시각은 70,80이다. 둘 다 뒤면 130,140이다. 첫째만 전이면 70,140이다. 첫째가 뒤이고 둘째가 전인 경우는 실제 순서와 맞지 않는다. 가능한 목록은 세 개지만 경과 시간은 10분 또는 70분, 두 값이다.
일반 기록도 각 자리에서 따로 전·후를 고르는 2ᵐ가지 문제로 보지 않는다. 실제 시간순 목록에서는 되돌리기 전 사건이 모두 앞에 있고, 뒤 사건은 모두 뒤에 있다. 전 사건의 개수를 k라 하면 전체 목록은 다음 한 식으로 정해진다.
k=0이면 모두 뒤, k=m이면 모두 전이다. 서로 다른 허용 k는 적어도 한 사건의 실제 시각을 J만큼 바꾸므로 서로 다른 전체 목록을 만든다. 이제 어느 k가 허용되는지만 검사하면 된다.
먼저 표시 값도 x₁<…<xₘ으로 엄격히 증가한다고 하자. A는 xᵢ<τ−J인 값의 개수, B는 xᵢ<τ인 값의 개수로 정한다. 전 사건은 표시도 τ보다 작아야 하므로 k≤B다. 뒤 사건은 표시가 τ−J 이상이어야 하므로 τ−J보다 작은 A개는 반드시 전 사건, 즉 k≥A다.
이 조건은 충분하다. 각 구간 안에서는 원래 표시가 엄격히 증가하며, 경계가 있으면 xₖ<xₖ₊₁<xₖ₊₁+J라 실제 시간도 증가한다. 전·후의 영역 조건도 모두 만족한다. 0≤A≤B≤m이므로 증가하는 표시 목록은 항상 적어도 한 실제 목록을 갖는다. 등호 xᵢ=τ−J는 뒤에서 허용되고, xᵢ=τ는 전에서 허용되지 않는다는 점을 개수의 엄격한 부등식에 남긴다.
δ=xₘ−x₁이라 하자. 첫째와 마지막이 같은 쪽이면 경과 시간은 δ다. 그 사이에 되돌림을 한 번 포함하면 δ+J다.
따라서 [A,B] 안에 끝값 0 또는 m이 있으면 δ를, 내부 정수가 있으면 δ+J를 답의 집합에 넣는다. 둘 다 있으면 두 값, 한 종류만 있으면 한 값이다. 목록 개수와 경과 시간 개수는 같은 질문이 아니다.
J=60,τ=120에서 표시가 30,70,80,130이면 A=1,B=3이므로 k=1,2,3이 모두 가능하다. 전체 실제 목록은 (30,130,140,190), (30,70,140,190), (30,70,80,190)이다. 중간 사건 시각은 달라도 모든 목록의 처음과 끝은 30,190이므로 경과 시간은 160분 하나로 정해진다.
표시가 증가하지 않는 자리도 있을 수 있다. 여기서는 xⱼ≥xⱼ₊₁인 자리를 ‘비증가 자리’라 부른다. 같은 시각이 다시 적힌 등호도 포함한다. 각 전·후 구간 안에서는 표시가 실제 시간과 같은 만큼 증가하므로, 비증가 자리는 전·후 경계를 가로지를 때에만 가능하다. 그런 자리가 두 개 이상이면 하나의 경계로 모두 설명할 수 없어 불가능하다.
비증가 자리가 정확히 하나, j라고 하자. 다른 모든 이웃 값은 엄격히 증가한다. 유일하게 가능한 경계는 k=j이며 다음 두 조건을 모두 만족할 때에만 실제 목록이 존재한다.
앞쪽의 가장 큰 값이 xⱼ, 뒤쪽의 가장 작은 값이 xⱼ₊₁이므로 두 영역 조건을 한 번씩 검사한 것이다. 또한 xⱼ<τ≤xⱼ₊₁+J라 경계에서 실제 시간의 엄격한 증가도 성립한다. 따라서 필요조건만 적은 것이 아니라 충분성까지 확인했다. 허용되면 전체 목록은 유일하고 경과 시간은 xₘ−x₁+J다. 두 조건 중 하나라도 어기면 실제 목록은 없다.
예에서 표시 80,70,90은 실제 (80,130,150)으로만 돌아와 경과 시간 70분이다. 표시 80,80도 실제 (80,140)으로 유일하게 설명되므로 경과 시간은 60분이다. 같은 표시가 두 사건이 동시에 일어났다는 뜻은 아니다. 반면 80,70,60은 비증가 자리가 두 개라 지금의 한 번 되돌림 모형에서 불가능하다. 표시가 내려간 양이 J와 같거나 더 큰 한 번의 하락도 영역 조건에 맞지 않으므로, 하락 한 개라는 사실만 검사해서는 부족하다.
교사는 ‘기록이 가능한가’, ‘실제 시각 목록이 하나인가’, ‘경과 시간이 하나인가’를 세 줄로 쓰게 한다. 표시를 정렬하면 원래 남아 있던 사건 순서까지 지워 버린다. 제공 교재의 함수·정의역·일대일함수는 한 실제 시각이 표시 하나로 가는 것과 표시에서 실제 시각 하나로 되돌아갈 수 있는 것을 구별하는 기초다. 한 경계의 모든 복원 목록 분류는 이 글의 자체 조건과 증명이다.
착안: National Research Council Canada, Time zones and daylight saving time의 시계를 한 시간 뒤로 돌리는 설명. 특정 지역의 현재 법·날짜·예외나 실제 로그를 판정한 글이 아니다. 임의 J,τ,D와 정확한 사건 기록, 가능한 전체 목록과 경과 시간 분류는 자체 교육용이며 원문 지도·시간대 표·사진·문장 순서를 옮기지 않았다.