Turbo the snail plays a game on a board with 2024 rows and 2023 columns. There are hidden monsters in 2022 of the cells. Initially, Turbo does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.
Turbo makes a series of attempts to go from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move, and Turbo remembers whether or not each cell he has visited contains a monster. If he reaches any cell in the last row, his attempt ends and the game is over.
Determine the minimum value of n for which Turbo has a strategy that guarantees reaching the last row on the nth attempt or earlier, regardless of the locations of the monsters.
What is the smallest number of attempts Turbo is guaranteed to escape in (and what is the strategy for it)?
First of all, cool problem. It would be a great component of an adventure novel or movie, putting the reader into the character's shoes to solve the maze. If it was me I would have forgotten about Game Theory and got eaten by monsters. The math problem phrasing makes solving much easier, by emplying the existance of a good solution. The problem says it's a snail and a board, but lets be honest, this is a labyrinth in some crazy death game escape show.
2024, 2023, and 2022 are year numbers. Though sometimes year numbers have special properties, I doubt it's the case here, so simplifying to a 10x9 board should be alright (thought the solution could be proportional or maybe maybe even-odd dependent.) The overall model of the board feels familiar: grid, puzzle game, and especially chess with rook placement problems.
Best way to get a hang of the situation is to play a few rounds, but make sure your are imagining the board correctly. There is exactly one monster in each row and each column, (except one column that is empty to ensure an escape path always exists.)
There are factorial (!2023) possible monster placements. But notably, the problem asks not for probabilities but guarantees. The average doesn't matter; your strategy must perform well in worst case scenarios. You can't assume the monster placement is random, the creator of the labyrinth could be messing with you.
For most strategies the worst case scenario is a diagonal line of monsters ("Hard mode"), forcing you to hit every single monster before finding the empty column. Oh, then I will just go to the last "empty" column streight away. Hold your horses, the gamemaster could have shifted the gap to anywhere on the diagonal, if it is a diagonal at all.
After you are done fighting the diagonal, make sure your strategy still works in "normal" cases and can beats all my levels consistently.
Congratulations, you won!
Hint 1: Finding a cell with a monster reveals much more information than you might think.
Hint 2: There is a good way to find a hole in a diagonal thanks to a quirk in monster placement.
It is an easy problem. I solved it quickly and thought it was just another CS problem (I had no context). Now the reveal: this is International Mathematical Olympiad (IMO) 2024 problem 5 here is a reddit thread on it.
Both People (and Machines) were struggling, only 3/6 of the Chinese (ranked second), 1/6 Koreans (ranked third), and 4/6 of the Indian team (fourth) solved it. In addition, Google's DeepMind failed to solve it as well, despite solving the hardest problems on the list.
There is a simple strategy that can be described in a pharagraph, but nobody expectes it to be that easy so the people overthink it (eg. logarithmically proportional to board size is a common answer). I won't spoiler and let you do the solving.
Bonus question: What is the best strategy if you have only one attempt? (It is a hard question)
This page is a single static .html file. You can view or download it's source code with Ctrl+S or Ctrl+Shift+C (Inspect).
My Homepage is hosted on github pages (from this Source Code). To clarify, the problem text is IMOs, the rest of the page is mine under CC0.
The problem sounded like a minigame and so I made it into one. The game in itself is easy. The current levels are more simulators for testing your strategy against edgecases than brainteasers. Because each strategy has it's own unique worst case scenario, I couldn't think of a way to program a universally difficult level.
Clarification on difficulty levels:
The game makes solving the problem much easier, probably because it is hard to imagine the board correctly and having a correct board in front of you makes parts of the strategy instantly obvious. People who played the game hacked my monster placement behavior on each level very quickly, they tried around randomly until something worked. Hard mode with the diagonal turned out to be harder than evil mode.
I don't recommed running the actuall 2024x2023 board (or higher than 100x99 for that matter) as it would need 4 million cells taking up megabytes of memory, with an average screen and laptop not being able to reender such amounts of HTML (so I added a confirmation pop-up when more than 100 rows are entered). But if you really really want to for whatever reason: You Have Been Warned!
Because I like suffering, I didn't use <canvas>, instead I decided to try CSS grids. If there is anything more fun than solving cool math problems, it is fighting CSS.