MathDB
Iran TST P11

Source: Iranian TST 2022 problem 11

April 2, 2022
combinatoricsgridcells

Problem Statement

Consider a table with nn rows and 2n2n 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 mm such that we can put mm 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