今回は日本数学オリンピック２０１７年予選第２問を取り上げます。
aとbが互いに素というのは、aとbの最大公約数が１ということで、２９！は１から２９までの整数の積のことです。
結局のところ、１×２×３×４×５×・・・×２８×２９の約数のペアで最大公約数が１のものは何ペアあるかという問題にすぎませんね。
もう少し小さい数なら、中学入試に出されても普通に解ける受験生が結構いるでしょう。
さて、問題を解いてみましょう。
２９以下の素数は、２、３、５、７、１１、１３、１７、１９、２３、２９となります（１以上１００以下の素数をエラトステネスのふるいによって書き出したものがあるので、参考にしましょう）。
aとbは２９！の約数のペアで、aが小さい方になります（２９！は平方数ではない（素因数２９の個数が１個であることから明らか）から、aとbが等しくなることはありませんね）。
２９！を素因数分解したときの素因数は上記の２９以下の素数となり、aとbの最大公約数が１だから、それぞれの素因数はa、bの一方のみに配置する必要があります。
その配置の仕方は２の１０乗＝１０２４通りありますが、この中には、a＜bのものとa＞bのものが同じ数だけ含まれているから、答えは１０２４/２＝５１２個となります。
算数オリンピック・ジュニア算数オリンピック・キッズＢＥＥ対策プロ家庭教師
算数オリンピック・ジュニア算数オリンピック・キッズＢＥＥ対策プロ家庭教師のお申込み・ご相談
