Consider a table with $n$ rows and $2n$ columns. we put some blocks in some of the cells. After putting blocks in the table we put a robot on a cell and it starts moving in one of the directions right, left, down or up. It can change the direction only when it reaches a block or border. Find the smallest number $m$ such that we can put $m$ blocks on the table and choose a starting point for the robot so it can visit all of the unblocked cells. (the robot can't enter the blocked cells.) Proposed by Seyed Mohammad Seyedjavadi and Alireza Tavakoli
Problem
Source: Iranian TST 2022 problem 11
Tags: combinatorics, grid, cells
08.05.2022 12:41
bump, any solutions?
09.05.2022 06:25
The answer is [n/2]-1.
09.05.2022 06:40
Consider a row doesn't contains the original square and it's not the border,if the Hamilton road turns left or right when reach it,then one of the 2 rows next to it has a block,if the road always go straight when reach it, then consider the column we can know that at least n-2 columns has blocks,other wise consider pairs (U,U+2),less then one pair satisfies both the Uth and U+2 th row don't have blocks,so there is at least [n/2]-1 blocks. And the construction is for 4|n-1,we set blocks at the left of the 3,7,...row and right of 6,10,.....row,and begin with the second square at the third row,for the other n bigger than 5,we set blocks at the left of the 5,9,13,....row and right of 4,8,.....row and begin with the left of the second row.
06.06.2022 00:01
The answer is $\left\lfloor\frac{n}{2}\right\rfloor-1$. But the construction is too troublesome! My answer with full of pics.
28.12.2023 08:21
Solved with rama1728. We claim that the answer is $\lfloor{\frac{n}{2}\rfloor} -1$. Say we have a working configuration with $m$ blocks on it. One can notice that the robot can slide along a row if and only if there is a block or an edge above or below it. Thus, placing a block 'unlocks' two rows. From this we can note that, we require, \[2m +3 \geq n \implies m \geq \lfloor{\frac{n}{2}\rfloor} -1\]Now, we shall give a construction to show that this number of blocks is sufficient. Note that, when $n \equiv 1 \pmod{4}$, we can simply place blocks on rows $3,7,11,\dots$ in the left-most column and rows $6,10,\dots$ of the right-most columns and simply start from the third row. For all other $n$, simply place blocks on the left-most column on rows $5,9,13,\dots$ and on the right-most column for rows $4,8,12,\dots$ and begin on the second row. Thus, indeed our answer is correct and we are done.