平成１７年１２月３日
[流れ星]
第163回数学的な応募問題解答
＜解答募集期間：11月13日〜12月4日
［規則性の発見(2)］
皆さん、2001年日本大学生産工学部の入試問題からヒントを得て出題しました。考えてください。
０以上の整数ｎに対してｆ（ｎ）は次の条件を満たすものとする。
【条件１】ｆ（０）＝０
【条件２】ｎが偶数のとき、ｆ（ｎ）＝ｆ（n/2）
【条件３】ｎが奇数のとき、ｆ（ｎ）＝ｆ（（n-1）/2）＋１
このとき、次の問に答えよ。
問１：ｆ（２），ｆ（３），ｆ（７），ｆ（８）の値を求めよ。
問２：０以上の整数ｋに対してｆ（２ｋ），ｆ（２ｋ-1）の値を求めよ。
問３：100を２進法で表わしなさい。また、ｆ（100）の値を求めよ。
問４：ｆ（ｎ）＝４となるｎを小さいものから順に４つ求めよ。
問５：１０２４≦ｎ≦２０４７とするとき、ｆ（ｎ）＝４となるｎのうち３番目に大きいものを求めよ。
ＮＯ１「uchinyan」11/13 11時54分受信
更新12/４
第163回数学的な応募問題の解答
問1：f(2) = f(1) = f(0) + 1 = 0 + 1 = 1
f(3) = f(1) + 1 = 2
f(7) = f(3) + 1 = 3
f(8) = f(4) = f(2) = f(1) = 1
問2： f(2^k) = f(2^(k-1)) = ... = f(2) = f(1) = 1
f(2^k - 1) = f(((2^k - 1) - 1)/2) + 1 = f(2^(k-1) - 1) + 1 = ... = f(2-1) +
(k-1) = k
問3：
数の2進法表記を、10101B などと書くことにします。B は binary の略です。すると、
100 = 64 + 32 + 4 = 2^6 + 2^5 + 2^2 = 1100100B
2進法表記の場合、2で割ることは、桁を一つ右にずらすことに注意すると、
f(100) = f(1100100B) = f(110010B) = f(11001B) = f(1100B) + 1
= f(110B) + 1 = f(11B) + 1 = f(1B) + 1 + 1 = f(0B) + 1 + 1 + 1
= 0 + 1 + 1 + 1
= 3
問4：問3までで、次の命題が予想できます。
(命題)
n を2進法表記したものを n = a(0)a(1)...a(k-1)a(k)B とする。
ただし、a(i), i = 0, .., k は、2進法表記の各桁で
0 又は 1 とする。
すると、f(n) = a(0) + a(1) + ... + a(k-1) + a(k)
[証明]
数学的帰納法を使います。
* k = 0 のとき
n = 0 又は 1 ですが、a(0) = 0 又は 1 で、f(0) = 0, f(1) = 1 より成立。
* k = m のとき
k = m-1 で成立すると仮定します。
n = a(0)a(1)...a(m-1)a(m)B ですが、a(m) は 0 又は 1 だから、
a(m) = 0 のときは、
f(n) = f(a(0)a(1)...a(m-1)0B) = f(a(0)a(1)...a(m-1)B)
a(m) = 1 のときは、
f(n) = f(a(0)a(1)...a(m-1)1B) = f(a(0)a(1)...a(m-1)B) + 1
となり、結局、まとめて
f(n) = f(a(0)a(1)...a(m-1)a(m)B) = f(a(0)a(1)...a(m-1)B) + a(m)
と書けます。したがって、帰納法の仮定より、
f(a(0)a(1)...a(m-1)B) = a(0) + a(1) + ... + a(m-1) なので、
f(n) = f(a(0)a(1)...a(m-1)a(m)B) = a(0) + a(1) + ... + a(m-1) + a(m) が成立します。
以上で、命題が証明できました。
[証明終わり]
これを使うと、f(n) = 4 は、n を2進法表記したときに 1 が四つある数であることが分かります。
こうした数の最小は、1111B で、それ以上は、10111B, 11011B, 11101B となります。
つまり求める数は、15, 23, 27, 29 になります。
問5：
問4と同様に、f(n) = 4 は、n を2進法表記したときに 1 が四つある数であることが分かります。
ただし今度は、1024 <= n <= 2047 で3番目に大きいものを選びます。
1024 = 10000000000B, 2047 = 11111111111B なので、11110000000B, 11101000000B,
11100100000B で、
n = 11100100000B = 1024 + 512 + 256 + 32 = 1824 になります。
[感想]
各問が2進法表記への導入になっているので、考えやすい問題ですね。
ただ、問4、問5は、試験では、試験でなくとも？、うっかりミスをしそうです。
念のためにプログラムでチェックしました ^^;
ＮＯ２「cbc」 11/13 21時38分受信
更新12/４
ＮＯ３「Jun」 11/13 23時00分受信 更新12/４
おもしろそうなので解いて見ました。
ｆ（ｎ）は、２進数表示をしたときに、「１」が何個並ぶかという関数でしょうか。
問１
ｆ（１）＝１、ｆ（２）＝１、ｆ（３）＝２、ｆ（４）＝１、
ｆ（５）＝２、ｆ（６）＝２、ｆ（７）＝３、ｆ（８）＝１
問２
ｆ（２＾ｋ）＝１
ｆ（２＾ｋ−１）＝ｋ
問３
１００＝１１００１００（２）
ｆ（１００）＝３
問４
１５，２３，２７，２９
問５
１８２４
計算間違いをしていなければいいのですが・・・。
ＮＯ４「kashiwagi｣11/14 08時13分受信 更新12/４
お世話になります。今回の問題は非常に興味深く拝読致しました。2進法で こんなに簡単に解が求められるとは・・・・、正に目から鱗でした。
163回解答
問題1
条件を使い
ｎに数をあてはめると、
因って、
問題2
条件より 
1, ところで1,2,4,8は2の累乗であるから
又、
ところで
であるから
問題3
100 =
であるから1100100が求めるものである。
問題4
問題3より100を二進法で表すと1100100であるから
が成立する。ところで同様な変換を50と25にも行うと、それぞれ
110010と11001となり、
となる。即ち、二進法で表した各桁の数字の和が求める3となっていることが分かる。
因って、
となる nの値は小さい順に、1111,10111,11011,11101となる。これらを１０進法に書き直すと、15,23,27,29となる。
問題5
1024と2047を2進法で表すと、各々10000000000と11111111111となる。問題4と同様に考えて、大きい順に並べると11110000000、11101000000、11100100000となる。よって3番目に大きな数は11100100000であり、10進法では1824となる。
ＮＯ５「浜田明巳」11/15 10時45分受信 更新12/４
整数問題なので，いつものように，エクセルのマクロMacro1で解いた．
問題１：f(2)=1,f(3)=2,f(7)=3,f(8)=1
問題２：f(2^0)=1,f(2^0-1)=0
f(2^1)=1,f(2^1-1)=1
f(2^2)=1,f(2^2-1)=2
f(2^3)=1,f(2^3-1)=3
f(2^4)=1,f(2^4-1)=4
f(2^5)=1,f(2^5-1)=5
f(2^6)=1,f(2^6-1)=6
f(2^7)=1,f(2^7-1)=7
f(2^8)=1,f(2^8-1)=8
f(2^9)=1,f(2^9-1)=9
f(2^10)=1,f(2^10-1)=10
f(2^11)=1,f(2^11-1)=11
f(2^12)=1,f(2^12-1)=12
f(2^13)=1,f(2^13-1)=13
となるので，
f(2^k)=1,f(2^k-1)=k
となる事が予想される．
問題２：100=1100100(2),f(100)=3
となるので，f(n)は，ｎを２進法で表したときの各位の１の個数である事が予想される．
問題３：15,23,27,29
問題４：1824
問題２の予想をマクロMacro2で検証してみた．確かに予想通りである．
Option Explicit
Sub Macro1()
Sheets("Sheet1").Select
Dim n As Long
Dim k As Integer
Dim kosuu As Integer
Dim nn As String
For n = 1 To 10000
Cells(n, 1).Value = n
Cells(n, 2).Value = f(n)
Range("A" & strr(n)).Select
Next n
'
'問１：ｆ（２），ｆ（３），ｆ（７），ｆ（８）の値を求めよ。
Cells(1, 4).Value = "f(2)=" & strr(f(2))
Cells(2, 4).Value = "f(3)=" & strr(f(3))
Cells(3, 4).Value = "f(7)=" & strr(f(7))
Cells(4, 4).Value = "f(8)=" & strr(f(8))
Range("D4").Select
'
'問２：０以上の整数ｋに対してｆ（２ｋ），ｆ（２ｋ-1）の値を求めよ。
n = 1
For k = 0 To 13
If k > 0 Then
n = n * 2
End If
Cells(k * 2 + 1, 6).Value = "f(2^"
& strr(k) & ")=" & strr(f(n))
Cells(k * 2 + 2, 6).Value = "f(2^"
& strr(k) & "-1)=" & strr(f(n - 1))
Range("F" & strr(k
* 2 + 2)).Select
Next k
'
'問３：100を２進法で表わしなさい。また、ｆ（100）の値を求めよ。
n = 100
nn = ""
While n > 0
nn = strr(n Mod 2) & nn
n = n \ 2
Wend
Cells(1, 8).Value = nn
Cells(2, 8).Value = "f(100)=" & strr(f(100))
Range("H2").Select
'
'問４：ｆ（ｎ）＝４となるｎを小さいものから順に４つ求めよ。
kosuu = 0
n = 0
While kosuu < 4
If f(n) = 4 Then
kosuu = kosuu + 1
Cells(kosuu,
10).Value = n
Range("J" & strr(kosuu)).Select
End If
n = n + 1
Wend
'
'問５：１０２４≦ｎ≦２０４７とするとき、ｆ（ｎ）＝４となるｎのうち３番目に大きいものを求めよ。
kosuu = 0
n = 2047
While kosuu < 3 And n >=
1024
If f(n) = 4 Then
kosuu = kosuu + 1
Cells(kosuu,
12).Value = n
Range("L" & strr(kosuu)).Select
End If
n = n - 1
Wend
End Sub
Private Function f(ByVal n As Integer) As Integer
If n = 0 Then
f = 0
ElseIf n Mod 2 = 0 Then
f = f(n / 2)
Else
f = f((n - 1) / 2) + 1
End If
End Function
Private Function strr(ByVal
n As Integer) As String
strr = Right(Str(n),
Len(Str(n)) - 1)
End Function
Option Explicit
Const MAX As Long = 2000
Sub Macro2()
Sheets("Sheet2").Select
Columns("C:C").Select
Selection.NumberFormatLocal =
"@"
'
Dim n As Long
Dim nn As Long
Dim ns As String
Dim owari As Integer
owari = 0
n = 1
While owari = 0 And n <= MAX
Cells(n, 1).Value = n
Cells(n, 2).Value = f(n)
nn = n
ns = ""
While nn > 0
ns = strr(nn Mod 2) & ns
nn = nn \ 2
Wend
Cells(n, 3).Value = ns
Cells(n, 4).Value = f1(ns)
Range("A" & strr(n)).Select
If Cells(n, 2).Value <> Cells(n, 4).Value
Then
owari = 1
Cells(n, 5).Value = "****"
Else
n = n + 1
End If
Wend
'
Columns("C:C").Select
Columns("C:C").EntireColumn.AutoFit
If owari Then
Range("A" & strr(n)).Select
Else
Range("A1").Select
End If
End Sub
Private Function f(ByVal n As Integer) As Integer
If n = 0 Then
f = 0
ElseIf n Mod 2 = 0 Then
f = f(n / 2)
Else
f = f((n - 1) / 2) + 1
End If
End Function
Private Function strr(ByVal
n As Integer) As String
strr = Right(Str(n),
Len(Str(n)) - 1)
End Function
Private Function f1(ByVal s As String) As Integer
Dim j As Integer
f1 = 0
For j = 1 To Len(s)
If Mid(s, j, 1) = "1" Then
f1 = f1 + 1
End If
Next j
End Function
ＮＯ６「Toru」 11/15 11時00分受信 更新12/４
第１６３回の解答を送ります。2進法に気がつけばすぐですね。なかなか面白い問題と思います。
問１、 f(2)=f(1)=1,f(3)=f(1)+1=2,f(7)=f(3)+1=3,f(8)=f(4)=f(2)=1
問２、 f(2^k)=f(2^(k-1))=---=f(1)=1,
f(2^k-1)=f(2^(k-1)-1)+1=f(2^(k-2)-1)+2=--=f(2^1-1)+k-1=k
問３、 100=2^6+2^5+2^2 より1100100
f(100)=f(50)=f(25)=f(12)+1=f(6)+1=f(3)+1=(f(1)+1)+1=3
問４、問３の時、100→50→25→12(+1)→6→3→1(+1)を2進法であらわすと
1100100→110010→11001→1100(+1)→110→11→1(+1)で 右から一つずつ数字を取って行って、１の時に１を加えることになる。
ここでもとの条件を2進法で考えてみれば
条件１：f(0)=0
条件２：１の位が0の時は0を取ってもかわらない
条件３：１の位が１の時は１を取った時に１を加える。
すなわち2進法で表わして、１の数を数えればよい。
よってf(n)=4になるものは2進法では小さい方から
1111,10111,11011,11101
これを１０進法にすれば、15,23,27,29
問５、1024,2047は2進法では10000000000 ,11111111111
より条件の数は2進法では１１桁の数
このうち１が４つあるものは大きい方から順に
11110000000,11101000000,11100100000---
11100100000を１０進法にもどせば、2^10+2^9+2^8+2^5=1824
ＮＯ７「kasama」 11/21 16時17分受信 更新12/４
今回も面白い問題ですね。我々プログラマにとっては64、128、256、512、1024・・・など２をベースにした数には大変馴染みがあります。しばらく問題を眺めていれば、論理は別して、直感的に規則が思い浮かぶので、取組み易かったです。
【問１】
与えられた漸化式を使って順に計算していけば良いのですが、簡単なプログラム【補足１】にやらせると、f(2)=1、f(3)=2、f(7)=3、f(8)=1とわかります。f(255)、f(511)、f(1023)付近の値を計算させると、何となく規則性が見えてきます。
【問２】
【条件１】を適用して、f(2k)=f(2k-1)=f(2k-2)=･･･=f(20)=f(1)=1
【条件２】を適用して、f(2k-1)=f(2k-1-1)+1=f(2k-2-1)+2=･･･=f(20-1)+k=f(0)+k=k
よって、f(n)はnを二進数表示した場合の1の個数とわかります。
【問３】
100を二進数表示すると1100100です。したがって、f(100)=3です。
【問４】
4つの1を用いて、小さい方から4つの二進数を考えると、1111、10111、11011、11101なので、15、23、27、29です。簡単なプログラム【補足２】で確かめると、確かに
(01:25) gp > dai163(4,1,4)
15 23 27 29
です。
【問５】
1024=10000000000、2047=11111111111なので、区間[10000000000,11111111111]で、4つの1で表現できる二進数を小さいほうから求めていくと、10000000111、10000001011、10000001101なので、3番目に大きいのは、10000001101=1037です。プログラムで確かめると、
(01:30) gp > dai163(4,1024,3)
1031 1035 1037
です。
【補足１】
f(n)=
{ if (n > 0, if (n % 2 > 0, f((n-1)/2)+1, f(n/2)), 0);}
【補足２】
dai163(m, i, k)=
{ local(n);n = 0; while (n < k,if (f(i) == m, print1(i, "
"); n++); i++; );}
ＮＯ８「ドンキー」 11/27 16時13分受信 更新12/４
162の解答も送ろうと思っていたんですが、知らない間に更新されてしまっていたので163の解答を送ります。
「解答」
問１：これは単に条件にしたがって計算していけば求められます。
f(1)=f(0)+1=0+1=1
f(2)=f(1)=1 ・・・（答）
f(3)=f(1)+1=1+1=2 ・・・（答）
f(4)=f(2)=1
f(5)=f(2)+1=1+1=2
f(6)=f(3)=2
f(7)=f(3)+1=2+1=3 ・・・（答）
f(8)=f(4)=1 ・・・（答）
問２：これも条件に従い計算します。
k＝0のときは f(2^k)=f(2^0)=f(1)=1 、 f(2^k-1)=f(2^0-1)=f(0)=0
k≧1のときは、2^kは偶数、2＾ｋ-1は奇数なので
ｆ（2＾ｋ）＝ｆ（2＾（ｋ−1））＝・・・＝ｆ（2）＝ｆ（1）＝1
f(2^k-1)=f(2^(k-1)-1)+1＝・・・＝ｆ（2-1）+（ｋ-1）＝1+（ｋ-1）＝ｋ
まとめると
f(2^k)=1 、 ｆ（2＾ｋ-1）＝ｋ ・・・（答）
問３：ｋ進法で表したとき、数のあとに（ｋ）をつけるとしておくと
100（10）＝1100100（2） ・・・（答）
ここで、２進法で表された数字は下一桁が0なら偶数、1なら奇数であることと、
２で割るという操作はちょうど桁を右に一つだけずらすことに相当することに注意すると、
ある整数ｎが２進法で表されているとき、
（条件２’）下一桁が0なら f(n)=f(nの桁を右に一つだけずらした数)
（条件３’）下一桁が1なら f(n)=f(n-1の桁を右に一つだけずらした数)+1
と読みかえることが出来ます。
ということは、２進法で表された数の下一桁が0であるかぎり桁を右に一つずらし続け、
１に出会うたびに１を引いてから桁を右に一つずらすかわりに、fの値を１だけ増やせばいいわけです。
つまり、二進法で表したときに現れる１の個数がそのままｆの値というわけですね。
よって ｆ（100）＝3 ・・・（答）
問４：問３での考察から、題意の数は
ｎ＝1111、10111,11011、11101（2）
よって10進法で表すと
ｎ＝15、23、27、29 ・・・（答）
問５：
＜水の流れコメント：問５は勘違いでしたから、削除していきます。＞
＜感想＞
今回は面白い問題でした。誘導が丁寧だったのでこのような方針で解けましたが、
２進法がこの問題の本質にあるというのはなかなか気づきにくいことではないかと思います。
参考にされたという日本大学の問題では穴埋めだったので、予想して埋めることは容易に出来ますが、
記述式で解かせようとするなら今回の問題のほうが質的にもいいのではないかと思いますね。
ところで、問５で1024≦ｎという条件は必要でしょうか？大きいほうから３つ選ぶなら、ｎ≦2047だけで答は決まると思います。
＜水の流れコメント：その通りですね。２進法で１１桁の中からという思いからです。＞
