A bear is in the center of the left down corner of a $100*100$ square .we call a cycle in this grid a bear cycle if it visits each square exactly ones and gets back to the place it started.Removing a row or column with compose the bear cycle into number of pathes.Find the minimum $k$ so that in any bear cycle we can remove a row or column so that the maximum length of the remaining pathes is at most $k$.
Problem
Source: Iranian third round 2019 finals Combinatorics exam problem 1
Tags: combinatorics
Pathological
21.09.2019 23:26
The answer is $k = 5000.$ This is clearly achievable by simply removing the $50$th row. We'll now show that this is optimal. Consider the following path. Start at the lower left corner. Move up until reaching the other corner. Move right one unit. Move down $49$ units. Move left one unit. Move up $49$ units. Move right one unit. Move down $49$ units. Repeat until we reach the top right corner. From there, rotate the board $180$ degrees and do the same thing. It's easy to see that we cannot guarantee any value $k < 5000$, and so the answer is $\boxed{5000}.$ $\square$
AgentC
31.07.2024 18:10
Pathological wrote: The answer is $k = 5000.$ This is clearly achievable by simply removing the $50$th row. We'll now show that this is optimal. Consider the following path. Start at the lower left corner. Move up until reaching the other corner. Move right one unit. Move down $49$ units. Move left one unit. Move up $49$ units. Move right one unit. Move down $49$ units. Repeat until we reach the top right corner. From there, rotate the board $180$ degrees and do the same thing. It's easy to see that we cannot guarantee any value $k < 5000$, and so the answer is $\boxed{5000}.$ $\square$ It should be 4999. A path with n vertices has length of n-1