平成１４年９月２１日

[流れ星]

　　　　　　　　第10４回数学的な応募問題解答その２

　　　　　　　　　　＜解答募集期間：９月１日〜９月２１日＞

［等比数列］

　　　

太郎さんは、１から１００までの整数（１も１００も含めて）から異なるＮ個を選んで等比数列を作るとき、その作り方が何通りあるか考えてみました。ただし、数列は単調増加とします。ここで、問題です。

問題１．Ｎ＝７の場合は何通りあるか。

問題２．Ｎ＝６の場合は何通りあるか。

問題３．Ｎ＝５の場合は何通りあるか。

問題４．Ｎ＝４の場合は何通りあるか。

問題５．Ｎ＝３の場合は何通りあるか。

N01「H7k」さん 　 8/31：13時36分受信　更新9/21
r=2の場合：
N=7:a=1
N=6:a=1,2,3 1-32
N=5:a=1-6 1-16
N=4:a=1-12 1-8
N=3:a=1-25 1-4
r=3の場合：
N=5:a=1
N=4:a=1,2,3
N=3:a=1-11
r=4の場合：
N=4:a=1
N=3:a=1-6
r=5の場合：
N=3:a=1-4
r=3/2の場合
N=5:a=16
N=4:a=8,16,24
N=3:a=4-44(4刻み)
r=4/3の場合
N=4:a=27
N=3:a=9,18,27,36,45,54
r=5/4の場合
N=3:a=16,32,48,64
r=6/5の場合
N=3:a=25,50
r=7/6の場合
N=3:a=36,72
r=8/7の場合
N=3:a=49
以下，簡略表記
r=9/8:N=3:a=64
r=10/9:N=3:a=81
r=5/3:N=3:a=9,18,27,36
r=7/5:N=3:a=25,50
r=9/7:N=3:a=49
r=5/2:N=3:a=4,8,12,16
r=7/4:N=3:a=16,32
r=8/5:N=3:a=25
r=10/7:N=3:a=49
r=7/3:N=3:a=9,18
r=9/5:N=3:a=25
r=7/2:N=3:a=4,8
r=8/3:N=3:a=9

＜水の流れ：コメント＞どのように考えたか　知りたいな。で、ｒ＝６，ｒ＝７，ｒ＝８、ｒ＝９、ｒ＝１０　、ｒ＝９／２，　ｒ＝９／４　、ｒ＝１０／３・・・もあります。

N01「H7k」さん 　 8/31：13時36分と9/1:20時59分受信　更新9/21
そうでしたね．
r=6:N=3:a=1,2
r=7:N=3:a=1,2
r=8:N=3:a=1
r=9:N=3:a=1
r=10:N=3:a=1
r=9/4:N=3:a=16
r=9/2:N=3:a=4
r=10/3:N=3:a=9
これで全部...かな?
> どのように考えたか　知りたいな。
以前，「算数オリンピックに挑戦」(Blue Backs)という本に，各項が100-1000の整数の等比数列で，項数のもっとも多いものを見付けよ．
とかいうような問題があったような記憶があります．(私は算数オリンピックにでたことはないです)

r=p/q (p>q)と書け，項数がNのとき，a=q^(N-1)は条件を満たす等比数列となります．
また，a=k*q^(N-1) (kはk*p^(N-1)が100以下となるような自然数)のも条件を満たす．
あとは調べていっただけです．
N=3:r=k/l (1<=l<k<=10):a=p*l^2 ( p>=1,p*k^2<=100)
N=4:r=k/l (1<=l<k<=4):a=p*l^3 ( p>=1,p*k^3<=100)
N=5:r=k/l (1<=l<k<=3):a=p*l^4 ( p>=1,p*k^4<=100)
N=6,7:r=2:a=p*l^2 ( p>=1,p*k^5 or 6<=100)
通り数の検証を...以下，#{x|(x<p and (x,p)=1) or (x=1)}=phi(p)とおく．

