si aucune ligne n'a le même nombre de cases coloriées il y a donc la possibilité de colorier 0 1 2 ...n-1 n cases dans chaque ligne en excluant un seul de ces résultats.

Idem pour les colonnes.

Il y aura donc des nombres communs de cases coloriées en ligne et en colonne.

Si on ne compte pas les lignes ou les colonnes non coloriées (0 ne serait pas un nombre de cases coloriées) On peut les éliminer du problème et construire un rectangle n1 x n2  avec en ligne 1 à n1 cases coloriées et en colonne 1 à n2 cases coloriées. Cela revient au même.

Donc, pour éviter d'avoir 2 lignes ou deux colonnes ayant le même nombre de cases coloriées, il faut qu'une ligne et une colonne aient le même nombre de cases coloriées.

Il y a 2n lignes et colonnes contre seulement n possibilités de colorier un nombre de case dans une ligne ou une colonne. Voilà.

OK pour Titou et Nombrilist qui ont fait on ne peut plus court.

Question subsidiaire:
Combien de relations "égalité" au minimum existe t il ?

En fait, on ne peut à la fois se servir des n+1 possibilités offertes. En effet, si on ne met rien dans une ligne, on ne peut colorier n cases dans une colonne, ce sera au maximum n-1 cases. De même, si on colorie n cases d'une ligne, aucune colonne n'aura 0 case coloriée.
Au final, il y a toujours au minimum n relations d'égalités.

C'était un problème proposé dans le journal Le Monde et présenté sur le site Chronomath. C'est une application simple du principe dit "des tiroirs".