Tanks at the 2015 All-Russian Math Olympiad
Yesterday I went online to check out the problems at the 2015 All-Russian Math Olympiad. I was stunned to discover a problem about tanks and fighter jets. I have never seen such a militarized problem before. The problem setup tells me something about the mood of people in Russia. It tells me that the mood has changed—alarmingly for the worse.
On the other hand, mathematically it was my favorite problem. So here it is.
Share:The field is a 41 by 41 square made of square cells. A tank is camouflaged and hidden in one of the cells. A pilot flying a fighter jet above knows that the tank is there and wants to destroy it. If there is a tank in a cell, it will be hit by the shot directed at this cell. The pilot also knows that two hits are needed to destroy the tank. The tank will move to a neighboring cell immediately upon being hit, without breaking its camouflage. Other than that, the tank won’t move. What is the smallest number of shots required to guarantee that the tank is destroyed?
lvps1000vm:
There are two possible interpretations: that each square has four neighbors or that each square has eight neighbors.
I can come up with a two-coloring of the board in the first case and with a four-coloring in the second.
10 August 2015, 5:22 pmtanyakh:
Forgot to mention: neighbors are the ones that share a side.
10 August 2015, 5:23 pmJoshua:
Asking sincerely, aren’t the political implications things we already knew about Russia from the Ukraine/Crimea events back in March 2014?
11 August 2015, 4:08 amareign:
i can do it in 2521 shots
12 August 2015, 1:32 amGerhard:
Suppose that some square x is shot only once. Then every neighbor y of x must be shot at least once before x (as otherwise the tank could hide in y, and save himself by moving from y to x), and must be shot at least once after x (as otherwise the tank could hide in x, and save himself by moving from x to y).
Let S denote the squares that are shot only once, and let T denote the set of squares that are shot at least twice. Then S forms an independent set (in the graph theoretic set), and the length of the underlying shooting sequence is at least |S|+2|T|. On the other hand, for an arbitrary independent set S the seqnence that first shoots all vertices in T, then shoots all vertices in S, and finally shoots again all vertices in T is a feasible shooting sequence. (If the tank hides in T, it is hit in the first phase and once again hit in the second or third phase; if the tank hides in S, then it is hit in the sceond phase and once again hit in the third phase).
All this implies that the length of the shortest feasible shooting sequence of any graph equals twice the number of vertices minus the size of the largest independent set. For the 41×41 chessboard, the largest independent set consists of the 21×21 black squares in a standard chessboard coloring.
Hence the answer to the 2015 All-Russian Math Olympiad puzzle is 2*41*41-21*21=2921 shots.
19 August 2015, 8:34 amA:
Making far-reaching conclusions about the whole people based on a single problem is of course unacceptable but – out of curiosity – how would you reformulate this problem? Have you never seen a problem where someone is trying to ‘kill’ something? How was it different? Would it be a better setting if they asked you to kill semi-blind animals instead of destroying tanks?
6 September 2015, 9:52 amTanya Khovanova's Math Blog » Blog Archive » From Tanks to Coins:
[…] already wrote about my favorite problem from the 2015 All-Russian Math Olympiad that involved tanks. My second favorite problem is about coins. I do love almost every coin […]
16 September 2015, 2:38 pm