nは2以上の自然数とする。
(1)
n個の自然数 x(1), x(2), …, x(n)のどれもnで割り切れないとき、
x(j)-x(i) (1≦i<j≦n)
がnの倍数となる2つの自然数 i, jが存在することを示せ。
(2)
n個の自然数 a(1), a(2),…, a(n) からなる集合をSとする。Sの空でない部分集合で、その要素の和がnで割り切れるものが存在することを示せ。
(1)
nで割り切れない自然数は、自然数k,mを用いて
kn+m (0≦k, 1≦m≦n-1)と表せる。
x(1)=k(1)n+m(1), x(2)=k(2)n+m(2),…, x(n)=k(n)n+m(n)
とすると、
x(j)-x(i)=k(j)n+m(j)-k(i)n-m(i)=n{k(j)-k(i)}+m(j)-m(i)
ここで、1≦m≦n-1より、1≦i<j≦nを満たすi, jについて、m(j)=m(i)となる自然数i, jは少なくとも1組存在する。
よって、x(j)-x(i)=n{k(j)-k(i)}となる自然数i, jは少なくとも1組存在し、k(j)-k(i)は整数だから、そのi, jについてx(j)-x(i)はnの倍数である。
(証明終)
(2)
Sの空でない部分集合をPとする。
(?@)
n個の自然数 a(1), a(2),…, a(n)の中に、少なくとも1つnの倍数が含まれているとき、明らかに、その要素の和がnで割り切れるPが存在する。
(?A)
n個の自然数 a(1), a(2),…, a(n) がすべてnの倍数でないとき、(1)と同様にして、
a(1)=k(1)n+m(1), a(2)=k(2)n+m(2),…, a(n)=k(n)n+m(n)
とおく。
(2)について、このあと、
1≦m≦n-1を満たすmについてn個のmがあるとき、そのn個のうちで和がnの倍数となるmの組み合わせが存在する
ことを示せばよいと思うのですが、やり方が思い浮かびません。
(1)を利用するんでしょうか？
できれば(1)の添削もお願いします。
|
No.21282 - 2013/04/29(Mon) 03:09:24
| ☆ Re: 整数問題 / IT | | | (2)は、
k=1,2,3,...,nについてx(k)=Σ[i=1..k]a(i)と考えれば、(1)が使えるのでは？
|
No.21283 - 2013/04/29(Mon) 04:55:56 |
| ☆ Re: 整数問題 / ktdg | | | No.21290 - 2013/04/30(Tue) 09:16:17 |
|
