平成２１年７月２６日

[流れ星]

　　　　　第２２７回数学的な応募問題解答

　　　　　　＜解答募集期間：７月５日〜７月２６日

［既約分数］

皆さん、先日大学入試問題を眺めていたら、近畿大学の過去問から次のような興味ある問題を見つけました。改題してあります。是非、チャレンジください。

考察について、「uchinyan」さんから題意が分かりづらいとご意見を頂きましたから、

出題者の意図をお伝えし、表現を変えてみます。

　まず、意図ですが、１≦ｋ≦１２のとき、但し書きの条件がなければ、集合Ｔの要素の中には同じ値がでてきます。そこで、集合Ｔのすべての要素の個数は、すなわち１４４個ですが、条件をつけた場合のとりうる値の個数は問４の答えですが、その２つの割合をｋを無限大にして考察ください。（全体との比率に変えました）　皆様にご迷惑をおかけしたことを深くお詫びします。

＜7月6日夜記述）

ＮＯ１「uchinyan」 7/05 14時15分受信

「uchinyan」 7/11 11時36分受信 更新7/26

第２２７回数学的な応募問題
［既約分数］

以下では，底が a，真数が b の対数を log_a{b} と書くことにします。

問1：
最小 2^1 = 2，最大 2^12 = 4096

問2：
M = 2^1 * 2^2 * ... * 2^11 * 2^12 = 2^(1 + 2 + ... + 11 + 12) = 2^78
log_2{M} = log_2{2^78} = 78

問3：
log_a{b^2} = 2 * log_a{b} = 2 * log_2{b}/log_2{a}
最後は，底の変換公式を使いました。
ここで，a = 2^m, b = 2^n, m, n は 1 〜 12 の整数，と書け，
log_2{a} = log_2{2^m} = m, log_2{b} = log_2{2^n} = n なので，
log_a{b^2} = 2 * n/m
そこで，
最小 2 * 1/12 = 1/6，最大 2 * 12/1 = 24

問4：
問3：の式変形より，n/m の個数になります。
ただし，同じものは除くので，結局，整数も含めるとして既約分数の個数になります。
そこで，地道に調べると，
m = 1 のとき，1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 の 12 個
m = 2 のとき，1/2, 3/2, 5/2, 7/2, 9/2, 11/2 の 6 個
m = 3 のとき，1/3, 2/3, 4/3, 5/3, 7/3, 8/3, 10/3, 11/3 の 8 個
m = 4 のとき，1/4, 3/4, 5/4, 7/4, 9/4, 11/4 の 6 個
m = 5 のとき，1/5, 2/5, 3/5, 4/5, 6/5, 7/5, 8/5, 9/5, 11/5, 12/5 の 10 個
m = 6 のとき，1/6, 5/6, 7/6, 11/6 の 4 個
m = 7 のとき，1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 8/7, 9/7, 10/7, 11/7, 12/7 の 11 個
m = 8 のとき，1/8, 3/8, 5/8, 7/8, 9/8, 11/8 の 6 個
m = 9 のとき，1/9, 2/9, 4/9, 5/9, 7/9, 8/9, 10/9, 11/9 の 8 個
m = 10 のとき，1/10, 3/10, 7/10, 9/10, 11/10 の 5 個
m = 11 のとき，1/11, 2/11, 3/11, 4/11, 5/11, 6/11, 7/11, 8/11, 9/11, 10/11, 12/11 の 11 個
m = 12 のとき，1/12, 5/12, 7/12, 11/12 の 4 個
そこで，
12 + 6 + 8 + 6 + 10 + 4 + 11 + 6 + 8 + 5 + 11 + 4
= 91 個

