APMO 2021 P4 - There exists a good subset consisting of at least $666$ cells

Discussion on Asian Pacific Mathematical Olympiad (APMO)
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
APMO 2021 P4 - There exists a good subset consisting of at least $666$ cells

Unread post by Anindya Biswas » Wed Jun 09, 2021 5:23 pm

Given a $32\times32$ table, we put a mouse (facing up) at the bottom left cell and a piece of cheese at several other cells. The mouse then starts moving. It moves forward except that when it reaches a piece of cheese, it eats a part of it, turns right, and continues moving forward. We say that a subset of cells containing cheese is good if, during this process, the mouse tastes each piece of cheese exactly once and then falls off the table. Show that:
  1. No good subset consists of $888$ cells.
  2. There exists a good subset consisting of at least $666$ cells.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply