質問<906>2002/8/1
証明せよ。 ①6n+5(n:0以上の整数)の形の素数は無限個存在する。 ②1辺が2cmの正三角形ABCがある。この三角形の内部(3辺の内側) に17個の点をとると、 ある5つのてんの距離は互いに1cmより短くなる。 ③外見が同じ、3のn乗のおもりがあり、そのうち1つだけ重さが違って、 それが重いことがわかっている。 天秤をn回使うと、その1つのおもりを発見できる。 夏休みの宿題なのですが、以上の3問がわかりません・・・(-_-;;) 解き方を教えてほしいです。お願いします。
お便り2002/8/8
from=Tetsuya Kobayashi
(1) 6n+5 型の素数が有限個しかないと仮定し、 その最大のものを p とする。 6n+5 型の素数全ての積に 6 を掛け、5 を足した数を a とする、 すなわち a=6(5*11*...*p)+5 (i) a が素数のとき、a が p より大きい 6n+5 型の素数となる。 (ii) a が合成数のとき、a は 6 で割ると 5 余るので、奇数である。 また、3 で割ると 1 余るので、3 の倍数でない。 したがってその素因数は全て 3 以外の奇数であるから、 6 で割って 1 または 5 余る。 6n+1 型の数をいくらかけても 6n+1 型の数になるので、 6n+5 型の数の素因数の中には必ず 6n+5 型の数がある。 その1つを b とする。 a は 5 から p までの 6n+5 型の素数のいずれによっても 割り切れないから、 b は 5 から p までの 6n+5 型の素数のいずれとも異なる。 したがって、b は p より大きい。 以上(i)(ii)、仮定に矛盾する。 したがって、6n+5 型の素数が無限に存在することが示された。 (2) AB, BC, CA の中点をそれぞれ P, Q, R, とし、線分 PQ, QR, RP を作図すると、 正三角形ABCは4つの領域に分割されます。 (領域の周は共有するものとします。) 正三角形ABCの内部に17個の点を配置すると、鳩の巣箱の原理より、 4つの領域の最低でもいずれか1つには、5個以上の点が配置されて いることになります。 この領域の任意の2点間の距離は1cm未満ですから、含まれる5個以上 の点の距離は互いに1cm未満になります。 その中から任意の5個の点を選んでやれば、その5個の点の距離は 互いに1cm未満になります。 (3) (I) n=1 のとき、 3個のおもりのうち任意の2個をとってきて天秤にかける。 (i) 天秤がつりあっていれば、天秤にかけなかったおもりが問題の おもりである。 (ii) 天秤がつりあっていなければ、下がった台に乗っているおもり が問題のおもりである。 したがって、1 回で発見できる。 (II) n=k のとき成立、すなわち、3^k 個のおもりの中から k 回で発見 できると仮定すると、 n=k+1 のとき、3^(k+1) 個のおもりを 3^k 個ずつの3グループに分ける。 3グループのうち任意の2グループをとってきて天秤にかける。 (i) 天秤がつりあっていれば、天秤にかけなかったグループに問題の おもりがある。 (ii) 天秤がつりあっていなければ、下がった台に乗っているグループに 問題のおもりがある。 ここまで天秤を 1 回使った。問題のおもりがあるグループは 3^k 個の おもりから成立しているので、 仮定より、あと k 回天秤を使えば、問題のおもりが発見できる。 すなわち、k+1 回で発見できるので、n=k+1 でも成立。 以上(I)(II)より、 全ての自然数 n について題意が成立することが示された。