  |
整数列a1...aNとし、a1からaLまでの部分列の和をsLとする(L=1...N)。
s1...sNはN個あり、sLをNで割った余りは最大0からN-1までのN個ある。
A. Nで割った余りが0になるsLが存在していれば、a1...aLがその和がNで割り切れる部分列である。
B. どのsLもNで割った余りが0にならなければ、取りうる余りは1...N-1の最大N-1個である。
取りうる余りは多くてもN-1個のため、N個のs1...sNのうち少なくとも2つは、Nで割ると同じ余りになるものが存在する(鳩の巣原理)。
この同じ余りになるsLで、先をsA、後をsBとすると、sB-sAは、Nで割ると余りが０になる。
{k^2, (k+1)^2, ..., (k+N)^2} のうちには 必ず N で割れる数が存在する
14
