8
$\begingroup$

Consider a blackboard with some positive integers written on it.

A move consists one of the following actions:

  1. Choose two integers $m$ and $n$ on the board, remove them, and write $m+n$ on the board.
  2. Choose one composite integer $m$ on the board, remove it and write all distinct prime factors of $m$ on the board.

The game ends when there is only one prime number on the board, or just the number one.

Does the game always end?

Improve this question
$\endgroup$
6
  • $\begingroup$ Can $m$ be prime for the 2nd type of move? $\endgroup$
    – Ankoganit
    Jul 22, 2016 at 11:08
  • $\begingroup$ Does your rule with distinct prime factors mean that for example for a 4 you only write a single 2 back to the board? $\endgroup$
    – The Dark Truth
    Jul 22, 2016 at 11:08
  • $\begingroup$ @TheDarkTruth Yes. $\endgroup$
    – wythagoras
    Jul 22, 2016 at 11:08
  • 1
    $\begingroup$ @Ankoganit No, I will add that. $\endgroup$
    – wythagoras
    Jul 22, 2016 at 11:09
  • 4
    $\begingroup$ No. 1 is not a prime. $\endgroup$
    – wythagoras
    Jul 22, 2016 at 11:09

1 Answer 1

Reset to default
7
$\begingroup$

The answer is

Yes, the game always ends.

Proof:

Suppose it can continue infinitely long. Note that the $2$nd type of operation strictly decreases the sum of numbers on the board, whereas the $1$st operation leaves it invariant. So we can perform the $2$nd operation only finitely many times. Consider the last occurrence of the 2nd operation. Some there can't be infinitely many operation of there first type between two consecutive operations of the first type, we have made only finitely many moves so far. (Thanks to elias for this part). After the last occurrence of the $2$nd operation, we can only make the first type of operation, which always decreases the number of numbers on the board by one. So it has to stop eventually. $\mathrm{QED}$

Improve this answer
$\endgroup$
4
  • $\begingroup$ I think your proof - to be robust and correct - needs that between two consecutive occurences of the 2nd operation (or before the first one), the 1st operation can be performed only finite times. Otherwise the 'last occurence of the 2nd operation' that you mention could have happen after infinite occurences of the 1st operation. Or do I miss something? $\endgroup$
    – elias
    Jul 22, 2016 at 11:35
  • 4
    $\begingroup$ I suggest the following way to think of it. Label each position by (sum of numbers, number of numbers); order "lexicographically"; then every move takes you strictly earlier in the ordering; but this is a well-ordering so can have no infinite strictly decreasing sequence. $\endgroup$
    – Gareth McCaughan ♦
    Jul 22, 2016 at 12:31
  • $\begingroup$ @GarethMcCaughan, I think, even in this one it is worth emphasizing, that a neither of the operation increases the 'number of numbers' to infinity. otherwise you could step (with a 2nd operation) from let's say (5,2) to (4,infinity), where you might get stuck - infinite 1st operations might be performed without stepping away from (4, infinity). do you agree? $\endgroup$
    – elias
    Jul 22, 2016 at 21:56
  • $\begingroup$ I suppose it depends on what you're willing to regard as obvious. Personally I'm comfortable just leaving it unstated that you've suggested got a finite collection of numbers on the blackboard; I wouldn't worry about suddenly having infinitely many any more than I would about suddenly finding pictures of kittens on the board instead of numbers. But there's certainly no harm in making it explicit. $\endgroup$
    – Gareth McCaughan ♦
    Jul 24, 2016 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.