**A Hungarian problem.**

Martin Rem returned from his trip to Hungary with the following problem. Let two positive integers `p` and `q` be given.
We start with a bag containing a finite number of integers. When the bag contains some number, `x` say, at least twice,
a move is possible; the move consists of replacing in the bag two occurrences of `x` by `x`+`p` and `x`−`q` respectively.
Show that this game terminates.

When we characterize the contents of the bag by its characteristic function `f` —i.e. for all `x`, `f` (`x`) = the number of
occurrences of the value of `x` in the bag— and use the initializing guard —which is true when the equation can be
solved and sets the unknown to a solution— the game can be written as follows

do x : f (x) ≥ 2 → | |

f (x−q), f (x), f (x+p) := f (x−q)+1, f (x)−2, f (x+p)+1 | |

od |

To start with, we generalize the game: for each move a new pair (`p`, `q`) of positive numbers may be chosen.
Furthermore we extend our program with auxiliary array `n`, initially satisfying for all `x` ` f` (`x`) = `n`(`x`),
and modified by extending the guarded command with the statement

n(x−q), n(x+p) := n(x−q) + 1, n(x+p) + 1 |

In other words, after initialization `n`(`x`) counts how many times `f` (`x`) is increased.

With `c` defined as `c` = (**N** `x` :: `n`(`x`) > 0) we have

**Lemma 0**.

Each `n`(`x`) is bounded **or** `c` is unbounded.

**Proof**. Since each `f` (`x`) is bounded by the constant number of integers in the bag, an `f` (`x`) that is increased an
unbounded number of times is also decreased an unbounded number of times, causing increases
of `n`(`y`) for some `y` > `x` (and some `y` < `x`). Hence we have for all `x`:

`n`(`x`) is bounded **or** (**S** `y` : `y `>`x` : `n`(`y`)) is unbounded.

Hence, for bounded `c` there is no largest `x` for which
`n`(`x`) is unbounded, hence there is no such `x` at all. (End of proof of Lemma 0).

Since “`c` is bounded **and** each `n`(`x`) is bounded” is equivalent with “the game terminates”, and since P ∨ Q equals
(¬Q ∧ P) ∨ Q, we derive from Lemma 0:

**Lemma 1 **

The game terminates **or** `c` is unbounded.

The smallest value in the bag is the smallest value `x` such that `n`(`x`) > 0 ; the largest value in
the bag is the largest value `x` such that `n`(`x`) > 0 . Hence, from Lemma 1 we conclude

**Lemma 2. **

The game terminates **or** the difference between largest and smallest value in the bag is
unbounded.

With the derivation of Lemma 2, the auxiliary array `n` has done its work. Defining “a gap of length `h`” as a solution
of the equation

`f` (`x`) > 0 **and** `f` (`x`+`h`) > 0 **and** (**A** `j` : `x `< `j` < `x`+`h` : `f` (`j`)=0)

we conclude from Lemma 2, because the number of integers in the bag is constant,

**Lemma 3.**

The game terminates **or** the length of the largest gap is unbounded.

Finally we undo some of our generalization: let the choice of the pair of positive numbers for each move be
restricted to pairs (`p`, `q`) such that `p`+`q` ≤ `K` for some `K`. We then have

**Lemma 4. **

No gap exceeds the maximum of `K` and the length of the largest initial gap.

Combination of the last two lemmata solves the Hungarian problem.

**Acknowledgement and concluding remark. **

Thanks are due to the members of the Tuesday Afternoon Club with whom I discussed my first proof of Lemma 2. That proof used mathematical induction on the number of integers in the bag. I am particularly grateful to R.W. Bulterman for the persistence of his dislike of the three-case analysis in the induction step required; He also objected to some handwaving with which I draw a correct but sweeping conclusion from “A possible move remains possible until done”.

I must admit that I would have liked a simpler termination proof than the one I found this evening. Perhaps it doesn’t exist: Hungary is a traditional source of non-trivial problems.

Considering first the generalized problem was an improvement; relaxing constraints could be a general technique for doing away with reductiones ad absurdum.

Plantaanstraat 5 | 2 December 1980 |

5671 AL NUENEN | prof. dr. Edsger W. Dijkstra |

The Netherlands | Burroughs Research Fellow |

Transcribed by Martin P.M. van der Burgt

Last revision