N=3:r=k/l (1<=l<k<=10):a=p*l^2 ( p>=1,p*k^2<=100)
k=2:2^2*26=104より25T
k=3:3^2*12=108より11T,phi(3)=2より計22T
k=4:4^2*7=112より6T,phi(4)=2より計12T
k=5:5^2*5=125より4T,phi(5)=4より計16T
k=6:6^2*3=108より2T,phi(6)=2より計4T
k=7:7^2*3=147より2T,phi(7)=6より計12T
k=8:8^2*2=128より1T,phi(8)=4より計4T
k=9:9^2*2=162より1T,phi(9)=6より計6T
k=10^2*2=200より1T,phi(10)=4より計4T
合計 105通り

N=4:r=k/l (1<=l<k<=4):a=p*l^3 ( p>=1,p*k^3<=100)
k=2:2^3*13=102より12T
k=3:3^3*4=108より3T,phi(3)=2より計6T
k=4:4^3*2=128より1T,phi(4)=2より計2T
合計 20通り

N=5:r=k/l (1<=l<k<=3):a=p*l^4 ( p>=1,p*k^4<=100)
k=2:2^4*7=112より6T
k=3:3^4*2=162より1T,phi(3)=2より計2T
合計 8通り

N=6:r=2:a=p*l^2 ( p>=1,p*2^5 <=100)
2^5*4=128より3T
合計 3通り

N=6:r=2:a=p*l^2 ( p>=1,p*2^6 <=100)
これは2^6*2=64より1通りのみ．

一般的に，1〜tの範囲の等比数列でN項のものの通り数は
\sum{k=2}{[\sqrt[N-1]{t}]}\phi(k)\left[\frac{t}{k^{N-1}}\right]
で表されるのでは?
Σ(k=2 to [ (tのN-1乗根) ]) phi(k)*[ t*k^(1-N) ]
([a]はaを超えない最大の整数)

＜水の流れ：コメント＞　> 以前，「算数オリンピックに挑戦」(Blue Backs)という本に， 各項が100-1000の整数の等比数列で，項数のもっとも多いものを見付けよ．
私もそのような問題を読んでいまして、ヒントにはなっています。
一般的に，1〜tの範囲の等比数列でN項のものの通り数は
sum{k=2}{[　sqrt[N-1]{t}]}phi(k)　left[\frac{t}{k^{N-1}}　right]　で表されるのでは?
Σ(k=2 to [ (tのN-1乗根) ]) phi(k)*[ t*k^(1-N) ]　([a]はaを超えない最大の整数)　　誰か検証をお願いします。

NO3「kiyo」さん　　　8/31: 22時00分受信　更新予定9/21

いつもお世話になっています。kiyoです。プログラムを組んでみました。今後とも宜しくお願いします。　
FOR N=3 TO 7
LET  Z=0
 PRINT "N=";N
FOR S=1 TO 25
 FOR R=2 TO 10
 LET  X=S*(R^(N-1))
IF X<101 THEN
 LET  Z=Z+1
 LET  S1=S
 PRINT S1;
 FOR I=2 TO N
LET  S1=S1*R
PRINT S1;
 NEXT I
 PRINT
END IF
 NEXT R
 NEXT S
PRINT
 PRINT Z;"通り"
 PRINT
NEXT N
END

N= 3
 1  2  4
 1  3  9
 1  4  16
 1  5  25
 1  6  36
 1  7  49
 1  8  64
 1  9  81
 1  10  100
 2  4  8
 2  6  18
 2  8  32
 2  10  50
 2  12  72
 2  14  98
 3  6  12
 3  9  27
 3  12  48
 3  15  75
 4  8  16
 4  12  36
 4  16  64
 4  20  100
 5  10  20
 5  15  45
 5  20  80
 6  12  24
 6  18  54
 6  24  96
 7  14  28
 7  21  63
 8  16  32
 8  24  72
 9  18  36
 9  27  81
 10  20  40
 10  30  90
 11  22  44
 11  33  99
 12  24  48
 13  26  52
 14  28  56
 15  30  60
 16  32  64
 17  34  68
 18  36  72
 19  38  76
 20  40  80
 21  42  84
 22  44  88
 23  46  92
 24  48  96
 25  50  100

 53 通り

N= 4
 1  2  4  8
 1  3  9  27
 1  4  16  64
 2  4  8  16
 2  6  18  54
 3  6  12  24
 3  9  27  81
 4  8  16  32
 5  10  20  40
 6  12  24  48
 7  14  28  56
 8  16  32  64
 9  18  36  72
 10  20  40  80
 11  22  44  88
 12  24  48  96

 16 通り

