東北大学 1977年 理系 第1問 解説

方針・初手

集合 $A$ は、$1$ から $250$ までの自然数のうち、$4,9,25,\dots$ のような $1$ より大きい平方数で割り切れる数全体である。したがって、平方因子をもつ数を数えればよい。

（1） と （2） は、それぞれ $4$ や $36$ の倍数を数えればそのまま答えになる。

（3） は、$250$ 以下の数のうち、$2^2,3^2,5^2,7^2,11^2,13^2$ のいずれかで割り切れるものを包除原理で数える。

解法1

(1)

$2^2=4$ で割り切れる数は自動的に $A$ の元である。よって、$1$ から $250$ までの $4$ の倍数の個数を数えればよい。

$$ \left\lfloor \frac{250}{4} \right\rfloor = 62 $$

したがって、求める個数は $62$ 個である。

(2)

$2^2$ と $3^2$ で同時に割り切れるとは、$4$ と $9$ の最小公倍数 $36$ で割り切れることと同じである。

$$ \left\lfloor \frac{250}{36} \right\rfloor = 6 $$

したがって、求める個数は $6$ 個である。

(3)

$250$ 以下で平方因子をもつ数を数える。

$250$ 以下で考えるべき素数の平方は

$$ 2^2=4,\quad 3^2=9,\quad 5^2=25,\quad 7^2=49,\quad 11^2=121,\quad 13^2=169 $$

である。$17^2=289>250$ なので不要である。

まず、これらのいずれか $1$ つで割り切れる数の個数の和は

$$ \left\lfloor \frac{250}{4} \right\rfloor +\left\lfloor \frac{250}{9} \right\rfloor +\left\lfloor \frac{250}{25} \right\rfloor +\left\lfloor \frac{250}{49} \right\rfloor +\left\lfloor \frac{250}{121} \right\rfloor +\left\lfloor \frac{250}{169} \right\rfloor $$

$$ =62+27+10+5+2+1=107 $$

ただし、このままでは重複して数えているものがあるので、2つの平方で同時に割り切れるものを引く。

積が $250$ 以下になるものだけを考えればよいから、

$$ 4\cdot 9=36,\quad 4\cdot 25=100,\quad 4\cdot 49=196,\quad 9\cdot 25=225 $$

のみが該当する。したがって重複分は

$$ \left\lfloor \frac{250}{36} \right\rfloor +\left\lfloor \frac{250}{100} \right\rfloor +\left\lfloor \frac{250}{196} \right\rfloor +\left\lfloor \frac{250}{225} \right\rfloor $$

$$ =6+2+1+1=10 $$

である。

なお、3つ以上の異なる素数平方の積の最小は

$$ 4\cdot 9\cdot 25=900>250 $$

であるから、3重以上の重複は存在しない。

よって、包除原理より

$$ |A|=107-10=97 $$

したがって、$A$ の元の個数は $97$ 個である。

解説

この問題の本質は、「$A$ は平方因子をもつ数の集合である」と言い換えることである。

（1） と （2） は、条件そのものが平方因子の存在を保証しているので、単なる倍数の個数に帰着する。

（3） では、平方数すべてを並べるのではなく、素数平方 $4,9,25,\dots$ だけを見れば十分である。合成数の平方因子をもつ場合でも、その中に必ず素数平方因子が含まれるからである。そこで包除原理を用いると、重複を整理して正確に数えられる。

答え

(1)

$62$

(2)

$6$

(3)

$97$