整数問題わかりません

質問

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.12

keyguy

多少不正確な表現で理解できなかったのかもしれません。
では、もっと分かりやすく。

{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以下であり
(*)はこれらのうち少なくとも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である。

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

回答No.11

keyguy

無用な場合わけを1つに統合してさらに分かりやすくしました。

要件を満たす数の組を(*)とし(*)の中の45以下の数を小さい順に
x,a,b,c,・・・,d(n+1個)とする。

(0)1<xのとき：
(*)の最大数を除き1を含めてできる数の組は要件を満たし最大数が(*)の最大数より小さいからこの場合には最大数が最小にはならない。

(1)x=1かつ45≦aのとき：
(*)が{1,45,46,47,48,・・・,2047}のとき最大数が最も小さいことは明白。最大数は2047となる。

(2)x=1かつa<7のとき：
101,102,103,・・・,143,
a・101,a・102,a・103,・・・,a・143
は互いに異なり100以上1000以下であり
(*)はこれらのうち少なくとも43個を含まないから(*)の最大数は2004+43=2047以上である。

(3)x=1かつ7≦a<45
a・b,a・c,・・・,a・dは共に互いに異なり46以上2047未満であり
(*)はn-1個のa・b,a・c,・・・,a・dを含むことはできないので
(*)は1以上45以下の自然数のうち45-1-n=44-n個(1,a,b,c,・・・,d以外の45以下の自然数の個数)の自然数を含まず46以上2000以下の自然数のうちn-1個(a・b,a・c,・・・,a・dの個数)の自然数を含まないから
(*)は1以上2000以下の自然数のうち(44-n)+(n-1)=43個の自然数を持たないことになり
(*)の最大数は2004+43=2047以上である。
(n=1と1<nで場合わけしたほうがいいが煩雑になるので回避しました。）

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

回答No.10

keyguy

一部修正漏れがありました。

1を含まない要件を満たす数の組が有ったとするとその数の組の最大数を除き1を含めてできる数の組は要件を満たし最大数がその数の組より小さいから1を含む数の組の中に最大数が最小になる数の組がある。

以下1を含み要件を満たす数の組を(*)とし(*)について場合わけをして最大数を示す。

(1)
(*)が2以上45未満の数を含まないとき:
(*)が{1,45,46,47,48,・・・,2047}のとき最大数が最も小さいことは明白。最大数は2047となる。
(2)
(*)において1の次に大きい数aが7未満のとき:
101,102,103,・・・,143,
a・101,a・102,a・103,・・・,a・143
は互いに異なり100以上1000以下であり
(*)はこれらのうち少なくとも43個を含まないから(*)の最大数は2004+43=2047以上である。

以下(*)の中の45未満の数を小さい順に
1,a,b,c,・・・,d(n+1個)とする。

(3)
(*)において1の次に大きい数aが7以上45未満であり45を含む場合:
a・b,a・c,・・・,a・d,a・45は共に互いに異なり46以上2047未満であり
(*)はn個のa・b,a・c,・・・,a・d,a・45を含むことはできないので
(*)は1以上45以下の自然数のうち45-2-n=43-n個の自然数(1,a,b,c,・・・,d,45以外の45以下の自然数の個数)を含まず46以上2000以下の自然数のうちn個の自然数(a・b,a・c,・・・,a・d,a・45の個数)を含まないから
(*)は1以上2000以下の自然数のうち(43-n)+n=43個の自然数を持たないことになり
(*)の最大数は2004+43=2047以上である。
(4)
(*)において1の次に大きい数aが7以上45未満であり45を含まない場合:
a・b,a・c,・・・,a・dは共に互いに異なり46以上2047未満であり
(*)はn-1個のa・b,a・c,・・・,a・dを含むことができずまた45も含まないので
(*)は1以上45以下の自然数のうち45-1-n=44-n個の自然数(1,a,b,c,・・・,d以外の45以下の自然数の個数)を含まず46以上2000以下の自然数のうちn-1個の自然数(a・b,a・c,・・・,a・dの個数)を含まないから
(*)は1以上2000以下の自然数のうち(44-n)+(n-1)=43個の自然数を持たないことになり
(*)の最大数は2004+43=2047以上である。

結局要件を満たす数の組の最大数の最も小さい数は2047といわざるを得ない。

回答No.9

keyguy

反応が無いところを見ると(3)と(4)が理解できないと思うのでもう少し丁寧に。

1を含まない要件を満たす数の組が有ったとするとその数の組の最大数を除き1を含めてできる数の組は要件を満たし最大数がその数の組より小さいから1を含む数の組の中に最大数が最小になる数の組がある。

以下1を含み要件を満たす数の組を(*)とし(*)について場合わけをして最大数を示す。

(1)
(*)が2以上44以下の数を含まないとき:
(*)が{1,45,46,47,48,・・・,2047}のとき最大数が最も小さいことは明白。最大数は2047となる。
(2)
(*)において1の次に大きい数aが7未満のとき:
101,102,103,・・・,143,
a・101,a・102,a・103,・・・,a・143
は互いに異なり100以上1000以下であり
(*)はこれらのうち少なくとも43個を含まないから(*)の最大数は2004+43=2047以上である。

以下(*)の中の45未満の数を小さい順に
1,a,b,c,・・・,d(n+1個)とする。

(3)
(*)において1の次に大きい数aが7以上であり45を含む場合:
a・b,a・c,・・・,a・d,a・45は共に互いに異なり46以上2047未満であり
(*)はn個のa・b,a・c,・・・,a・d,a・45を含むことはできないので
(*)は1以上45以下の自然数のうち45-2-n=43-n個の自然数(1,a,b,c,・・・,d,45以外の45以下の自然数の個数)を含まず46以上2000以下の自然数のうちn個の自然数(a・b,a・c,・・・,a・d,a・45の個数)を含まないから
(*)は1以上2000以下の自然数のうち(43-n)+n=43個の自然数を持たないことになり
(*)の最大数は2004+43=2047以上である。
(4)
(*)において1の次に大きい数aが7以上であり45を含まない場合:
a・b,a・c,・・・,a・dは共に互いに異なり46以上2047未満であり
(*)はn-1個のa・b,a・c,・・・,a・dを含むことができずまた45も含まないので
(*)は1以上45以下の自然数のうち45-1-n=44-n個の自然数(1,a,b,c,・・・,d以外の45以下の自然数の個数)を含まず46以上2000以下の自然数のうちn-1個の自然数(a・b,a・c,・・・,a・dの個数)を含まないから
(*)は1以上2000以下の自然数のうち(44-n)+(n-1)=43個の自然数を持たないことになり
(*)の最大数は2004+43=2047以上である。

結局要件を満たす数の組の最大数の最も小さい数は2047といわざるを得ない。

回答No.8

keyguy

1を含まない要件を満たす数の組が有ったとするとその数の組の最大数を除き1を含めてできる数の組は要件を満たし最大数がその数の組より小さいから1を含む数の組の中に最大数が最小になる数の組がある。

以下1を含み要件を満たす数の組を(*)とし(*)について場合わけをして最大数を示す。

(1)
(*)が2以上44以下の数を含まないとき:
(*)が{1,45,46,47,48,・・・,2047}のとき最大数が最も小さいことは明白。最大数は2047となる。
(2)
(*)において1の次に大きい数aが7未満のとき:
101,102,103,・・・,143,
a・101,a・102,a・103,・・・,a・143
は互いに異なり100以上2000以下であり
(*)はこれらのうち少なくとも43個を含まないから(*)の最大数は2004+43=2047以上である。

以下(*)の中の45未満の数を小さい順に
1,a,b,c,・・・,d(n+1個)とする。

(3)
(*)において1の次に大きい数aが7以上であり45を含む場合:
a・b,a・c,・・・,a・d,a・45は共に互いに異なり46以上2047未満であり
(*)はn個のa・b,a・c,・・・,a・d,a・45を含むことはできないので(*)の最大数は2047以上である。
(4)
(*)において1の次に大きい数aが7以上であり45を含まない場合:
a・b,a・c,・・・,a・dは共に互いに異なり46以上2047未満であり
(*)はn-1個のa・b,a・c,・・・,a・dを含むことができずまた45も含まないので(1)の最大数は2047以上である。

結局要件を満たす数の組の最大数の最も小さい数は2047といわざるを得ない。

回答No.7

keyguy

(1,45,46,47,48,・・・,2047)・・・(0)
は要件を満たす
(0)以外で要件を満たす数の組がありその数の組の最小数が1でないとするとその数の組の最大数を取り外し1を取りつけてできる数の組は要件を満たすから1を含む数の組の中に最大数が最小になる数の組がある。
(0)以外で1を含む要件を満たす数の組(1)が有ったとする。
(1)の中の45未満の数を小さい順に
1,a,b,c,・・・,d(n+1個)とすると
aが2以上6以下だとすると
101,102,103,・・・,143,
a・101,a・102,a・103,・・・,a・143
はすべて互いに異なりa以上2047以下であり
(1)はこれらのうち43個の数を取れないから(1)の最大数は2047以上である。
aが7以上だとすると
a・b,a・c,・・・,a・d,a・45は共に互いに異なり46以上2047未満であり
(1)に45が含まれるときには
(1)はn個のa・b,a・c,・・・,a・d,a・45を含むことはできず
(1)に45が含まれていないときには
(1)はn個のa・b,a・c,・・・,a・d,45を含むことができず
(1)の最大数は2047以上である。

回答No.6

keyguy

(1,45,46,47,48,・・・,2047)・・・(*)
は要件を満たす
他に要件を満たす数の組がありその組の最小数が1でないとするとその数の組の最大数を取り1を加えてできた数の組は要件を満たすから1を含む数の組のみを考えれば良い。
(*)以外で1を含む要件を満たす数の組(**)を考え
(**)のなかの45未満の数を小さい順に
1,a,b,c,・・・,d(n+1個)とすると
a・b,a・c,・・・,a・d,a・45はともに2047未満であり
(**)に45が含まれるときには
(**)はn個のこれらの数を含むことはできず
(**)に45が含まれていないときには
(**)はn個のa・b,a・c,・・・,a・d,45を含むことができず
従って(**)の最大数は2047未満にはならない。

回答No.5

keyguy

小さい順に並べて数の組
(1,45,46,47,48,・・・,2047)
よりも数の組の最大値が小さくなるものが無いことを示せば良い。
1の次に大きい数字が2～44である場合
その数とその次に大きい数であって45以下の数との積が2047以下になるので最大値を2047より小さくすることはできない。

回答No.4

kiriburi

a1=1とできます…（異なる自然数1,j,kについて常に1*aj≠akが成立する）

回答No.3

arukamun

No.1は明らかに間違いでした。
No.2の方の方法が理にかなっていますね。