伊伊伊伊伊伊伊伊伊伊
二項係数についての入試問題から
うら
とし お
裏 俊男
伊伊伊伊伊伊伊伊伊伊
特集 入試問題研究
伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊
伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊
§1．はじめに
過去，その年の西暦年を盛り込んだ入試問題がし
ばしば出題されてきた。今年西暦 2015 年は，
(2015)=(11111011111)
という特徴があった。
これを使ったなんらかの出題があるのではと予想
(期待？) していたが，今年の東大入試の 1 問
m
2015−m
−
−
2015
2 2
2
2015
m
2015−m
+
−
−
2 2
2
2015
m
2015−m
+
−
−
2 2
2
=
+……
と変形し，
C が偶数となる最小の m を求めよ
はこの特徴に関連した出題だった。
[a+b]−[a]−[b]≧0
だから，この各 {
うな最小の m を求める，という考えに導かれる。
§2．解法
この数の特徴を活かせば，
最小のはひとまずお
2015 !
C=
m ! (2015−m) !
いて，
m
2015−m
−
−
2015
0
2 2
2
が 2 の倍数かどうかは，右辺を素因数分解し，素因
数 2 の冪を調べればよい。
数は
([
=(11111100000)−1
因数 p の冪は
=2+2+……+2−1
より，m=2，k=6 のとき
2
=
2015
2
2
=
n
n
−
p
p
∑ k⋅
n
=∑
p
で求められた。
(実際は有限和であり，和をとる範囲 k=1∼∞ の
∞は大げさだが，詳しく書くのも面倒だからそのま
まで…)
したがって，C を素因数分解したときの，素
因数 2 の冪は
2015
2015
+
+
+……
2015
2 2 2
m
m
m
− + + +……
2
2
2
2015−m
−
+ 2015−m
+ 2015−m
+……
2
2
2
2
れる。実際，
] はガウス記号)
であるから，階乗 n ! を素因数分解したときの，素
これは
(2015)=(11111011111)
n
k
となる m の候補として，直ちに m=2 があげら
n 以下の自然数のうち， k の倍数であるものの個
} のいずれかが 0 にならないよ
+2+……+2−1
2
+2 +2 +2 +2
2−1
+
2
2
=2 +2 +2 +2+1
2015−m
= 2
2
2
=
m
2
=0
=
2
2
2 −1
+2 +2 +2
+
2
2
+2+2+2+2−1
2
=2+2+2+2
よって，m=2 とすると，k=6 に対して
m
2015−m
−
−
2015
=10
2 2
2
あとは，m<2 である m に対して，
m
2015−m
−
−
2015
=0
2 2
2
m=2，k=6 のとき
(k=1，2，3，……) (＊)
m
2015−m
−
−
2015
0
2 2
2
となることが§3 のようにして容易にわかるので，
であることも，シフトレジスタにのった 2 進数を思
m=2 が求める答，ということになる。
い浮かべれば簡単だったかもしれない：
2015= 1 1 1 1 1 0 1 1 1 1 1
§3．2 進数とシフトレジスタ
2= 0 0 0 0 0 1 0 0 0 0 0
自然数は計算機の中で， 2 進数の形で扱われる。
2015 は 11 ビットのレジスタによって，
6 ビット右シフトしたところで
1 1 1 1 1 0 1 1 1 1 1
2
2015−2
−
−
2015
0
2
2 2
と表されている。
計算機の中では，
÷2という計算は，レジスタの
中の値を 1 つ右にずらす ( 1 ビット右シフトする)
ことで実現される：
§4．類題
数 n が同様の特徴をもつ場合の C について類
0 1 1 1 1 1 0 1 1 1 1 1 ×
∴
2015−2= 1 1 1 1 0 1 1 1 1 1 1
↑↑
題を考えてみた：
0 1 1 1 1 1 0 1 1 1 1
ここで，最上位のビットには 0 が入り，最下位のビ
ットは捨てられる。÷2なら k 回 ( k ビット) 右
シフトすればよい。すなわち，
C が 3 の倍数となる最小の m を求めよ
答．m=2⋅3=162
(解) (2105)=(2212222) である。
3 進数を格納できるレジスタがあったとすると，
l
=値 l の入ったレジスタを
2
k ビット右シフトしたもの
3l =値 l の入ったレジスタを
さて，m<2 である整数 m は計算機の中で，
0 0 0 0 0 0 m m m m m
k 回右シフトしたもの
であり，
2105= 2 2 1 2 2 2 2
(ただし，各 m=0，1)
2⋅3= 0 0 2 0 0 0 0
と表される。
2015 の 2 進数表現は都合よく下 5 桁はすべて 1 な
ので，2015−m は，
2105−2⋅3= 2 1 2 2 2 2 2
だから， 5 回右シフトすれば，
2⋅3
2105−2⋅3
−
−
2105
0
3 3
3
1 1 1 1 1 0 m′ m′ m′ m′ m′
(ただし，各 m′=1−m)
また，m<2⋅3 とすると
したがって，以下の 3 つのレジスタを同時にどの
m= 0 0 m m m m m
ように k ビット右シフトしようとも，上 2 つのレジ
ただし，m=0，1
スタの和は， 3 つ目のレジスタの値に等しい。
よって，
m= 0 0 0 0 0 0 m m m m m
2015−m
2015= 1 1 1 1 1 0
1
1
1
1
1
m2 + 2015−m
= 2015
2
2
m
2015−m
−
−
2015
=0
2 2
2
((＊) の証明終)
m′=2−m (i=3，2，1，0)
何回右シフトしようとも (k=1，2，3，……)
m3 + 2105−m
= 2105
3
3
すなわち
m，m，m，m=0，1，2
2105−m= 2 2 m′ m′ m′ m′ m′
m′=1−m
= 1 1 1 1 1 0 m′ m′ m′ m′ m′
よって，C⋅ は 3 の倍数である。
と表される。
∴
だから，
m
2105−m
−
−
2105
=0
3 3
3
よって，2⋅3 が求める最小の m である。
(東京都立小山台高等学校)
3
© Copyright 2024 ExpyDoc