(別解)
n/m が既約分数になるかどうかは，n が m と互に素かどうかを調べればいいので，
m 以下の m と互に素な自然数の個数を表すオイラー関数 φ(m) を用いても数えられます，
なお，オイラー関数に関しては，例えば，数学的な応募問題の第157回をご覧ください。
今，a, b が 2^1 〜 2^k までの T の部分集合における既約分数の個数を a(k) 個とします。
このとき，a, b が 2^1 〜 2^(k+1) の場合の a(k+1) を考えます。
・a, b が 2^1 〜 2^k となる場合
明らかに，a(k) 個。
・a = 2^(k+1), b = 2^1 〜 2^(k+1) となる場合
対応するのは，n/m. n = 1 〜 k+1, m = k+1 なので，既約分数は n が m と互に素となる場合で，
φ(m) = φ(k+1) 個，になります。
・a = 2^1 〜 2^(k+1), b = 2^(k+1) となる場合
対応するのは，n/m. n = k+1, m = 1 〜 k+1 なので，既約分数は n が m と互に素となる場合で，
φ(n) = φ(k+1) 個，になります。
以上で場合を尽くしていますが，a = b = 2^(k+1) の場合が重複しています。
しかし，この場合は n = m = k+1, n/m = (k+1)/(k+1) = 1 で，既約分数にならないので，
そもそも上記の個数には入らず，問題にはなりません。
そこで，
a(k+1) = a(k) + 2 * φ(k+1)
つまり，
a(k) = a(k-1) + 2 * φ(k)
になります。ただし，k は 1 以上で a(1) = 1 です。
これより，
a(k) - a(k-1) = 2 * φ(k)
a(k) - a(1) = 2 * Σ[i=2,k]φ(i)
a(k) = a(1) + 2 * Σ[i=2,k]φ(i) = 1 + 2 * Σ[i=2,k]φ(i)
φ(1) = 1 に注意すると，
a(k) = 2 * Σ[i=1,k]φ(i) - 1
とも書けます。
そこで，今は，a(12) を求めればいいので，
a(12) = 2 * Σ[i=1,12]φ(i) - 1
= 2 * (φ(1) + φ(2) + φ(3) + φ(4) + φ(5) + φ(6) + φ(7) + φ(8) + φ(9) + φ(10) + φ(11) + φ(12)) - 1
= 2 * (1 + 1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 + 4 + 10 + 4) - 1
= 2 * 46 - 1
= 91 個
になります。

問5：
log_a{b^2} = 2 * n/m より，a <-> b とすると，log_b{a^2} = 2 * m/n となり，
a と b が等しくないときは，これら二つを掛けると 2^2 になり，
a と b が等しいときは，n = m なので，log_a{b^2} = 2 となるので，
すべての T の要素の積 N は，2 の T の要素の個数べき乗，N = 2^91，となります。
そこで，log_2{N} = log_2{2^91} = 91 です。

考察：
T の要素の個数を考えればいいので，log_a{b} = n/m に関して考えれば十分です。
そこで，問4：の(別解)と同様に考えると，T の要素が異なる値の場合の個数は
a(k) = 2 * Σ[i=1,k]φ(i) - 1
です。
一方で，T の要素に同じ値も許すと，a = 1 〜 k, b = 1 〜 k なので k^2 個です。
そこで，
r(k) = k^2/a(k) = k^2/(2 * Σ[i=1,k]φ(i) - 1)
として，
r = lim[k->∞]{r(k)} = lim[k->∞]{k^2/(2 * Σ[i=1,k]φ(i) - 1)}
を考えればいいことになります。
ただ，Σ[i=1,k]φ(i) の評価がよく分からなかったので，プログラムを組んで調べてみました。
十進ベーシックです。
ここで，phi(x) はオイラー関数φ(x)で，よく知られた，x を素因数分解した場合の計算式，
x = p1^a1 * p2^a2 * ... * pn^an のとき φ(x) = x * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pn)
を使って計算しています。

FUNCTION phi(x)
　LET f = x
　　FOR i = 2 TO SQR(x)
　　　IF MOD(x,i) = 0 THEN
　　　　LET f = f - f/i
　　　　DO WHILE MOD(x,i) = 0
　　　　　LET x = x/i
　　　　LOOP
　　　END IF
　　NEXT i
　　IF x > 1 THEN
　　　LET f = f - f/x
　END IF
　LET phi = f
END FUNCTION

LET s = 0
FOR k = 1 TO 1000000
　LET s = s + phi(k)
　IF (k <= 20) OR (MOD(k,100000) = 0) THEN
　　LET a = s * 2 - 1
　　PRINT k; a; k^2/a
　END IF
NEXT k

END

結果は，
k の値　T の要素が異なる値の場合の個数(a)　k^2/a
として，

1 1 1
2 3 1.33333333333333
3 7 1.28571428571429
4 11 1.45454545454545
5 19 1.31578947368421
6 23 1.56521739130435
7 35 1.4
8 43 1.48837209302326
9 55 1.47272727272727
10 63 1.58730158730159
11 83 1.4578313253012
12 91 1.58241758241758
13 115 1.4695652173913
14 127 1.54330708661417
15 143 1.57342657342657
16 159 1.61006289308176
17 191 1.5130890052356
18 203 1.59605911330049
19 239 1.51046025104603
20 255 1.56862745098039
100000 6079301507 1.64492581729752
200000 24317197835 1.64492637150929
300000 54713496967 1.64493232911584
400000 97268414619 1.6449327423164
500000 151982079351 1.64493077780986
600000 218853953443 1.64493258785824
700000 297884379079 1.64493351922307
800000 389073894447 1.64493174467448
900000 492421165575 1.64493335507657
1000000 607927104783 1.64493405892299

となりました。

