平成２３年１１月１３日

[流れ星]

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

　　　　　　＜解答募集期間：10月23日〜11月13日

［log₂nの最大整数］

今年の工学院大学入試問題から改題して出題しました。

ＮＯ１「uchinyan」 10/23 14時04分受信 更新11/13

第２６５回数学的な応募問題

［log2(n)の最大整数］

(1)

log2(1) = 0，log2(2) = 1，log2(4) = 2，log2(8) = 3，なので，

a(1) = 0，a(2) = 1，a(3) = 1，a(4) = 2，a(5) = 2

(2)

y = log2(x)，x > 0，は，単調増加関数で，2^k <= n < 2^(k+1) のとき a(n) = k なので，

(2^(k+1) - 1) - (2^k - 1) = 2^(k+1) - 2^k = 2^k 個。

(3)＆(4)

2^i <= n < 2^(i+1) のとき a(n) = i でこれが 2^i 個なので，2^k <= m < 2^(k+1) とすると，

Σ[n=1,m]{a(n)}

= Σ[n=1,2^k - 1]{a(n)} + Σ[n=2^k,m]{a(n)}

= Σ[i=0,k-1]{2^i * i} + (m - 2^k + 1) * k

ここで，

S(k) = Σ[n=1,2^k - 1]{a(n)} = Σ[i=0,k-1]{2^i * i}

とすると，

S(k) = 2 * S(k) - S(k)

= 2 * Σ[i=0,k-1]{2^i * i} - Σ[i=0,k-1]{2^i * i}

= Σ[i=0,k-1]{2^(i+1) * i} - Σ[i=0,k-1]{2^i * i}

= Σ[i=1,k]{2^i * (i-1)} - Σ[i=1,k-1]{2^i * i}

= Σ[i=1,k-1]{2^i * (i-1)} + 2^k * (k-1) - Σ[i=1,k-1]{2^i * i}

= 2^k * (k-1) + Σ[i=1,k-1]{2^i * ((i-1) - i)}

= 2^k * (k-1) - Σ[i=1,k-1]{2^i}

= 2^k * (k-1) - 2 * (2^(k-1) - 1)/(2 - 1)

= 2^k * (k-1) - 2^k + 2

= 2^k * (k-2) + 2

Σ[n=1,m]{a(n)}

= (2^k * (k-2) + 2) + (m - 2^k + 1) * k

= (m + 1)k - 2^(k+1) + 2

そこで，

(3)

2^10 = 1024 < 2011 < 2048 = 2^11 なので，m = 2011，k = 10 で，

Σ[n=1,2011]{a(n)}

= (2011 + 1) * 10 - 2^(10+1) + 2

= 20120 - 2048 + 2

= 18074

(4)

Σ[n=1,2^(k+1) - 1]{a(n)} = S(k+1) = 2^(k+1) * (k-1) + 2

(感想)

基本をしっかり理解していれば解けるいい問題だと思います。

ただ，それだけに，試験場では計算間違いが怖い問題ですね。

ＮＯ２「浜田明巳」 10/25 13時46分受信 <br>

「浜田明巳」 10/27 15時04分受信 更新11/13

