7
$\begingroup$

The numbers 25 and 36 are written on a blackboard. At each turn, a player writes on the blackboard the (positive) difference between two numbers already on the blackboard, if this number does not already appear on the blackboard. The loser is the player who cannot write a number.

I tried but wasn't able to find any approach to this.

Original source appears to be: Mathematical Circles (Russian Experience), page 58.

$\endgroup$
  • 4
    $\begingroup$ What's the question? "Which player has a winning strategy" maybe? $\endgroup$ – 2012rcampion Mar 30 at 17:54
  • 1
    $\begingroup$ Hi and welcome to Puzzling SE! This looks like a puzzle you found elsewhere. For content you did not create yourself, proper attribution is required. If you have permission to repost this, please edit to include (at minimum) where it came from, then vote to reopen. Posts which use someone else's content without attribution are generally deleted. $\endgroup$ – Eagle Mar 30 at 18:24
  • 2
    $\begingroup$ P.S. The wording of the above comment are taken from Rubio's answer here This wasn't added in the above comment as it was exceeding the word limit by 42 characters. $\endgroup$ – Eagle Mar 30 at 18:25
  • 1
    $\begingroup$ (Thanks @Akari. I was able to find what seems to be the original source, and added it. $@\!$ all about everything, please be mindful of our attribution requirements here going forward. Thanks for contributing and welcome to Puzzling!) $\endgroup$ – Rubio Mar 30 at 21:28
  • $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it :) $\endgroup$ – Rubio Apr 2 at 18:11
8
$\begingroup$

The numbers $25$ and $36$ are coprime. This means that if we continually replace the largest of the two numbers by the (positive) difference of the two numbers, we are essentially performing the Euclidean algorithm for finding their GCD, and will eventually get a $1$. The sequence is $36$, $25$, $36-25=11$, $25-11=14$, $14-11=3$, $11-3=8$, $8-3=5$, $5-3=2$, $3-2=1$.
Once there is a $1$ on the board, you can repeatedly subtract it to fill in any gaps and eventually produce every number from $1$ to $36$. This shows that if you have two cooperating players, all number from $1$ to $36$ can be produced.
But this also happens when the game is played between two non-cooperating players. It is impossible to prevent any of the numbers appearing. If any number in the euclidean sequence is not on the board, then there are still moves available. So eventually $1$ must be produced, and then as long as there are missing numbers between $1$ and $36$, there is at least one move available. This means that regardless of what moves are played, all numbers $1$ to $36$ will appear. We started with $2$ numbers on the board, so the game ends after $34$ moves.

The result is that

The game always ends after $34$ moves, after which the first player cannot move and loses.

$\endgroup$
  • 4
    $\begingroup$ Beat me by a minute, nice one :-) $\endgroup$ – Rand al'Thor Mar 30 at 18:04
5
$\begingroup$

The key fact is as follows:

The only time the game can end is when the numbers are in the form $k,2k,3k,4k,\dots,ak$ for some fixed $a$ and $k\geq1$. This is because, given two numbers $m$ and $n$ on the board, we can always apply repeated subtraction between them to reach their GCD, and then from there to reach every multiple of their GCD up to $\text{max}(m,n)$.

Therefore this particular game ends when the numbers on the board are

$1,2,3,4,\dots,35,36$. This will take a total of 34 moves, since there are two numbers at the start and a new one is written each time.

So the conclusion is

no matter how the game goes, the first player loses, since 34 is even.

$\endgroup$
  • 2
    $\begingroup$ Beat me by about 3 seconds :) Oh, and Jaap beat the two of us as well. $\endgroup$ – Arnaud Mortier Mar 30 at 18:02
3
$\begingroup$

Answer:

The player who plays first will lose, no matter what choices the player make.

This is because

The Euclidean algorithm tells you that as long as $1$ (the gcd of $25$ and $36$) is not on the board, there are legal ways to continue the process. Now, from the moment when $1$ does appear on the board, no matter how long it took to get there, every positive number between $1$ and $36$ becomes reachable.

Therefore

no matter what path is taken, the amount of steps before the game is over is $34$, one for each integer between $1$ and $36$, excluding the two already on the board at the beginning of the game.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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