|
投稿者：山中和義
投稿日：2015年 3月 8日(日)10時42分50秒
|
|
|
|
問題 平成27年度 東京大学入試 前期理系
mを2015以下の正の整数とする。 C(2015,m)が偶数となる最小のmを求めよ。
考察
実際の値を求めると、多桁の整数の計算になってしまう。
OPTION ARITHMETIC RATIONAL
LET N=2015
FOR M=1 TO N
IF MOD(COMB(N,M),2)=0 THEN EXIT FOR
NEXT M
PRINT M
END
（終わり）
答え
C(n,m)=P(n,m)/m!=(n/1)×((n-1)/2)×((n-2)/3)× … ×((n-m+1)/m)より、
(n-m+1)/mをかけていくことは、C(n,1)、C(n,2)、C(n,3)、… を得ていることである。
C(2015,m)
=(2015/1×2014/2×2013/3×2012/4×2011/5×2010/6×…×(2015-m+1)/m
=(2015/1×2013/3×2011/5×…)×(2014/2×2012/4×2010/6×…×(2015-m+1)/m)
と変形して、素因数2でのみ約分すると、
=(2015/1×2013/3×2011/5×…)×(1007/1×503/1×1005/3×…×(2015-m+1)/m)
C(n,m)は整数より、分母に残した奇数は、どこかの分子を割り切り、新しい奇数の分子をつくる。
したがって、
奇数×奇数=奇数
奇数×偶数=偶数
から、上記の計算過程で偶数の分子を見つければよい。
(n-m+1)/mは、奇数/奇数と偶数/偶数の繰り返しなので、分母が偶数のときのみ約分して、
2014/2×2012/4×2010/6×2008/8×2006/10×2004/12×2002/14×2000/16
×1998/18×1996/20×1994/22×1992/24×1990/26×1988/28×1986/30×1984/32
=1007/1×503/1×1005/3×251/1×1003/5×501/3×1001/7×125/1
×999/9×499/5×997/11×249/3×995/13×497/7×993/15×62/1
から、m=32
（終わり）
補足
2014/2、2012/4、2010/6、… は、2進法表記では、偶数は下位が0であるので、
分子と分母のそれぞれの0の個数に注意すればよい。
n-m+1 m 2進法表記
----------
2015 1 11111011111 1
2014 2 11111011110 10 ← 相殺される
2013 3 11111011101 11
2012 4 11111011100 100 ← 相殺される
2011 5 11111011011 101
2010 6 11111011010 110 ← 相殺される
：
1986 30 11111000010 11110 ← 相殺される
1985 31 11111000001 11111
ここまで、相殺されるが、
1984 32 11111000000 100000
ここで、1個多くなる。
OPTION ARITHMETIC RATIONAL
LET N=2015
FOR M=1 TO N
LET G=GCD(N-M+1,M)
IF MOD((N-M+1)/G,2)=0 THEN EXIT FOR
NEXT M
PRINT M
END
●C(n,m) mod p の計算
OPTION ARITHMETIC RATIONAL
LET N=2015
LET P=2
PRINT 1; !C(n,0)=1
DIM D(N) !約分された分子
FOR M=1 TO N !(n-m+1)/mをかける
LET D(M)=N-M+1
LET T=M !約分する
FOR J=1 TO M
LET G=GCD(D(J),T)
LET D(J)=D(J)/G
LET T=T/G
IF T=1 THEN EXIT FOR !分母が1になったなら
NEXT J
LET T=1
FOR J=1 TO M
LET T=MOD(T*D(J),P) !mod p
NEXT J
PRINT T;
NEXT M
PRINT
END
その２
LET N=2015
LET P=2
DIM C(0 TO N) !C(n,m)
FOR M=0 TO N !(1+x)^mの展開、パスカルの三角形のk段
LET C(M)=1
FOR J=M-1 TO 1 STEP -1
LET C(J)=MOD(C(J-1)+C(J),P) !mod p
NEXT J
NEXT M
MAT PRINT C;
END
0段目から2015段目までを計算するので、多少時間を要する。
参考 二項係数、パスカルの三角形、シェルピンスキーのギャスケット
|
|
|