2021年東工大第3問の誘導を除いた解法

お久しぶりです。修論とかが忙しくて更新できていませんでした。ちなみに今は修論を英語にして国際誌に出す作業があったり、そのあともしばらくも忙しいのでまとまった更新は6月以降くらいになりそうです。

とりあえずそんなこんなですが、今年の東工大の入試が誘導を抜くと割と整数の典型問題でなく、かつそこそこ有用性の高い素数の性質を使う問題だなと思って久しぶりに記事を書こうと思いました。

まず問題はこれです。

ようは2nCn/(n+1)が整数になるnを求めたら良いです。

これ、この誘導で(a_(n+1))/a_nを求めて整数になる性質をうんぬんかんぬんすればできるんだなってことが後で少し考えたらわかりましたが、ではこの誘導を除いたら比率を考えてもあまり割り切れる的な性質がなくて考えづらくないかって思いました。

しかしながら、2n Cnの形を思い出すとこの値を素因数分解したとき、2n以下の素数しか出てこないっていうふうになります。

あとは2n Cnはnを大きくすると2n(n+1)より大きくなるので小さい値をしらみつぶししたら解けます。

一般的にコンビネーションがらみの整数の問題は素数pで何回割り切れるかみたいな考え方を使うことが主なので、コンビネーションの評価と素数の合成数である性質というより「素数pとしたらp未満の整数はpの倍数にならない」みたいな性質を使ってて面白いなと思いました。

答えはこちらです。