N= 5
 1  2  4  8  16
 1  3  9  27  81
 2  4  8  16  32
 3  6  12  24  48
 4  8  16  32  64
 5  10  20  40  80
 6  12  24  48  96

 7 通り

N= 6
 1  2  4  8  16  32
 2  4  8  16  32  64
 3  6  12  24  48  96

 3 通り

N= 7
 1  2  4  8  16  32  64

 1 通り

＜水の流れ：コメント＞　>公比のＲが整数だとすれば正解ですが、有理数も考えてください。

NO3「kiyo」さん　　　9/1：0時11分受信　更新予定9/21
こんばんは。kiyoです。早とちりでした。今後とも宜しくお願いします。

   N= 3
   1   2   4
   1   3   9
   1   4  16
   1   5  25
   1   6  36
   1   7  49
   1   8  64
   1   9  81
   1  10 100
   2   4   8
   2   6  18
   2   8  32
   2  10  50
   2  12  72
   2  14  98
   3   6  12
   3   9  27
   3  12  48
   3  15  75
   4   6   9
   4   8  16
   4  10  25
   4  12  36
   4  14  49
   4  16  64
   4  18  81
   4  20 100
   5  10  20
   5  15  45
   5  20  80
   6  12  24
   6  18  54
   6  24  96
   7  14  28
   7  21  63
   8  12  18
   8  16  32
   8  20  50
   8  24  72
   8  28  98
   9  12  16
   9  15  25
   9  18  36
   9  21  49
   9  24  64
   9  27  81
   9  30 100
  10  20  40
  10  30  90
  11  22  44
  11  33  99
  12  18  27
  12  24  48
  12  30  75
  13  26  52
  14  28  56
  15  30  60
  16  20  25
  16  24  36
  16  28  49
  16  32  64
  16  36  81
  16  40 100
  17  34  68
  18  24  32
  18  30  50
  18  36  72
  18  42  98
  19  38  76
  20  30  45
  20  40  80
  21  42  84
  22  44  88
  23  46  92
  24  36  54
  24  48  96
  25  30  36
  25  35  49
  25  40  64
  25  45  81
  25  50 100
  27  36  48
  27  45  75
  28  42  63
  32  40  50
  32  48  72
  32  56  98
  36  42  49
  36  48  64
  36  54  81
  36  60 100
  40  60  90
  44  66  99
  45  60  80
  48  60  75
  49  56  64
  49  63  81
  49  70 100
  50  60  72
  50  70  98
  54  72  96
  64  72  81
  64  80 100
  72  84  98
  81  90 100

105通り
--------------------

   N= 4
   1   2   4   8
   1   3   9  27
   1   4  16  64
   2   4   8  16
   2   6  18  54
   3   6  12  24
   3   9  27  81
   4   8  16  32
   5  10  20  40
   6  12  24  48
   7  14  28  56
   8  12  18  27
   8  16  32  64
   9  18  36  72
  10  20  40  80
  11  22  44  88
  12  24  48  96
  16  24  36  54
  24  36  54  81
  27  36  48  64

 20通り
--------------------

   N= 5
   1   2   4   8  16
   1   3   9  27  81
   2   4   8  16  32
   3   6  12  24  48
   4   8  16  32  64
   5  10  20  40  80
   6  12  24  48  96
  16  24  36  54  81

  8通り
--------------------

   N= 6
   1   2   4   8  16  32
   2   4   8  16  32  64
   3   6  12  24  48  96

  3通り
--------------------

   N= 7
   1   2   4   8  16  32  64

  1通り

NO4「jun」さん　　　 8/31：23時14分受信　　　　　　　　更新予定9/21

第１０４回の問題を考えました。なかなか奥が深いですねえ。
問題１　　１通り
問題２　　３通り
問題３　　８通り
問題４　　２０通り
問題５　　１０５通り　　でどうでしょう？
計算間違い（数え間違い）をしていそうです。
でも、問題５の答えが１００通り以上もあるなんて、すごい！予想外ですよね。

NO5「ｽﾓｰｸﾏﾝ」さん 9/01：19時12分受信　　　　　　　　更新予定9/21