(1) ａ_ｎ＝[log_２ｎ]となるので，
　ｋ：非負整数，２^ｋ≦ｎ≦２^ｋ＋１−１のとき，ａ_ｎ＝ｋ
　∴ａ_１＝０，ａ_２＝ａ_３＝１，ａ_４＝ａ_５＝２
(2) ａ_ｎ＝ｋとなるｎの個数は，
　(２^ｋ＋１−１)−２^ｋ＋１＝２^ｋ（個）
(3) Σ_{１≦ｋ≦２０１１}ａ_ｋ＝Σ_{１≦ｋ≦１０２３}ａ_ｋ＋Σ_{１０２４≦ｋ≦２０１１}ａ_ｋ
　ここで，
　　Ｓ_ｎ＝Σ_{１≦ｋ≦ｎ}ｋ・２^ｋ＝１・２^１＋２・２^２＋３・２^３＋………＋ｎ・２^ｎ
とおくと，
　　２Ｓ_ｎ＝１・２^２＋２・２^３＋………＋(ｎ−１)・２^ｎ＋ｎ・２^ｎ＋１
　差をとると，< ;br> 　　−Ｓ_ｎ＝１・２^１＋１・２& lt;sup>２＋１・２^３＋………＋１・２^ｎ−ｎ・２^ｎ＋１
　　　　　＝２(２^ｎ−１)／(２−１)−ｎ・２^ｎ＋１＝(１−ｎ)２^ｎ＋１−２
　　∴Ｓ_ｎ＝(ｎ−１)２^ｎ＋１＋２
　　∴Σ_{１≦ｋ≦１０２３}ａ_ｋ＝Σ_{１≦ｋ≦９}ｋ・２^ｋ＝８・２^１０＋２＝８１９４
　次に，
　　Σ_{１０２４≦ｋ≦２０１１}ａ_ｋ＝Σ_{１０２４・u槭B襦紕横娃隠・・・・・・・・１０}＝１０(２０１１−１０２４＋１)＝９８８０
　　∴与式＝８１９４＋９８８０＝１８０７４
(4) ２^ｋ＋１−１≧１から，２^ｋ＋１≧２　　　∴ｋ＋１≧１　　　∴ｋ≧０
　ｋ≧１のとき，
　　Σ_{１≦ｎ≦２^ｋ＋１−１}ａ_ｎ＝Ｓ_ｋ＝(ｋ−１)２^ｋ＋１＋２
　これはｋ＝０の場合を含む．
　　∴Σ_{１≦ｎ≦２^ｋ＋１−１}ａ_ｎ＝(ｋ−１)２^ｋ＋１＋２

　ちなみに(3)に関しては，次のエクセルのマクロでも確かめてみた．
Option Explicit
Sub Macro1()
    Sheets("Sheet1").Select
    Cells(1, 1).Value = 0
    Range("A1").Select
    Dim n As Integer
    For n = 1 To 2011
       Cells(1, 1).Value = Cells(1, 1).Value + Int(Log(n) / Log(2))
    Next n
End Sub

ＮＯ３「ｽﾓｰｸﾏﾝ」 10/28 17時36分受信 更新11/13

秋冷の候...晴耕雨読...? 今回は手を出してみました ^^;v

[log(2)n]=k...2^k以上2^(k+1)以下なら成り立ちますから...
定義より...[2^k]≦n<[2^(k+1)] のとき、an=k なので...
an=k の個数=(2^(k+1)-1)-(2^k-1)=2^(k+1)-2^k

(1)
　n=1...[2^0]≦1<[2^1]...a1=0
　n=2...2^1=2...a2=1
　n=3...[2^1]≦3<[2^2]...a3=1
　n=4...2^2...a4=2
　n=5...[2^2]≦5<[2^3]...a5=2

(2)
　上から...2^(k+1)-2^k

(3)
　Σ(1〜2011) an=10(2011-2^10)+9(2^10-2^9)+...+2(2^3-2^2)+(2^2-2)+0(2^1-2^0)
　　　　　　　　　　 =10*2011-(2^10+2^9+...+2^2+2)
                       =20110-(2^10+2^9+...+2^2+2+1+1)+(1+1)
                       =20110-2^11+2
                       =20110-2*1012+2
                       =20110-2022
                       =18088

＜水の流れ：一部計算ミスがあったようです。

Σ(1〜１０２３) an＝9(2^10-2^9)+...+2(2^3-2^2)+(2^2-2)+0(2^1-2^0)

　　　　　　　　　　　　　　　＝８１９４

　で、さらに、Σ(１０２４〜２０１１)＝１０×（２０１１−１０２４＋１）

　　　　　　　　　　　　　　　　　＝９８８０　　　　　　　　　　　　　　＞

(4)
　Σ(2^(k+1)-1〜1) an=k*(2^(k+1)-1-(2^k-1))+(k-1)*(2^k-2^(k-1))+...+(2^2-2)
                             =k*2^(k+1)-(2^k+2^(k-1)+...+2+1+1)+2
                             =k*2^(k+1)-2^(k+1)+2
                             =(k-1)*2^(k+1)+2

でいいはずだと...^^

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