(1) 異なるn+1個の整数のうち, 適当な2個を選べば、その差がnの
(2) 30, 300, 330, 3000, 3300, ………, 33333330 という最高位から3が
武
例 題 272 部屋割り論法
倍数になることを示せ。
のがあることを示せ、
考え方 部屋割り論法を利用する。
(1) n+1個の数を a, az, …, an, an+1 とする。
これらをnで割った余りを,それぞれ れ,ra, …,
Yn, Pu+1 とすると,れ,ra,…, Yn+iはすべて0以上
の カー1以下のn個の整数のいずれかである。
解答
nで割ったときの
rは、
0Sr<n
部屋割り論法
したがって, n+1個の余り r, r2, *", Tn+1の中に
は、少なくとも同じ値が2つある。
ここで、その2つを r, 」とおくと、
a=nk+r, a;=nkj+r」(Ri, kjは整数)
より,a-a=n(k-k))+r-n=n(k-k)
よって、a; とajの差はnの倍数である。
0~n-1はn個
=r」
(2)(1)より,8個の数
3, 33, 333, 3333, 33333,
0- 333333, 3333333, 33333333
のうち7で割った余りが等しいものが少なくとも2
つ存在する。
その2つの数の大きい方から小さい方を引くと7 Ss
(1)を利用する。
ケの倍数であり、33…30…0の形をしているから題意は
示された。
SST
OT
日 お ISIS Teる
Focus
ない
n+1個のものを,n組に分けるとき,
2個以上が入っている組が少なくとも1つ存在する
(部屋割り論法)