1、2＾7=128＞100だから、公比は1しかない。
よって、100こ。
2、2＾6=64、3＾6＞100だから、公比は、1と2が存在する。
公比1は面白くないので、公比2の時を考えると、初項は1しか
あり得ないので、（∵2＾7＞100）1こ！+100
3、2＾5=32、3＾5＞100なので、初項が1と2と3（3*32=94＜100
）の3こ！+100
4、2＾4=16、3＾4=81、4＾4＞100なので、5＜100/16＜6から、5
こと、1＜100/81＜2から、1こで、あわせて6こ。+100
5、2＾3=8、3＾3=27、4＾3=64、5＾3＞100なので、12＜100/8
＜13，3＜100/27＜4、1＜100/64＜2から、あわせて、16こ。+100
6、2＾2=4、3＾2=9、5＾2=25、6＾2=36、7＾2=49、8＾2=64、9
＾2=81、10＾2=100から、25+11+2+2+1+1+1=43　+100　となる 。　以上。面白かったです。
＜水の流れ：コメント＞　>公比のＲが整数だとすれば正解ですが、有理数も考えてください。また、異なる整数ですから、同じ整数は２回と並べませんよ。

NO6「浜田」さん 　9/03：13時15分受信　　　　　　　　更新予定9/21

問題１．１通り
問題２．３通り
問題３．８通り
問題４．２０通り
問題５．１０５通り

エクセルのマクロ（実行するには，シート１〜５が必要です）
Option Explicit
Sub Macro1()
    Dim N As Integer
    Dim r(1) As Integer
    Dim a(8) As Integer
    Dim gcd As Integer
    For N = 7 To 3 Step -1
      Sheets("Sheet" & (8 - N)).Select
      Cells(1, 1).Value = 0
      Range("A1").Select
      a(1) = 1
      While a(1) <= 100 - (N - 1)
        a(2) = a(1) + 1
        While a(2) <= 100 - (N - 2) 'a(2)=r*a(1)
          r(0) = a(1)
          r(1) = a(2)
gcd = GCM(r(0), r(1))
          r(0) = r(0) / gcd
          r(1) = r(1) / gcd
          Call check(N, 3, r(), a())
          a(2) = a(2) + 1
        Wend
        a(1) = a(1) + 1
      Wend
    Next N
End Sub
Sub check(ByVal N As Integer, ByVal m As Integer, ByRef r() As Integer, ByRef a() As Integer)
    Dim j As Integer
    If (r(1) * a(m - 1)) Mod r(0) = 0 Then
      a(m) = r(1) * a(m - 1) / r(0)
      If a(m) <= 100 Then
        If m < N Then
          Call check(N, m + 1, r(), a())
        Else
          Cells(1, 1).Value = Cells(1, 1).Value + 1
          For j = 1 To N
            Cells(Cells(1, 1).Value, j + 2).Value = a(j)
          Next j
          For j = 1 To 2
            Cells(Cells(1, 1).Value, N + j + 3).Value = r(2 - j)
          Next j
        End If
      End If
    End If
End Sub
Private Function GCM(ByVal a As Integer, ByVal b As Integer) As Integer
    If b = 0 Then
      GCM = a
    Else
      GCM = GCM(b, a Mod b)
    End If
End Function

ＰＳ．「For N = 7 To 3 Step -1」の「N = 7」を「N = 8」とし，シート０を用意すれば，Ｎ＝８のときに解がないことを示すことが出来る．

ＰＳ．全回の問題で，傾きの定義と微分を使って示す方法は思いつきませんでした．

ＰＳ．いつも気になっているのですが，
　「皆さん、考え方がわかったら、全部でなくていいですから、とペンネームを添えて、メールで送ってください。待っています。」
「・・・、とペンネームを・・・」には，「解答」が抜けているのですよね？

＜水の流れ：コメント＞　以後の回から、ご指摘のようにします。「エクセル」での表は勝手ながら、省略させてもらいます。ご了解願います。

　NO7「BossF」さん 9/05：08時03分受信　　　　　　　　更新予定9/21

等比数列　　　太郎さんは、１から１００までの整数（１も１００も含めて）から異なるＮ個を選んで等比数列を作るとき、その作り方が何通りあるか考えてみました。ただし、数列は単調増加とします。ここで、問題です。

[解]

等比数列の一般項は、初項=a 公比=r として　an=ar^n-1とかけます。

