Je ne comprends pas la solution de ce problème INMO

Question

Dans n'importe quel ensemble de $181$ entiers carrés, prouve qu'on peut toujours trouver un sous-ensemble de $19$ nombres dont la somme des éléments est divisible par $19$.

Quelqu'un sur AOPS :

La vérification directe montre que tout carré est $0,1,4,9,16,6,17,11,7,5 \mod [19].$ Il y a donc exactement $10$possibilités distinctes. Du principe du casier, puisque vous avez utilisé$181$ nombres au moins un de la classe contient au moins $19$de vos carrés. Ajout de ces$19$ les carrés de la même classe conduisent au résultat.

Quelqu'un peut-il m'expliquer cette solution, ou une autre?

Merci!

PS: Cette question est tirée de l'Olympiade mathématique nationale indienne 1994, problème 3

Answer 1

S'il y avait au plus $18$ de chacun de ces $10$ congruences carrées utilisées dans l'ensemble, alors le nombre maximum d'éléments dans l'ensemble serait $18 \times 10 = 180$. Cependant, comme il y a$181$ éléments, cela signifie que, selon le principe du casier, il doit y avoir au moins une congruence, disons $r$, utilisé au moins $19$fois. Comme l'indique la solution, ajouter ces$19$ éléments donneront une somme avec un reste de $19r$, c'est-à-dire une valeur divisible par $19$.

Notez qu'en général, vous n'avez besoin que d'un ensemble de $2 \times 19 - 1 = 37$ entiers, sans aucune restriction particulière sur leurs congruences, pour qu'il y ait un sous-ensemble de $19$ d'entre eux qui totalisent un multiple de $19$. Pour plus d'informations sur ces types de problèmes, veuillez consulter Prouver que parmi les$2n - 1$ entiers, il y a toujours un sous-ensemble de $n$ dont la somme à un multiple de $n$.