이것으로 끝난 걸까? 아니다. 이 알고리즘이 끝없이 계속 돌아가지 않는다는 것을 보여줘야 한다. 실제 일 알고리즘은 언젠가는 멈춰야 한다. 알고리즘을 아무리 많이 반복하더라도 만들어질 수 있는 표의 개수에 한계가 있기 때문이다(표에 들어 있는 mn개의 각각의 항목이 가질 수 있는 상태의 수는 두 개뿐이다). 그러므로 모든 원소의 합의 경우의 수도 유한하다. 이 알고리즘에서는 합이 증가하는 순으로 일련의 표들을 만들어내기 때문에 유한한 단계 안에 완료될 수밖에 없다.
위에서 살펴본 두 예에서 모두 다음과 같은 성질을 가지는 어떤 양을 활용했다.
• 정해진 방향으로만 값이 바뀔 수 있다(첫 번째 문제에서는 줄어드는 쪽으로, 두 번째 문제에서는 늘어나는 쪽으로).
• 가질 수 있는 값의 개수가 유한하므로 유한한 단계 안에 완료될 수밖에 없다.
• 최종값에 다다르면 문제 풀이가 끝난다.
이런 양을 일변량(monovariant)이라고 부른다. 하나의 변인에 의해 변하는 양이라는 뜻이다. 적절한 일변량을 찾기는 쉽지 않다. 이런 이유로 일변량과 관련된 퍼즐이 수학 경시대회에서 자주 눈에 띄곤 한다. 위에 있는 두 번째 예제는 1961년 러시아 수학 올림피아드 연습문제로 출제된 문제다.[Win04, p.77] 하지만 반복 향상이 일변량 문제나 간단한 퍼즐에서만 쓰이는 것이라고 할 수는 없다. 전산학 분야에서 가장 중요한 알고리즘 중 하나로 꼽히는 단체법(simplex method)도 이런 접근법을 바탕으로 한다. 이쪽에 관심이 있다면 이 책 후반부에 있는 다른 일변량 퍼즐을 찾아보자.