また、求める等比数列は、題意より　　a∈{自然数} です。　以下文字は r 以外全て自然数とします

 また、 「単調増加」は、異なる数を選ぶから、狭義である　i.e. r>1 であることに注意します。

また、a=k・ｐ^ｑのとき、ｒ =s/p (p<ｓかつ、互いに素)とすると、

aq+1=k・s^ｑまで整数が続くことにも注意します。…�@　　　(例；a=2^ｑ、ｒ=3/2 とすると、q+1項=3^ｑ)

さて

3≦N≦7で、 r ≧2 ですので、まず２乗〜６乗までの100以下最大の累乗数を求めておきますと、

2⁶=64, 3⁴=81, 4³=64, 5^２=25, 6^２=36, … , 10^２=100…�A

以下�@�Aに注意して問題を解きます

視察により

問題1　N=7 のとき　(a,r)=(1,2) 　　　　　一通り…答

問題2　N=6 のとき　(a,r)=(1,2),(2,2)　 　二通り…答

問題3　N=5 のとき　

(a,r)=(1,2),(2,2),(3,2),(4,2),(5,2),(6,2),(1,3),(16,3/2)

　　　　　　　　　　　　　　　　　　　　　　　　 八通り…答

ここからは、ちょっと計算

問題4　N=4 のとき　

a4=k・s³≦100 を満たす、(k,s)を考えますと

s³≦100 が必要ですから s≦4

s=4 なら k=1 で　p=1,3

s=3 なら k=1,2,3 で　p=1,2

s=2 なら 1≦k≦12 で　p=1

したがって、1x2+3x2+1x12=20通り…答

問題5　N=3 のとき　

問題4と同様に

a3=k・s²≦100 を満たす、(k,s)を考えますと

s²≦100 が必要ですから s≦10

s=10 なら k=1 で　p=1,3,7,9

s=9   なら k=1 で　p=1,2,4,5,7,8

s=8   なら k=1 で　p=1,3,5,7

s=7 なら k=1,2 で　p=1,2,3,4,5,6

s=6 なら k=1,2 で　p=1,5

s=5 なら 1≦k≦4 で　p=1,2,3,4

s=4 なら 1≦k≦6 で　p=1,3

s=3 なら 1≦k≦11で　p=1,2

s=2 なら 1≦k≦25で　p=1

したがって

1x4+1x6+1x4+2x6+2x2+4x4+6x2+11x2+25x1=105通り…答

NO8「VILL」さん 9/07：18時03分受信　　　　　　　　更新予定9/21　　　

VILLと申します。第１０４回の私の解答です。

求める等比数列を，初項を a，公比 ｒ とします。一般項は，　ａｎ＝ａ×ｒ＾n-1　(１≦ｎ≦Ｎ)です。
問題から，ａ，ａｎ は１００までの自然数です。このことから，ｒ は１より大きい有理数です。
そこで，　ｒ＝ｈ/ｋ　(ｈ と ｋ は互いに素な自然数，１≦ｋ＜ｈ)とします。これより，一般項は，ａｎ＝ａ×ｈ＾n-1/ｋ＾n-1ですね。
さて，ａ×ｈ＾Ｎ-1/ｋ＾Ｎ-1≦１００　を満たすものを数えるわけですが，左辺は１００までの自然数なので，ａ が ｋ＾n-1 を因数にもたないといけません。
そこで，　a＝ｍ×ｋ＾Ｎ-1 (ｍは自然数)　としまして，
 ａ×ｈ＾Ｎ-1/ｋ＾Ｎ-1＝ｍ×ｈ＾Ｎ-1≦１００
を考えていきます。(結局，どの文字数も自然数で縛りたかっただけです。(苦笑))

問題１　N＝７のとき， ａ×ｈ＾７-1/ｋ＾７-1＝ａ×ｈ＾６/ｋ＾６＝ｍ×ｈ＾６≦１００ を考えます。　
�@）ｈ＝２のとき…２＾６×ｍ≦１００，ｍ≦１と９/１６　よって１通り。
このとき，ｋ＝１ なので１×１＝１(通り)。
�A）ｈ≧３のちきは，ｈ＾６＞１００ となるので不適。　以上より，１通り。

