Q10 Matemática  (IMO Shortlist 2006)

Um bolo tem a forma de um quadrado $n$ x $n$ composto por $n^2$ quadrados unitários. Os morangos ficam em alguns dos quadrados unitários, de modo que cada linha ou coluna contém exatamente um morango; chame este arranjo $\mathcal{A}$. Seja $\mathcal{B}$ outro arranjo. Suponha que cada retângulo de grade com um vértice no canto superior esquerdo do bolo contenha não menos morangos do arranjo $\mathcal{B}$ do que do arranjo $\mathcal{A}$. Prove que a disposição $\mathcal{B}$ pode ser obtida de $\mathcal{A}$ executando uma série de trocas, definidas da seguinte forma: Uma troca consiste em selecionar um retângulo de grade com apenas dois morangos, situado no canto superior direito canto e canto inferior esquerdo, e movendo esses dois morangos para os outros dois cantos desse retângulo.