25
$\begingroup$

Viswanathan Anand plays a chess game against Magnus Carlsen. Anand plays white and Magnus plays black. They use a non-standard digital double chess clock that is counting up from zero (instead of the usual counting down towards zero). This double chess clock shows hours, minutes and seconds for both players. At the moment when Magnus completes his 40th move, both clocks read 2 hours, 30 minutes, 00 seconds.

Question 1: Was there necessarily a moment in the game, when the clock of one player showed exactly 1 min 51 sec less than the clock of the other player?

Question 2: Was there necessarily a moment in the game, when the clock of one player showed exactly 1 min 57 sec less than the clock of the other player?

$\endgroup$
  • 2
    $\begingroup$ I assume they're playing without increment, which would case a player's time to increase after his move? $\endgroup$ – xnor Mar 24 '15 at 9:13
  • 2
    $\begingroup$ @xnor: Yes, they play without increment. Nothing fancy: At the end of your move, you press your button; then your clock stops moving, and the clock of your opponent starts running. Repeat. $\endgroup$ – Gamow Mar 24 '15 at 9:15
  • 3
    $\begingroup$ I've edited the tags, since the puzzle actually has nothing to do with the game of chess (it could just as easily be any other game they're playing). It's more like a combinatorics problem, based as it is on the intermediate value theorem. I hope you don't mind! Nice puzzle btw. $\endgroup$ – Rand al'Thor Mar 24 '15 at 9:49
  • 6
    $\begingroup$ Well, I'm not going to enter into an edit war over it, but the chess tag should really be used only for puzzles that intrinsically involve the game of chess. This doesn't: you could just as easily replace the chess-game context with anything else involving two people taking turns to do something under timed conditions. $\endgroup$ – Rand al'Thor Mar 24 '15 at 9:59
  • 1
    $\begingroup$ Note that specifying the 40th move (instead of, for example, the 38th move) can have a significance: in many tournaments extra time is added to the clock (so the clocks are set back) after the 40th and 60th moves. If you don't have the intention of leading your audience in this direction, it would be better to change it to another number. Unless you want to have a red herring with the explicit purpose of introducing a fake lead into the question. :) $\endgroup$ – vsz Mar 25 '15 at 7:10
11
$\begingroup$

The answer to question 1 with 1 min 51 sec (that is, $n=111$ seconds) is yes. The answer to question 2 with 1 min 57 sec (that is, $n=117$ seconds) is no. Both answers are special cases of my solution that fully settles this puzzle for all possible numbers $n$ of seconds!

Question: Was there necessarily a moment in the game, when the clock of one player showed exactly $n$ seconds less than the clock of the other player?

Since 2 hours 30 minutes are exactly 9000 seconds, one would expect that the answer changes at 9000/80 = 112.5 seconds. But surprise, surprise, this is not correct!!

If $n\le114$ then the answer is yes.
If $n\ge115$ then the answer is no.

For $n\le114$, assume that the time difference never is $n$. Then the first move of first player takes at most 113 seconds as the second clock shows 0. Then the first move of the second player takes at most 113 seconds more than the time on the first player's watch. Then the second move of the first player takes at most 113 seconds more than the time on the second player's watch. Continuing this way we get by mathematical induction:

After move $m$ of the first player, his watch has traversed at most $113*(2m-1)$ seconds.
After move $m$ of the second player, his watch has traversed at most $113*(2m)$ seconds.

After move 40 of the first player, his watch has traversed at most $113*(2*40-1)$ = 8927 seconds. This is below 2.5 hours. There is a contradiction.

For $n\ge115$ construct a game where the first move of the first player takes 114 seconds. The first move of second player and all moves 2,...,39 of both players take 228 seconds.

After the first move of first player, the difference has gone up from 0 to 114. The first move of second player brings the differences down from 114 to -114. The next move of the first player brings the difference up to 114 again. The next move of the second player brings the difference down to -114 again, and so on.

After move 39 of the second player the difference is down at -114 again. The watch of the first player has traversed 114+38*228 seconds, this is 8778 seconds. The watch of the second player has traversed 39*228 seconds, this is 8892 seconds. Move 40 of the first player takes 222 seconds and brings the difference up to +108. Move 40 of the second player takes 108 seconds and brings the differences down to 0.

The difference always stays between -114 and +114 and the watches are never $n\ge115$ seconds away from each other.

$\endgroup$
  • 4
    $\begingroup$ This doesn't really add much. You've copied my method to prove something that wasn't asked about in the OP. $\endgroup$ – Rand al'Thor Mar 24 '15 at 23:53
  • 2
    $\begingroup$ Why are you so rude to me? The average time taken for a move is highly relevant to the solution, and commenting on the ideas used (here, the IVT) is common practice. But anyway, there's no point debating; let Gamow (not Gamov btw) tell us himself which answer he thinks is better. $\endgroup$ – Rand al'Thor Mar 25 '15 at 10:12
  • 3
    $\begingroup$ OK, now you've edited your post to actually answer the OP's question. You were still 2 hours late. I got there first, I'm afraid. If you'd used a slicker method, it would have been different. $\endgroup$ – Rand al'Thor Mar 25 '15 at 10:16
40
$\begingroup$

After 40 moves by each player, 150 minutes have elapsed on each player's clock. So the average time taken for a move is exactly $150/40=3.75$ minutes, i.e. 3 minutes and 45 seconds.

Question 1

The answer is yes.

Proof: by a continuous version of the pigeonhole principle, there must be a move by one player or other (WLOG, say Anand's $n$th move) that takes at least 3 minutes 45 seconds. Assume for contradiction that the difference in times between the two clocks is always less than 1 minute 51 seconds (1.85 minutes). At the start of Anand's $n$th move, (Anand's time)-(Carlsen's time) is at least $-1.85$ minutes. Increase this by at least 3 minutes 45 seconds to get that at the end of Anand's $n$th move, (Anand's time)-(Carlsen's time) is at least $3.75-1.85=1.9>1.85$ minutes, contradiction. So the difference in time is $\geq1.85$ minutes at some stage of the game. The difference starts off at $0$ minutes, so by the pigeonhole principle, it must be exactly 1.85 minutes at some stage. QED.

Question 2

The answer is no.

Proof: the following scenario is possible.

  • Anand's first move takes exactly 1 minute 56 seconds
  • each move from Carlsen's first to Anand's 39th takes exactly 3 minutes 52 seconds (which is double 1 minute 56 seconds)
  • Carlsen's 39th and Anand's 40th move each take exactly 1 minute 8 seconds
  • Carlsen's 40th move takes exactly 1 minute 56 seconds again.

It can be verified that the total time taken by each player is exactly 150 minutes. After every move from Anand's first to Anand's 39th, exactly 1 minute 56 seconds more have elapsed on the clock of the player who has just moved than on the clock of the player whose move it is. After Carlsen's 39th move, Anand's clock is still 48 seconds ahead of Carlsen's. After Anand's 40th move, his clock is again 1 minute 56 seconds ahead of Carlsen's. After Carlsen's 40th move, the clocks are equal at 150 minutes. So the difference between the two clocks is always at most 1 minute 56 seconds.


A nice variant of the classical intermediate value theorem-type problems.

$\endgroup$
  • 2
    $\begingroup$ This was beautifully rigorous. $\endgroup$ – Cruncher Mar 24 '15 at 16:33

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.