問題２　Ｎ＝６のとき，ａ×ｈ＾６-1/ｋ＾６-1＝ａ×ｈ＾５/ｋ＾５＝ｍ×ｈ＾５≦１００ を考えます。
�@）ｈ＝２のとき…２＾５×ｍ≦１００，ｍ≦３と１/８　よって３通り。
このとき，ｋ＝１ なので３×１＝３(通り)。
�A）ｈ≧３のときは，ｈ＾５＞１００となるので不適。　以上より，３通り。

問題３　Ｎ＝５のとき，ａ×ｈ＾５-1/ｋ＾５-1＝ａ×ｈ＾４/ｋ＾４＝ｍ×ｈ＾４≦１００ を考えます。
�@）ｈ＝２のとき…２＾４×ｍ≦１００，ｍ≦６と１/４　よって６通り。
このとき，ｋ＝１ なので６×１＝６(通り)。
�A）ｈ＝３のとき…３＾４×ｍ≦１００，ｍ≦１と１９/８１　よって１通り。
このとき，ｋ＝１ ，２なので１×２＝２(通り)。
�B）ｈ≧４のときはｈ＾４＞１００となり不適。　　　以上より，６＋２＝８(通り)。

問題４　Ｎ＝４のとき，ａ×ｈ＾４-1/ｋ＾４-1＝ａ×ｈ＾３/ｋ＾３＝ｍ×ｈ＾３≦１００ を考えます。
�@）ｈ＝２のとき…２＾３×ｍ≦１００，ｍ≦１２と１/２　よって１２通り。
このとき，ｋ＝１ なので１２×１＝１２(通り)。
�A）ｈ＝３のとき…３＾３×ｍ≦１００，ｍ≦３と１９/２７　よって３通り。
このとき，ｋ＝１，２ なので３×２＝６(通り)。
�B）ｈ＝４のとき…４＾３×ｍ≦１００，ｍ≦１と９/１６　よって１通り。
このとき，ｋ＝１，３ なので１×２＝２(通り)。
�B）ｈ≧５のときはｈ＾３＞１００となり不適。　　以上より，１２＋６＋２＝２０(通り)。

問題５　Ｎ＝３のとき，ａ×ｈ＾３-1/ｋ＾３-1＝ａ×ｈ＾２/ｋ＾２＝ｍ×ｈ＾２≦１００　を考えます。
�@）ｈ＝２のとき…２＾２×ｍ≦１００，ｍ≦２５　よって２５通り。
このとき，ｋ
＝１ なので２５×１＝２５(通り)。
�A）ｈ＝３のとき…３＾２×ｍ≦１００，ｍ≦１１と１/９　よって１１通り。
このとき，ｋ＝１，２ なので１１×２＝２２(通り)。
�B）ｈ＝４のとき…４＾２×ｍ≦１００，ｍ≦６と１/４　よって６通り。
このとき，ｋ＝１，３ なので６×２＝１２(通り)。
�C）ｈ＝５のとき…５＾２×ｍ≦１００，ｍ≦４　よって４通り。
このとき，ｋ＝１，２，３，４ なので４×４＝１６(通り)。
�D）ｈ＝６のとき…６＾２×ｍ≦１００，ｍ≦２と７/９　よって２通り。
このとき，ｋ＝１，５ なので２×２＝４(通り)。
�E）ｈ＝７のとき…７＾２×ｍ≦１００，ｍ≦２と２/４９　よって２通り。
このとき，ｋ＝１，２，３，４，５，６ なので２×６＝１２(通り)。
�F）ｈ＝８のとき…８＾２×ｍ≦１００，ｍ≦１と９/１６　よって１通り。
このとき，ｋ＝１，３，５，７ なので１×４＝４(通り)。
�G）ｈ＝９のとき…９＾２×ｍ≦１００，ｍ≦１と１９/８１　よって１通り。
このとき，ｋ＝１，２，４，５，７，８ なので１×６＝６(通り)。
�H）ｈ＝１０のとき…１０＾２×ｍ≦１００，ｍ≦１　よって１通り。
このとき，ｋ＝１，３，７，９ なので１×４＝４(通り)。
�I）ｈ≧１１のときはｈ＾２＞１００となり不適。
以上より，２５＋２２＋１２＋１６＋４＋１２＋４＋６＋４＝１０５(通り)。

＜自宅＞　　mizuryu@aqua.ocn.ne.jp