2014 Math Festival in Moscow

I stumbled upon a couple of problems that I like while scanning the Russian website of Math Festival in Moscow 2014. The problems are for 7 graders.

Problem. Inside a 5-by-8 rectangle, Bart draws closed paths that follow diagonals of 1-by-2 rectangles. Find the longest possible path.

This problem is really very difficult. The competition organizers offered an extra point for every diagonal on top of 16. The official solution has 24 diagonals, but no proof that it’s the longest. I’m not sure anyone knows if it is the longest.

Here is another problem:

Problem. Alice and Bob are playing a game. They start with two numbers: 2014 and 2015. In one move a player can do one of two things:

  1. subtract one of the numbers by one of the non-zero digits in any of the two numbers or,
  2. divide one number by two if the number is even.

The winner is the person who is the first to get a one-digit number. Assuming that Alice starts, who wins?

Share:Facebooktwittergoogle_plusredditpinterestlinkedinmail

7 Comments

  1. Leo B.:

    How is the first problem different from: on a 5×8 chessboard, find the longest closed path using knight moves? I got 30 with little difficulty.

  2. tanyakh:

    Oops, They meant non-intersecting paths.

  3. Lew B:

    In “Non-crossing Knight Tours” at http://euler.free.fr/knight/index.htm for the 6×9 chessboard the value 24 is given. It indicates it is the longest known, but is not clear whether 24 is optimal.

  4. Adam:

    Oh, I got the second one! At the risk of it being a spoiler: For a given pair (A,B), a player can do any of: A-digit(A), A-digit(B), B-digit(A), B-digit(A), A/2 if A is even, and B/2 if B is even. When I first read the problem, I missed the two options A-digit(A) and B-digit(B). Once I realized those were options, the answer became clear.

  5. Adam:

    Here is a path of length 25 for the first one:

    Plot the rectangle on a grid, one corner at (0,0) and the opposite corner at (8,5).
    The following path has 25 diagonals, no overlaps:
    (0,3)-(1,5)-(2,3)-(3,5)-(4,3)-(5,5)-(6,3)-(7,5)-(8,3)-(6,2)-
    (5,4)-(4,2)-(3,4)-(2,2)-(1,4)-(0,2)-(2,1)-(3,3)-(4,1)-(5,3)-
    (6,1)-(8,2)-(7,0)-(5,1)-(3,0)-(1,1)

  6. tanyakh:

    Adam, great example. Unfortunately, they ask about closed paths.

  7. Adam:

    Oops. Well, at least I got the second one.