ITエンジニアのブログ

IT企業でエンジニアやってる人間の日常について

nCk が偶数となるkを探すプログラム

東京大学の入試で出題された数学の問題で、 2015Cm が偶数となる最小の自然数 m を求めさせる問題が存在します。

普通に解いても面白いですが、プログラムでも簡単に nCk に拡張して書けそうだなと思いましたので、しばらく書いていなかった Haskell で書いてみました。

nCk が偶数となる最小の自然数 k を、 n に対してそれぞれ求める。

考察

nCkは次のようにかけます。

\displaystyle {}_{n}\mathrm{C}_{k} = \frac{n(n-1) \cdots (n - k + 1)}{k!}

これは、次のようにも表せます。

\displaystyle {}_{n}\mathrm{C}_{k} = \prod_{i = 1}^{k} \frac{n - i + 1}{i}

従って、nC(k-1) がわかっていると、 nCk を少しの計算で求められます。


\displaystyle {}_{n}\mathrm{C}_{k} = {}_{n}\mathrm{C}_{k - 1} \cdot \frac{n - k + 1}{k} \qquad \cdots (*)

これにより、kを1ずつ増やしながら奇偶の判定を行うことができます。

実装

import Control.Monad

maxN = 2020

odds :: [Integer]
odds = [1,3..]

main :: IO ()
main = do
    putStrLn "n: min k [nCk is even]"
    forM_ (take ((maxN + 1) `div` 2) odds) $ \n -> do
        putStrLn $ show n ++ ": " ++ show (loop n 1 1)

loop :: Integer -> Integer -> Integer -> Integer
loop n k t =
    let nt = t * (n - k + 1) `div` k in
    if nt `mod` 2 == 0 then
        k
    else if n <= k then
        -1
    else
        loop n (k + 1) nt

(*) の式を使い、loop で kを1ずつ増やしながら奇偶をチェックしています。偶数となったら k を返せば、nに対して、題意のkを得られます。

補足

実は、 nC(k-1) が奇数の場合、nCk の奇偶は (n - k + 1) / k の奇偶に一致するため、 loop 中の t として保存している nCk の値は必要ないのですが、プログラムの意図を分かりやすくするために敢えて書いています。

これも分かり易さのために省略していますが、 nCk = nC(n-k) であることを考えれば、kはnまででなく、n/2まで調べれば良いこともわかります。

結果

上記プログラムでは 2020 までの奇数を選んで n とし、 最小の k を求めています。

出力の最後の方 (2000 ~) は次の通り、

2001: 2
2003: 4
2005: 2
2007: 8
2009: 2
2011: 4
2013: 2
2015: 32
2017: 2
2019: 4

n = 2015 のとき、題を満たす k は 32 です。

見た感じ、n+1 に素因数2をどれだけ含んでいるかが鍵となりそうです。

また、 n = 2^m - 1 のときは、どれも -1 が出力されていました。つまり k 無し。この辺りで問題も作れそうです。