A. Shapovalov => My problems

Problems which caused an article

Once used a problem begin to live by itself. These are problems which started discussions and caused popular or scientific articles.

Tanya Khovanova "A Line of Sages" - The Mathematical Intelligencer, November 2013

The problem was composed by me with the assistance of Konstantine Knop. I put the question and find a couple algorithmes for max 50 sages. K.Knop helped to find a much better result, just a bit worse then the best one. Then I solved the problem and found the optimal result.
The problem was first used on the Tournament of Towns in the Spring 2013.

A sultan decides to give 100 of his sages a test. The sages will stand in line, one behind the other, so that the last person in the line sees everyone else. The sultan has 101 hats, each of a different color, and the sages know all the colors. The sultan puts all but one of the hats on the sages. The sages can only see the colors of the hats on people in front of them. Then, in any order they want, each sage guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the sages cannot speak. They are not allowed to repeat a color that was already announced. Each person who guesses his color wrong will get his head chopped off. The ones who guess correctly go free. The rules of the test are given to them one day before the test, at which point they have a chance to agree on a strategy that will minimize the number of people who die during this test. What should that strategy be?


Alexander Shapovalov "Occupation games on graphs in which the second player takes almost all vertices" - Discrete Applied Mathematics, Volume 159, Issue 15, 2011

The problem was first used on the Tournament of Towns in the Spring 2011. A simplier version (for 4 geniuses) was used on the Moscow Math Olympiad the same year.
Then the general result was published as a scientific article.

Among a group of programmers, every two either know each other or do not know each other. Eleven of them are geniuses. Two companies hire them one at a time, alternately, and may not hire someone already hired by the other company. There are no conditions on which programmer a company may hire in the first round. Thereafter, a company may only hire a programmer who knows another programmer already hired by that company. Is it possible for the company which hires second to hire ten of the geniuses, no matter what the hiring strategy of the other company may be?

Christian Blatter "A prince and a moving princess"
John R. Britnell, Mark Wildon "Finding a princess in a palace: A pursuit-evasion problem" - arXiv:1204.5490 [math.CO]

The problem was first presnted on by V.Shorin and me to the Kvant Summer Tournament of Towns in 1999 . Then a general question "Find all graphs for which a pursuit can always succeed" was presented by A.Spivak and me to the Moscow Math Olympiad in 2000 .

A princess inhabits a flight of 17 rooms in a row. Each room has a door to the outside, and there is a door between adjacent rooms. The princess spends each day in a room that is adjacent to the room she was in the day before. One day a prince arrives from far away to woo for the princess. The guardian explains the habits of the princess and also the rules to him: Each day he may knock at an outside door of his choice. If the princess is behind it she will open and in the end marry him. If not, nothing happens, and he gets another chance the next day. Unfortunately his return ticket expires after 30 days. Does he have enough time to conquer the princess? (Adapted from "simpler-solutions.net")