Q3 Matemática  (Czech-Polish-Slovak Match 2010)

Seja $p$ um número primo. Prove que de uma matriz de quadrados $p^2\times p^2$, podemos selecionar $p^3$ dos quadrados de tal forma que os centros de quaisquer quatro dos quadrados selecionados não sejam os vértices de um retângulo com lados paralelos para as bordas da matriz.