An interesting piece, I came across browsing some combinatorial problems. The plot is connected with Greek mythology. Medusa was a monstrous creature, a winged human female with living venomous snakes in place of hair. Those who gazed into her eyes would turn to stone. King Midas ruled Phrygia, a Greek city. He had ability to turn everything he touched into gold. So, you see, it’s interesting to imagine what would happen if we place them both into the ring, one vs another! Here is the story.
Problem 8, 2nd day. King Midas and Medusa alternatively play on an infinite chessboard. Initially, all of the cells of the chessboard are made of stones. In each of his turn, Midas chooses three squares which are in the same column or row, and turns them into gold. In each of Medusa’s turn, she can choose any grid square and turns its 4 cells into stone. King Midas wins if he can make a grid square entirely of gold. Medusa wins if she can always prevent Midas doing so. Who wins?
Some observations and motivation.
I admit, at first I had read the problem very sloppy, and it seemed as if there was a grid board on which the action took place. So, it seemed a very easy problem then, since Midas cannot win, no matter of Medusa’s moves. Indeed, suppose Midas makes all cells of the table golden with his last move. But, in her previous move Medusa had stoned some square, and the king cannot make all of its 4 cells gold just in one move. I even looked up after the name of the competition wondering was it a kindergarten one! Anyway, this observation is helpful. It shows king Midas cannot choose some big square and make it golden. Medusa always wins in some local area. If it’s possible Midas to win, he must place multiple threats of making gold squares on many well apart areas. He should use his advantage of placing threats on 3 well apart areas at a time, while Medusa could eliminate only 2 of them.
The strategy of King Midas.
We prove King Midas always can make a gold square. Moreover, Midas, in a good mood can allow Medusa to stone any 4 cells, that are intersection of 2 rows and 2 columns.
Let be a large enough positive integer which will be determined later. The king chooses an infinite family of disjoint squares lined up in a row. In every move he turns into gold the upper-left cells of 3 different empty squares in . After turns, he marks the upper-left corner of sets in and Medusa can erase at most of them, since she can operate over no more than 2 sets in at a time. Once Medusa operates over a square in , Midas considers it as unusable and does not take any action on its cells.
Thus, after the first phase, we get squares in with golden upper-left cell. We denote the family of those squares as Further, Midas aims at cells, each one in distinct set in , disposed at the same positions inside the big squares, and begins turning them into gold, 3 at a time. He manages to do it in moves, while Medusa can damage at most sets in . At this moment we have sets of with two goldean cells each, disposed at the same positions. Denote that subfamily of as
Midas proceeds in the same spirit obtaining each next phase a family of sets with golden squares each, disposed at the same positions. For there will be at fully golden square, providing we have chosen .