서로 다른 숫자 카드가 왼쪽부터 4,2,3,1 순서로 놓였다. 목표는 1,2,3,4다. A 규칙은 임의의 두 위치를 맞바꾸고, B 규칙은 바로 이웃한 두 위치만 맞바꾼다. 각 규칙의 최소 횟수를 구하라.
역전 수는 앞 카드가 뒤 카드보다 큰 위치 쌍의 개수다.
임의 위치를 바꿀 수 있으면 첫째와 넷째 카드만 맞바꾸어 끝난다. 이미 정렬되어 있지는 않으므로 0회는 안 되고 최소 1회다.
이웃 교환에서는 바꾼 두 카드의 앞뒤 관계 하나만 달라진다. 다른 카드와의 상대 순서는 유지되므로 역전 수가 정확히 1 증가하거나 감소한다. 현재 역전은 (4,2),(4,3),(4,1),(2,1),(3,1)의 다섯 개다.
목표의 역전 수는 0이어서 적어도 5회가 필요하다. 다음은 그 하한을 이루는 실제 조작이다.
횟수의 하한과 그 횟수로 가능한 구성은 둘 다 확인해야 한다. 원문은 숫자값 a,a+1의 위치를 바꾸는 다른 규칙이었다. 현재 문항은 위치가 이웃해야 한다. 교사는 “인접”이 값에 붙는지 위치에 붙는지를 규칙 첫 줄에 적게 한다.
착안 원문: NZMO 2025 Round 1, Problem 5. 위 조건·문항과 해설은 새로 구성했다. 원문의 문항이나 그림을 번역·재사용한 것이 아니다.