215k views
4 votes
Kate drew a 33×33 checkered square (lattice) on the asphalt with white chalk (i.e. there are 34 horizontal segments and 34 vertical segments drawn). By one move it is allowed to pick out an arbitrary square (of any size) and repaint its boundary using a chalk of blue colour. In different moves it is allowed to repaint any segment more than once. What is the smallest number of such moves required to repaint all the initial lines in blue colour?

1 Answer

4 votes

Final answer:

The minimum number of moves to repaint all the initial lines in blue on a 33×33 checkered lattice is 132 moves. This is determined by the need to repaint all the outermost segments exactly once.

Step-by-step explanation:

The student's question is asking for the smallest number of moves required to repaint all the lines of a 33×33 checkered lattice with blue chalk. To find this, we must recognize that the task involves repainting over segments, which could be done strategically in order to minimize the number of moves. The key here is to take into account that the boundary of any square will share sides with adjacent squares.

One efficient strategy is to repaint the boundaries of the individual 1×1 squares one by one. Since each side of a square is shared by 2 squares, except for the outer sides of the entire lattice, repainting a 1×1 square will repaint four lines, two of which may have already been painted in a previous move. However, there is no way to avoid repainting lines, as each has to be painted at least once. With 33×33 squares, this would require at least 33×33 moves.

Yet, this number is not strictly the minimum as we could start with the largest square (the border of the whole lattice) and then continue to repaint smaller squares inside it. But, regardless of method, each of the 2×(33+33) outermost segments need to be painted exactly once, and there are no adjoining segments to those that could be painted simultaneously in one move without overlapping.

Hence, the minimum number of moves is the number of independent lines on the boundary of the lattice, which is 2×(33+33) or 132 moves.

User AnV
by
8.1k points