整数問題わかりません

質問

2004個の自然数a1,a2,・・・,a2004について
・a1<a2<・・・＜a2004
・2004以下の互いに異なる自然数i,j,kについて
　常にai*aj≠akが成立する

このときa2004のとりうつ値の最小値っていくつですか？

　数学オリンピック予選で解けなかった問題です。
　誰か解答教えて下さい。

回答No.13

keyguy · ベストアンサー

もしかして(1)が理解できないのかもしれないので(1)を詳しく示しましょう。

{1,45,46,47,48,・・・,2047}は明らかに要件を満たすが以下この要素の最大数2047はすべての要件を満たす数の組の最大数以下であることを示す。
要件を満たす数の組(*)を{a,b,c,・・・,y,z}とする。

(0)1<aのとき：
{1,a,b,c,・・・,y}は要件を満たす数の組でありy<zなので(*)の最大数は最小にはなり得ない。

(1)a=1かつb<7のとき：
101,102,103,・・・,144,
b・101,b・102,b・103,・・・,b・144
は互いに異なり100以上1000以下であり
(*)に101とb・101が共には含まれれず
(*)に102とb・102が共には含まれれず
・・・・・・・・・・・・・・・・・・・・・・・・
(*)に144とb・144が共には含まれれず
結局(*)は1000以下の自然数の内少なくとも44個含まれないから
2047<2004+44≦zなので(*)の最大数は最小にはなり得ない。

(2)a=1かつ45<bのとき：
当然2047<2004+44≦zなので(*)の最大数は最小にはなり得ない。

(3)a=1かつ7≦b≦45のとき：
(*)において7以上45以下の要素がn個あり小さい順にα,β,・・・,γとすると
α・β,・・・,α・γは共に互いに異なり46以上2000未満であり
(*)はn-1個のα・β,・・・,α・γを含むことはできないので
(*)は1以上45以下の自然数のうち45-1-n=44-n個(1,α,β,・・・,γ以外の45以下の自然数の個数)の自然数を含まず46以上2000未満の自然数のうちn-1個(α・β,・・・,α・γの個数)の自然数を含まないから
(*)は1以上2000未満の自然数のうち(44-n)+(n-1)=43個の自然数を持たないことになり
2004+43=2047≦zなので(*)の最大数は2047以上である。

(0)と(1)と(2)と(3)以外の場合はなく結局要件を満たす数の組の最大数の最も小さい数は2047といわざるを得ない。

お礼

やっとわかりました。ありがとう♪

回答No.2

liar_adan

これ、「2004個だけ考えればよい」
というところがポイントだと思うんです。

つまり、0～nの間の数を使わないで、
a1=n+1, a2=n+2, ... , a2004=n+2004
とします。
ここで、
(1)…a2004 < a1*a2
とすれば、常に条件が成立します。
(1)を書き換えると
n+2004 < (n+1)*(n+2)
これを解くとnは43コンマいくらより大。(負の方は無視)
つまりnは44以上。
ということで、
a1 = 44+1 = 45
a2 = 44+2 = 46
...
a2004 = 44+2004 = 2048
となって、
a1 * a2 = 2070 > 2048
となります。もちろん、範囲内のどの数をかけても
重複しません。

答はこれで正しいと思うのですが、
証明が面倒で…。
仮に、今出した数列より小さな数列があって条件を満たすとする。
それをbnとし、b2004 < a2004とする。
仮に1つだけ小さいとする。(b2004 + 1 = a2004)
すると、b1, b2はa1, a2よりも少なくとも1つだけ小さい。
だが、b1 * b2 < b2004なので、この数列の間に数が入る。
よって、b1, b2はa1, a2よりも少なくとも2つ小さい。
だが今度b3を考えると…
と増やしてやっていって、ある程度(10個)ぐらいa1より
小さな数が出てくると、それらの組み合わせですでに
44個の空きを使い果たしてしまい、b列がa列より小さいというのに矛盾する…
というふうに証明できると思います。
……上記は自分でもまとまっていないと思いますが、
こんな感じで……。
本式には、数学的帰納法を2段階くらい使ってできると思うのですが。

回答No.1

arukamun

直感的に素数と、素数の２乗の様な気がします。
そうすると、２００４番目は１７１１７になるんですが、回答はあるのでしょうか？