最初は，黄金比 (sqrt(5) + 1)/2：1 〜 1.618：1 になるのかな，と思ったのですが，
それよりは少し大きいようです。
あれこれ思い悩みながら結果を見ていてふと思いついたのは，
ζ(2) = π^2/6 = 1.644934066848226...
でした。え，どうして思いついたかですか？　まぁ，偶然なのですが．．．
黄金比よりも大きくて， 1.64493... となりそうなものは，と考えていて，
昔，物理をやっていた関係で，π^2 〜 重力加速度 〜 9.81 が，ふと頭を横切り，6 で割ったら近そうだ，
という感じでした (^^;

では，どうしてこうなるのかを考えてみましょう。

まず，r(k) の逆数
1/r(k) = a(k)/k^2 = (2 * Σ[i=1,k]φ(i) - 1)/k^2
は，その意味からして，k^2 個の n/m 中の既約分数の割合ですが，
これは，1 〜 k から二つの自然数 m，n を取ったとき m，n が互に素になる確率と考えられます。
そこで，k を無限大にした
1/r = lim[k->∞]{1/r(k)} = lim[k->∞]{(2 * Σ[i=1,k]φ(i) - 1)/k^2}
は，1 〜 ∞，つまり自然数全体，から二つの自然数 m，n を取ったとき m，n が互に素になる確率になります。
これは，m，n が互に素でない，つまり共通の素因数をもつ，場合の余事象です。
素数 p が m，n の共通素因数ということは，m，n が共に素数 p の倍数ということです。
p の倍数は p, 2p, 3p, ... と p 増えるごとに存在するので，m が p の倍数である確率は 1/p です。
同様に，n が p の倍数である確率も 1/p です。
そこで，m，n が共に p の倍数である確率は 1/p^2，m，n が共に p の倍数でない確率は 1 - 1/p^2 です。
m，n が互に素であるには，すべての素数 p に対してこれがいえないといけないので，その確率 P は，
P = Π[すべての素数 p についての積](1 - 1/p^2)
になります。そこで，今求めるもの r は，
r = 1/P = Π[すべての素数 p についての積]{1/(1 - 1/p^2)}
さてこれを，変形してみます。ただし，収束性などのうるさい問題は大学の教科書に任せて，可能と仮定します (^^;
r = Π[すべての素数 p についての積]{1/(1 - 1/p^2)}
1/(1 - 1/p^2) は，初項 1，公比 1/p^2 の等比数列の和，と考えられるので，
= Π[すべての素数 p についての積]{Σ[i=0,∞]{(1/p^2)^i}
具体的に書き下すと，
= (1 + 1/2^2 + 1/2^4 + ... )(1 + 1/3^2 + 1/3^4 + ...)(1 + 1/5^2 + 1/5^4 + ...)...
展開すると
= 1 + 1/2^2 + 1/3^2 + 1/4^2 + 1/5^2 + 1/6^2 + 1/7^2 + ...
= Σ[n=1,∞]{1/n^2}
最後のところは，自然数 n を素因数分解すれば n^2 はその素因数のべきの二乗の積になることからいえます。
そして，ζ関数の定義
ζ(s) = Σ[n=1,∞]{1/n^s}
と比べると，
r = 1/P = ζ(2)
です。この値は，例えば，数学的な応募問題の第197回や第198回などより，
r = 1/P = ζ(2) = π^2/6 = 1.644934066848226...
となります。これで，理由付きで求まりました。

なお，自然数全体から二つの自然数 m，n を取ったとき m，n が互に素になる確率は，
P = 1/r = 1/ζ(2) = 6/π^2 = 0.6079271018540...
ですね。

(感想)
考察：が，やっとできました。ζ関数が現れるとは以外でした。
確かに，興味深い結果ですね。苦労しましたが，大変勉強になりました。

ＮＯ２「kashiwagi」 7/13 21時03分受信 更新7/26

227回解答

（1） 題意よりSの最大値は2¹²＝4096、最小値は2¹＝2　である

（2） 1+2+3+・・・・・・+12＝12・13/2＝78　因ってlog₂M＝log₂2⁷²＝72　である

（3） 題意よりTの最大値は分母を最小、分子を最大とすればよく、

T＝log₂M＝2log₂2¹²/ log₂2¹＝24　、最小値は反対であるから2/12＝1/6　である

（4） 題意より表を作成し、数えて12×12-53＝91となる

（5） N＝2⁹¹　因って、log₂2⁹¹＝91　である

考察

　今、ｋ行ｋ列の行列にみたてると、総数はｋ²　このうち、同じでない数は○^ｋとかける。因って、同じ数はｋ²-○^ｋとなる。これより、これらの比は○^ｋ/（ｋ²-○^ｋ）であるから、ｋを無限に大きくすると0となる。即ち、ｋが無限大ならば全部が同じ数だけとなる。

＜水の流れ：さて、問４ですが、数えていくのですが、１２の約数のときは　オイラー関数が役に立ちます。問題の考察ですが、2組の自然数をとってきたとき、それが互いに素となる確率を考えたことがおありでしょうか。これがヒントです。＞

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。