3

[Full disclosure: I'm a noob]

The game: Squares and Circles. There are a finite number ($n$) of squares and circles and two players take turns, able to do the following moves:

a) Replace a pair of identical shapes with a square

b) Replace a pair of different shapes with a circle.

The game ends when there is one shape left. Prove the game ends.

My questions is whether it's necessary to use induction here to prove that the game ends. Is it sloppy just to consider the two types of moves and show that both the moves decrease the number of shapes by 1, and that after $n-1$ turns there would be only one shape left?

Michael Hardy
  • 1
Yashmnash
  • 187
  • I'm reticent to comment whether it is necessary or not to use induction, but certainly it gives a clean way to prove that the game ends, so I'm not sure why one would avoid it. The game immediately ends if $n = 1$, so suppose $n > 1$. If all $n$ shapes are the same, move (a) reduces the number of shapes to $n-1$; if not, there must be at least one pair of different shapes, so move (b) reduces the number of shapes to $n-1$. By induction, a game beginning with $n-1$ shapes terminates, so we're done. – Alex Wertheim Jul 14 '17 at 01:32
  • As for your reasoning, that seems fine, though it is maybe worth saying a sentence (as I did) demonstrating that there is always a move available, no matter what the ''state'' of the board is. – Alex Wertheim Jul 14 '17 at 01:34
  • 3
    From one point of view, the following are equivalent: $$ \begin{align} \bullet & \text{ Every non-empty subset of } \mathbb N \text{ has a smallest member.} \ \bullet & \text{ Every decreasing sequence of members of } \mathbb N \text{ is finite.} \ \bullet & \text{ The principle of mathematical induction.} \end{align} $$ You used the second of these three propositions. $\qquad$ – Michael Hardy Jul 14 '17 at 01:42
  • 1
    The parity of the number of circles is an invariant. There you have another chance to use induction to show that the surviving shape is a circle if and only if the initial number of circles is odd. – Fabio Somenzi Jul 14 '17 at 05:27

2 Answers2

4

That is a fine proof. Generally what is an acceptable proof depends on your audience. You are trying to convince them that it could be made formal if you wanted to. Making this formal would invoke the fact that the naturals have a minimum, but that is "obvious".

Ross Millikan
  • 374,822
1

Let's see if we can do it in the three ways mentioned in my comment.

  • One of the three is already done in the posted question; that is the second bullet point in my comment under the question.
  • Now let's try the method in the first bullet point in my comment. Suppose there is a smallest number $n$ such that in some cases if there are $n$ shapes, the game need not end. The first move reduces the number of shapes. The number is then less than $n.$ Since $n$ is the smallest possible counterexample and this is smaller than $n,$ this is not a counterexample; therefore the game must subsequently come to an end. Our assumption that a counterexample exists is therefore seen to be false.
  • Now mathematical induction. The basic case is $n=1;$ in that case the game has already ended. Now suppose $n$ is some number for which, if the total number of shapes is $\le n,$ then the game must end. If there are $n+1$ shapes, then the first move reduces the number of shapes to one for which the game must end. Therefore with $\le n+1$ shapes, the game must end.

Earlier I posted this related question. The present question seems like a case where the method in my second bullet point is the most efficient way to do the problem. Proving that Euclid's algorithm always terminates is perhaps another such instance.

Michael Hardy
  • 1
  • 1
    The OP's proof uses only a very special case of the second bullet point, namely the case that the each term of the sequence is the preceding term minus $1$. To me (and probably to you) this special case looks no simpler than the general case. But, in view of the difficulties some students have with induction and equivalent principles, I can't help wondering whether the special case might be more obvious to some students than the general case. – Andreas Blass Jul 14 '17 at 04:06
  • @AndreasBlass : I know that some things obvious to me are not obvious to many undergraduate students, but nonetheless I'm somewhat inclined to doubt that this is one of those. – Michael Hardy Jul 14 '17 at 04:53