一橋大学　 2021年　問題1


$1000\ 以下の素数は \ 250\ 個以下であることを示せ。$


$(解説)$

$\ \ 1000\ 以下の自然数から、2\ の倍数、\ 3\ の倍数,\ 5\ の倍数、\cdots を順次取除いていくと素数が残ります。$
$\ \ この方法を「エラトステネスのふるい」といいます。 $


(1)


$U=\{1,\ 2,\ \cdots,\ 1000\}\ とし、その部分集合で、2\ の倍数、3\ の倍数、5\ の倍数の集合をそれぞれ \ A,\ B,\ C\ とする。$

$\quad n(A)=\big[\cfrac{1000}{2}\big]=500,\qquad n(B)=\big[\cfrac{1000}{3}\big]=333,\qquad n(C)=\big[\cfrac{1000}{5}\big]=200$

$\quad n(A \cap B)=\big[\cfrac{1000}{6}\big]=166,\qquad n(B \cap C)=\big[\cfrac{1000}{15}\big]=66,\qquad n(C \cap A)=\big[\cfrac{1000}{10}\big]=100$

$\quad n(A \cap B \cap C)=\big[\cfrac{1000}{30}\big]=33$

$したがって$

\begin{eqnarray*} n(\overline{A} \cap \overline{B} \cap\overline{C}) &=&n(\overline{A \cup B \cup C})\\ \\ &=&n(U)-n(A \cup B \cup C)\\ \\ &=&n(U)-\big\{n(A)+n(B)+n(C)-n(A \cap B)-n(B \cap C) - n(C \cap A)+ n(A \cap B \cap C)\big\}\\ \\ &=&1000-500-333-200+166+66+100-33\\ \\ &=&266 \end{eqnarray*}

$次に、この中には \ 7\ の倍数が入っているので、それを除きます。$

$Uの中の \ 7\ の倍数は \ \ 7 \times １,\quad 7 \times 2,\quad \cdots ,7 \times 142 \ \ がある。$

$U'=\{1,\ 2,\ \cdots ,\ 142\}\ \ とし、その部分集合で、2\ の倍数、3\ の倍数、5\ の倍数の集合をそれぞれ \ A',\ B',\ C'\ とする。$

$\quad n(A')=\big[\cfrac{142}{2}\big]=71,\qquad n(B')=\big[\cfrac{142}{3}\big]=47,\qquad n(C')=\big[\cfrac{142}{5}\big]=28$

$\quad n(A' \cap B')=\big[\cfrac{142}{6}\big]=23,\qquad n(B' \cap C')=\big[\cfrac{142}{15}\big]=9,\qquad n(C' \cap A')=\big[\cfrac{142}{10}\big]=14$

$\quad n(A' \cap B' \cap C')=\big[\cfrac{142}{30}\big]=4$

$したがって$
\begin{eqnarray*} n(\overline{A'} \cap \overline{B'} \cap\overline{C'}) &=&n(\overline{A' \cup B' \cup C'})\\ \\ &=&n(U')-n(A' \cup B' \cup C')\\ \\ &=&n(U')-\big\{n(A')+n(B')+n(C')-n(A' \cap B')-n(B' \cap C') - n(C' \cap A')+ n(A' \cap B' \cap C')\big\}\\ \\ &=&142-71-47-28+23+9+14-4\\ \\ &=&38 \end{eqnarray*}

　
$したがって、1000\ 以下の素数は、1\ を除き、$
$2,\ 3,\ 5,\ 7\ を加えて $

$\quad 266-38-1+4=231\ 個以下であるから$

$\quad 250\ 個以下であることが示された。$

$実際には、この中からさらに \ 11,\ 13,\ 17,\ \cdots $
$の倍数を除かなくてはならない。$

$右の表はExcel \ VBA \ で \ 1000\ 以下の素数を$
$求めたもので全部で、168\ 個ある。$


$(研究)$

$4\ つの集合の和集合(結び)の要素の個数については \qquad n(A)=|A|\ \ で表すと$

$\quad |A\cup B \cup C \cup D|=|A|+|B|+|C|+|D|-|A \cap B|-|A \cap C|-|A \cap D|-|B \cap C|-|B \cap D|-|C \cap D|$
$\hspace{9em} +|A \cap B \cap C|+|A \cap B \cap D|+|A \cap C \cap D|+|B \cap C \cap D|-|A \cap B \cap C \cap D|$

$\qquad このことについては \ ($n個の集合の和集合の要素の個数$)\ を参考にしてください。$

$上に加えて \ 7\ の倍数の集合を \ D\ とおくと$

$\quad |D|=\big[\cfrac{1000}{7}\big]=142,\qquad |A \cap D|=\big[\cfrac{1000}{14}\big]=71,\qquad |B \cap D|=\big[\cfrac{1000}{21}\big]=47,\qquad |C \cap D|=\big[\cfrac{1000}{35}\big]=28$

$\quad |A \cap B \cap D)=\big[\cfrac{1000}{42}\big]=23,\qquad |A \cap C \cap D)=\big[\cfrac{1000}{70}\big]=14,\qquad |B \cap C \cap D)=\big[\cfrac{1000}{105}\big]=9$

$\quad |A \cap B \cap C \cap D)=\big[\cfrac{1000}{210}\big]=4$


$よって$

\begin{eqnarray*} & &|\overline{A} \cap \overline{B} \cap \overline{C} \cap \overline{D}|\\ \\ &=&|\overline{A \cup B \cup C \cup D}|\\ \\ &=&|U|-|A \cup B \cup C \cup D|\\ \\ &=&|U|-|A|-|B|-|C|-|D|+|A \cap B|+|A \cap C|+|A \cap D|+|B \cap C|+|B \cap D|+|C \cap D|\\ \\ & & \hspace{3em} -|A \cap B \cap C|-|A \cap B \cap D|-|A \cap C \cap D|-|B \cap C \cap D|+|A \cap B \cap C \cap D|\\ \\ &=&1000-500-333-200-142+166+100+71+66+47+28-33-23-14-9+4\\ \\ &=&228\\ \end{eqnarray*}
$したがって、1000\ 以下の素数は、1\ を除き、2,\ 3,\ 5,\ 7\ を加えて \qquad 228-1+4=231\ 個以下$



ページの先頭へ↑




メインメニュー　に戻る