13/09/01 05:00:47.76
>>351
２ｎ－１個の整数の中に、余りが同じものがｎ個以上あれば、そこからｎ個を取り出すと和はｎの倍数なので、命題は成立する。
よって、以下では、余りが同じものはｎ－１個以下とする。
ｎの因数についての帰納法による。
(1) ｎが素数のとき
２ｎ－１個の整数をｎで割った余りの順に並べ、x_1, x_2, ..., x_(2n-1) とする。
同じ余りがｎ個以上並ばないため、
j-i ≧ n-1 ⇒ x_j - x_i はｎで割リ切れない。
ここで、i=1,2,････,n-1 に対して
y_i = x_(n+i)- x_i ≠ 0 (mod n)
つまり、「非合同ペア」がｎ－１組できる。
{x_1、x_(n+1)}
{x_2、x_(n+2)}
････････
{x_(n-1)、x_(2n-1)}
各ペアから一方を選ぶやり方は
{y_1、y_2、･････、y_(n-1)}
の部分集合（φも含める）と対応しており 2^(n-1) とおりある。