Evolton
方針
(1) は各素数について、 のどれを割るかを比較する。 は指数を無視して「その素数が現れるか」だけを見る関数なので、素数ごとに左辺と右辺で現れる回数をそろえればよい。(2) は (1) により条件を 、 に移し、 から までの番号について最大公約数の型を表で数える。
解答
(1)
素数 を1つ固定する。 が を割るかどうか、 を割るかどうかで場合を分ける。 が のどちらも割らないとき、 は のいずれの にも現れない。 が のちょうど一方だけを割るとき、 は には現れず、 には現れる。したがって左辺 に は1回現れる。一方、右辺 にも は1回現れる。 が の両方を割るとき、 は にも にも現れるので、左辺には2回現れる。右辺でも と の両方に現れるので2回現れる。
以上より、すべての素数 について、左辺と右辺に現れる回数が一致する。したがって である。
(2)
(1) より である。ただし は の最大公約数である。
まず となるのは のとき、すなわち のときである。これは が互いに素であることを意味する。 のそれぞれについて、 で となる個数を数えるとである。合計は だから 次に となるのは のときである。これは、最大公約数 が2で割り切れ、しかも奇素数では割り切れないことを意味する。つまり は のように、素因数としては2だけをもつ。
同じように ごとに数えるとである。例えば なら、 は偶数で、かつ3を共有してはいけないので の4個である。
合計は だから
別解
解法2（包除原理で100組を数える）
方針
(1) の恒等式から条件を最大公約数 の素因数だけに移す。 は互いに素でない組を共有素数ごとに包除し、 は偶数同士25組から共有する奇素数をもつ組を除く。
解答
(1)
素数 に対し、、 の真偽を で表すとする。 に現れる の指数は、この2つの真偽の和である。一方、 には両方が真のとき、 には少なくとも一方が真のときに が1回現れる。その指数の和は同じである。すべての素数について一致するからである。
(2)
第1の条件は 、すなわち と同値である。 から の2数が共通にもつ可能性のある素数は である。両方がそれぞれの素数の倍数である順序つき組は個である。 と をともに共有する組は 、 と をともに共有する組は の各1個で、それ以外の重なりはない。よって互いに素でない組は個である。したがって第2の条件は と同値である。したがって2数はともに偶数であり、奇素数を共有しない。偶数同士は 組ある。このうち奇素数 を共有するのは 、奇素数 を共有するのは だけである。ゆえに
総評
難度6、計算量6。目安時間は15〜20分。採点ポイントは、(1) で素数ごとの出現回数を比較すること、(2) で条件を直接 から調べず最大公約数 の条件へ変換すること、最後の表を重複なく数えることです。
誤りやすいのは、 を「最大公約数が2」とだけ読んでしまうことです。実際には なども であり、奇素数を共有しないことが本質です。表で数えるときは、 や のように偶数かつ奇素数を含む番号で除外条件を確認すると、数え落としを防げます。
第1解法は標準的な答案構成を詳しく示し、第2解法は異なる着眼または計算経路で同じ結論を独立に確認する。図は条件の役割と解法の流れを可視化した。積分・極限・総和は独立行に置き、分数は表示サイズで組版した。