平成２４年９月２３日
[流れ星]
第２８０回数学的な応募問題解答
＜解答募集期間：9月2日～9月2３日＞
［４桁の電話番号］
（１）0000から9999までの10000通りの電話番号のうち、０，１が少なくとも１回ともに現れる番号は全部でいくつあるか。
（２）０から9999までの整数のうちで、０，１が少なくとも１回ともに現れる整数はいくつあるか。
NO1「uchinyan」 09/02 15時43分受信 更新9/23
どうせなので n 桁で解いてしまいましょう。
(1) (解法1)
n 桁のうち，0，1 のある桁の数を k 桁，0 のある桁の数を m 桁とすると，
0，1 が少なくとも 1 回ともに現れるのだから，k >= 2，m >= 1，k-m
>= 1 で，
0，1 が現れる桁を選ぶのに nCk 通り，その k 桁内での 0，1 の配置に kCm 通り，
0，1 以外の n-k 桁は 2 ～ 9 なので 8^(n-k) 通り，となって，nCk * kCm * 8^(n-k) 個，
これを k = 2 ～ n，m = 1 ～ k-1 で足せばいいから，
Σ[k=2,n]{Σ[m=1,k-1]{nCk
* kCm * 8^(n-k)}}
= Σ[k=2,n]{nCk
* Σ[m=1,k-1]{kCm} * 8^(n-k)}
= Σ[k=2,n]{nCk
* (Σ[m=0,k]{kCm} - kC0 - kCk) * 8^(n-k)}
= Σ[k=2,n]{nCk
* ((1 + 1)^k - 1 - 1) * 8^(n-k)}
= Σ[k=2,n]{nCk
* (2^k - 2) * 8^(n-k)}
= Σ[k=2,n]{nCk
* 2^k * 8^(n-k)} - 2 * Σ[k=2,n]{nCk
* 8^(n-k)}
= (Σ[k=0,n]{nCk
* 2^k * 8^(n-k)} - nC0 * 2^0 * 8^(n-0) - nC1 * 2^1 * 8^(n-1))
- 2 * (Σ[k=0,n]{nCk
* 1^k * 8^(n-k)} - nC0 * 1^0 * 8^(n-0) - nC1 * 1^1 * 8^(n-1))
= ((2 + 8)^n - 8^n - 2 * n * 8^(n-1)) - 2 * ((1 + 8)^n - 8^n - n *
8^(n-1))
= 10^n - 2 * 9^n + 8^n 個
この問題では，n = 4 なので，
10^4 - 2 * 9^4 + 8^4 = 10000 - 13122 + 4096 = 974 個
になります。
(解法2)
n 桁のうち 0，1 が少なくとも 1 回ともに現れるのだから，
まず，全体の 10^n 個から，0，1 が両方ともに 1 回も現れない 8^n 個を引きます。
しかしこの中には，まだ，片方しか現れない場合が残っているので，これも引きます。
これは，
1 ～ 9 を使い 1 が少なくとも 1 回現れる場合 9^n - 8^n 個，と
0，2 ～ 9 を使い 0 が少なくとも 1 回現れる場合
9^n - 8^n 個，です。
そこで，結局，
10^n - 8^n - (9^n - 8^n) - (9^n - 8^n) = 10^n - 2 * 9^n + 8^n 個
この問題では，n = 4 なので，
10^4 - 2 * 9^4 + 8^4 = 10000 - 13122 + 4096 = 974 個
になります。
(解法3)
n 桁のうち 0，1 が少なくとも 1 回ともに現れるのだから，
まず，全体の 10^n 個から，
0 が全く現れない場合 9^n 個と 1 が全く現れない場合 9^n 個を引きます。
ところが今度は，これでは，
0，1 が両方とも全く現れない場合 8^n 個を２回引いてしまっているので１回分を足します。
そこで，結局，
10^n - 9^n - 9^n + 8^n = 10^n - 2 * 9^n + 8^n 個
この問題では，n = 4 なので，
10^4 - 2 * 9^4 + 8^4 = 10000 - 13122 + 4096 = 974 個
になります。
(2) (解法1)
(1)より，整数が n-1 桁以下の場合で n 桁に足らない上位桁部分に 0 を補った場合の数は，
10^n - 2 * 9^n + 8^n 個，になります。
そこで，整数がちょうど n 桁の場合は，
n 桁目が 1 の場合
残りの n-1 桁に 0 が少なくとも 1 回現れればいいので 10^(n-1) - 9^(n-1) 個
n 桁目が 2 ～ 9 の場合
残りの n-1 桁に(1)が使えて，8 *
(10^(n-1) - 2 * 9^(n-1) + 8^(n-1)) 個
で，合計，9 * 10^(n-1) - 17 * 9^(n-1) + 8^n 個，です。
そこで，整数が n 桁以下の場合には，k = 1 ～
n として k 桁の整数の場合を足せばいいので，
Σ[k=1,n]{9 * 10^(k-1) - 17 * 9^(k-1) + 8^k}
= 9 * (10^n - 1)/(10 - 1) - 17 * (9^n - 1)/(9 - 1) + 8 * (8^n -
1)/(8 - 1)
= (10^n - 1) - 17(9^n - 1)/8 + 8(8^n - 1)/7 個
この問題では，n = 4 なので，
(10^4 - 1) - 17(9^4 - 1)/8 + 8(8^4 - 1)/7 = 9999 - 13940 + 4680 =
739 個
になります。
(解法2)
(1)より，整数が n-1 桁以下の場合で n 桁に足らない上位桁部分に 0 を補った場合の数は，
10^n - 2 * 9^n + 8^n 個，になります。
そこで，上位 k 桁に 0 が並び n-k 桁以下で 0 が現れず 1 が少なくとも 1 回現れる場合，
9^(n-k) - 8^(n-k) 個，を k = 1 ～ n で足し上げたものを(1)の結果から引けばいいので，
(10^n - 2 * 9^n + 8^n) - Σ[k=1,n]{9^(n-k)
- 8^(n-k)}
= (10^n - 2 * 9^n + 8^n) - (9^n - 1)/(9 - 1) + (8^n - 1)/(8 - 1)
= 10^n - (17 * 9^n - 1)/8 + (8 * 8^n - 1)/7
= 10^n - 17(9^n - 1)/8 - 2 + 8(8^n - 1)/7 + 1
= (10^n - 1) - 17(9^n - 1)/8 + 8(8^n - 1)/7 個
この問題では，n = 4 なので，
(10^4 - 1) - 17(9^4 - 1)/8 + 8(8^4 - 1)/7 = 9999 - 13940 + 4680 =
739 個
になります。
(感想)
「０，１が少なくとも１回ともに現れる」という条件が，最初，ピンと来なくて迷いましたが，
要するに，0，1 が両方とも同時に 1 回以上現れる，つまり，0002，1234 などはなし，
と解釈しましたが，それでよかったでしょうか。
場合の数は，いろいろと考えられるので割と好きな分野なのですが，
問題文の解釈に迷うことも多く，その意味では，少し苦手です。
まぁ，数学というよりも国語の問題なんですが，常識がない，ともいえるかなぁ (^^;
NO2「浜田明巳」 09/03 17時32分受信
更新9/23
（１）i). ０，１が合計４個のとき，
ア). ０が３個，１が１個，または０が１個，１が３個のとき，
ａａａｂ，ａａｂａ，ａｂａａ，ｂａａａ（｛ａ，ｂ｝＝｛０，１｝）
の４種類なので，
４×２＝８（個）
イ). ０が２個，１が２個のとき，
ａａｂｂ，ａｂａｂ，ａｂｂａ（｛ａ，ｂ｝＝｛０，１｝）
の３種類なので，
３×２＝６（個）
ii). ０，１が合計３個のとき，０が２個，１が１個，または０が１個，１が２個なので，
ａａｂｃ，ａａｃｂ，ａｂａｃ，ａｃａｂ，ａｂｃａ，ａｃｂａ，ｂａａｃ，ｃａａｂ，ｂａｃａ，ｃａｂａ，ｂｃａａ，ｃｂａａ
（｛ａ，ｂ｝＝｛０，１｝；ｃ＝２，３，４，………，９）
の１２種類なので，
１２×２×８＝１９２（個）
iii). ０，１が合計２個のとき，０が１個，１が１個なので，
ａｂｃｄ，ａｃｂｄ，ａｃｄｂ，ｃａｂｄ，ｃａｄｂ，ｃｄａｂ
（｛ａ，ｂ｝＝｛０，１｝；ｃ，ｄ＝２，３，４，………，９）
の６種類なので，
６×２×８２＝７６８（個）
まとめると，
(８＋６)＋１９２＋７６８＝９７４（個）
（２）i).
２桁のとき，１０の１個．
ii). ３桁のとき，
ア). ０が２個，１が１個のとき，１００の１個．
イ). ０が１個，１が２個のとき，１１０，１０１の２個．
ウ). ０が１個，１が１個のとき，
１０ａ，１ａ０，ａ１０，ａ０１（ａ＝２，３，４，………，９）
の４種類なので，
４×８＝３２（個）
iii). ４桁のとき，
ア). ０が３個，１が１個のとき，１０００の１個．
イ). ０が１個，１が３個のとき，１１１０，１１０１，１０１１の３個．
ウ). ０が２個，１が２個のとき，１１００，１０１０，１００１の３個．
エ). ０が２個，１が１個のとき，
１００ａ，１０ａ０，１ａ００，ａ００１，ａ０１０，ａ１００（ａ＝２，３，４，………，９）
の６種類なので，
６×８＝４８（個）
オ). ０が１個，１が２個のとき，
１１０ａ，１１ａ０，１０１ａ，１ａ１０，１０ａ１，１ａ０１，ａ１１０，ａ１０１，ａ０１１
（ａ＝２，３，４，………，９）
の９種類なので，
９×８＝７２（個）
カ). ０が１個，１が１個のとき，
１０ａｂ，１ａ０ｂ，１ａｂ０，ａ０１ｂ，ａ０ｂ１，ａ１０ｂ，ａ１ｂ０，ａｂ０１，ａｂ１０
（ａ，ｂ＝２，３，４，………，９）
の９種類なので，
９×８２＝５７６（個）
まとめると，
１＋(１＋２＋３２)＋(１＋３＋３＋４８＋７２＋５７６)＝７３９（個）
（別解）（１）余事象を考える．
i). ０が０個，１が０個のとき，
ａｂｃｄ（ａ，ｂ，ｃ，ｄ＝２，３，４，………，９）
となるので，
８４＝４０９６（個）
ii). ０が１個，１が０個，または０が０個，１が１個のとき，
ａｂｃｄ，ｂａｃｄ，ｂｃａｄ，ｂｃｄａ（ａ＝０，１；ｂ，ｃ，ｄ＝２，３，４，………，９）
の４種類なので，
４×２×８３＝８４＝４０９６（個）
iii). ０が２個，１が０個，または０が０個，１が２個のとき，
ａａｂｃ，ａｂａｃ，ａｂｃａ，ｂａａｃ，ｂａｃａ，ｂｃａａ
（ａ＝０，１；ｂ、ｃ＝２，３，４，………，９）
の６種類なので，
６×２×８２＝７６８（個）
iv). ０が３個，１が０個，または０が０個，１が３個のとき，
ａａａｂ，ａａｂａ，ａｂａａ，ｂａａａ
（ａ＝０，１；ｂ＝２，３，４，………，９）
の４種類なので，
４×２×８＝６４（個）
v). ０が４個，１が０個，または０が０個，１が４個のとき，００００，１１１１の２個
まとめると，
４０９６＋４０９６＋７６８＋６４＋２＝９０２６（個）
これが余事象の数なので，求める個数は，
１００００－９０２６＝９７４（個）
（参考）問題文に「少なくとも」という文句が入っているときは，大抵余事象を考える方が簡単であるが，この場合は簡単ではなかった．
（別解）（２）（１）の答から，１桁，２桁，３桁の数で０を使わない場合の数を引けばよい．
i). １桁のとき，１個．
ii). ２桁のとき，２桁の正の整数の内で，数字０を使わないものを選べばよい．
ア). 十の位が１のとき，１１～１９の９個．
イ). ア).以外で一の位が１のとき，２１～９１の８個．
iii). ３桁のとき，３桁の正の整数の内で，数字０を使わないものを選べばよい．
ア). １を３個使うとき，１１１の１個．
イ). １を２個使うとき，
１１ａ，１ａ１，ａ１１（ａ＝２，３，４，………，９）
の３種類なので，
３×８＝２４（個）
ウ). １を１個使うとき，
１ａｂ，ａ１ｂ，ａｂ１（ａ，ｂ＝２，３，４，………，９）
の３種類なので，
３×８２＝１９２（個）
まとめると，
１＋(９＋８)＋(１＋２４＋１９２)＝２３５（個）
故に求める個数は，
９７４－２３５＝７３９（個）
（別解）エクセルのマクロで解いてみた．上記の答案よりも断然楽であった．場合分けがほとんどいらない．
Option Explicit
Dim a(4) As Integer
Sub Macro1()
Sheets("Sheet1").Select
Cells(1, 1).Value = 0
Call saiki(1)
Range("A1").Select
End Sub
Sub saiki(ByVal n As
Integer)
Dim b(1) As Integer
Dim j As Integer
a(n) = 0
While a(n) <= 9
If n < 4 Then
Call saiki(n + 1)
Else
For j = 0 To 1
b(j) = 0
Next j
For j = 1 To 4
If a(j) <= 1 Then
b(a(j)) = 1
End If
Next j
If b(0) + b(1) = 2 Then
Cells(1, 1).Value = Cells(1, 1).Value + 1
For j = 1 To 4
Cells(Cells(1, 1).Value, j + 1).Value = a(j)
Next j
Range("B" & Cells(1, 1).Value).Select
End If
End If
a(n) = a(n) + 1
Wend
End Sub
Option Explicit
Sub Macro2()
Sheets("Sheet2").Select
Cells(1, 1).Value = 0
Dim n As Integer
Dim nn As String
Dim n0 As Integer
Dim a(1) As Integer
Dim j As Integer
For n = 10 To 9999
For j = 0 To 1
a(j) = 0
Next j
nn = Right(Str(n), Len(Str(n)) - 1)
For j = 1 To Len(nn)
n0 = Val(Mid(nn, j, 1))
If n0 <= 1 Then
a(n0) = 1
End If
Next j
If a(0) + a(1) = 2 Then
Cells(1, 1).Value = Cells(1, 1).Value + 1
Cells(Cells(1, 1).Value, 2).Value = n
Range("B" & Cells(1, 1).Value).Select
End If
Next n
Range("A1").Select
End Sub
「浜田明巳」 09/05 12時26分受信
更新9/23
（別解）（２）余事象を使って解く．
１０～９９９９まで９９９０個ある．
i). ２桁の場合，１０以外であればよいので，１１～９９まで８９個ある．
ii). ３桁の場合，
ア). １が３個の場合，１１１の１個．
イ). ０が２個，１が０個の場合，ａ００（ａ＝２，３，４，………，９）の８個．
ウ). ０が０個，１が２個の場合，１１ａ，１ａ１，ａ１１（ａ＝２，３，４，……，９）
の３種類であるので，
３×８＝２４（個）
エ). ０が１個，１が０個の場合，ａｂ０，ａ０ｂ（ａ，ｂ＝２，３，４，………，９）
の２種類であるので，
２×８２＝１２８（個）
オ). ０が０個，１が１個の場合，ａｂ１，ａ１ｂ，１ａｂ（ａ，ｂ＝２，３，４，………，９）
の３種類であるので，
３×８２＝１９２（個）
カ). ０が０個，１も０個の場合，ａｂｃ（ａ，ｂ，ｃ＝２，３，４，………，９）
であるので，
８３＝５１２（個）
iii). ４桁の場合，
ア). １が４個の場合，１１１１の１個．
イ). ０が３個，１が０個の場合，ａ０００（ａ＝２，３，４，………，９）の８個．
ウ). ０が０個，１が３個の場合，１１１ａ，１１ａ１，１ａ１１，ａ１１１（ａ＝２，３，４，……，９）
の４種類であるので，
４×８＝３２（個）
エ). ０が２個，１が０個の場合，ａｂ００，ａ０ｂ０，ａ００ｂ（ａ，ｂ＝２，３，４，………，９）
の３種類であるので，
３×８２＝１９２（個）
オ). ０が０個，１が２個の場合，
ａｂ１１，ａ１ｂ１，ａ１１ｂ，１ａｂ１，１ａ１ｂ，１１ａｂ（ａ，ｂ＝２，３，４，………，９）
の６種類であるので，
６×８２＝３８４（個）
カ). ０が１個，１が０個の場合，
ａｂｃ０，ａｂ０ｃ，ａ０ｂｃ（ａ，ｂ，ｃ＝２，３，４，………，９）
の３種類であるので，
３×８３＝１５３６（個）
ａｂｃ１，ａｂ１ｃ，ａ１ｂｃ，１ａｂｃ（ａ，ｂ，ｃ＝２，３，４，………，９）
の４種類であるので，
４×８３＝２０４８（個）
ク). ０が０個，１も０個の場合，ａｂｃｄ（ａ，ｂ，ｃ，ｄ＝２，３，４，………，９）
であるので，
８４＝４０９６（個）
故にまとめると，
９９９０－{８９＋(１＋８＋２４＋１２８＋１９２＋５１２)＋(１＋８＋３２＋１９２＋３８４＋１５３６＋２０４８＋４０９６)}
＝９９９０－(８９＋８６５＋８２９７)
＝９９９０－９２５１＝７３９（個）
NO3「新俳人澄朝」09/06 16時26分受信 更新9/23
NO4「ｽﾓｰｸﾏﾝ」 09/10 17時46分受信
「ｽﾓｰｸﾏﾝ」 09/11 22時45分受信 更新9/23
（１）0000から9999までの10000通りの電話番号のうち、０，１が少なくとも１回ともに現れる番号は全部でいくつあるか。
4個、1,0のとき…2^4-2=14
3個、1,0のとき…4*8*(2^3-2)=192
2個、1,0のとき…4C2*8^2*(2^2-2)=768
合計=768+192+14=974 個
「ｽﾓｰｸﾏﾝ」 09/16 20時41分受信
「ｽﾓｰｸﾏﾝ」 09/19 01時01分受信 更新9/23
（２）０から9999までの整数のうちで、０，１が少なくとも１回ともに現れる整数はいくつあるか。
二桁以上しかあり得ない…
xx…10…=1
xxx…1xx+yxx=2*10-1+8*2=35
xxxx…1xxx+yxxx=11xx+10xx+1yxx+y1xx+y0xx+yyxx
=2*10-1+10^2+8*(2*10-1)+8*(2*10-1)+8*(2*10-1)+8^2*2
=20-1+100+3*8*19+128
=19*25+100+128
=703
合計=703+35+1=739 個
ってことですかぁ...^^;...Orz～想いの外、手こずりました...上手い方法を知りたいです ^^
Good Night ☆
NO5「にいばりZ12」09/11
01時09分受信 更新9/23
（１）0000から9999までの10000通りの電話番号のうち、０，１が少なくとも１回ともに現れる番号は全部でいくつあるか。
A=0,B=1,K=2～９とします
ＡとＢは必ず入っていなければならないので
数字のパターンはＡＡＡＢ，ＡＡＢＢ，ＡＢＢＢ，ＡＢＫＫ，ＡＡＢＫ，ＡＢＢＫの６種類になり各数の順列を求めればいいことになります。
ＡＡＡＢ，ＡＡＢＢ，ＡＢＢＢは２進数で0001から1110の１４通り
{4!/3!+4!/(2!*2!)+4!/3!=14とも計算できます｝
ＡＢＫＫは4！/2！×８×8＝768（Ｋが８個あるので）
ＡＡＢＫは4！/2！×8＝96
ＡＢＢＫも4！/2！×8＝96
合計は14+768+96+96＝974通りになります。
（２）０から9999までの整数のうちで、０，１が少なくとも１回ともに現れる整数はいくつあるか。
（1）と同様に計算します
A=0,B=1,K=2～９とします
ＡとＢは必ず入っていなければならないので
数字のパターンはＡＡＡＢ，ＡＡＢＢ，ＡＢＢＢ，ＡＢＫＫ，ＡＡＢＫ，ＡＢＢＫの６種類になり各数の順列を求めればいいことになります。
ここで、Ａが先頭にきてはいけないことに注意し
ＡＡＡＢ，ＡＡＢＢ，ＡＢＢＢは２進数で10から1110から11と１１１を除く１１通り
ＡＢＫＫは4！/2！×８×8-3！/2！×８×8＝576通り・・・・Ａが先頭に来る場合の数を引きます
ＡＡＢＫは4！/2！×8-2！×8＝80通り・・・・ＡＡが先頭に来る場合の数を引きます
ＡＢＢＫは4！/2！×8-3！/2！×８＝72通り・・・・Ａが先頭に来る場合の数を引きます
合計は11+576+80+72＝739通りになります。
NO6「Iga」
09/14 22時43分受信 更新9/23
Ｉｇａです。珍しく続けて解答します。とりあえず場合分けをして数えました。
（１）0000から9999までの10000通りの電話番号のうち、０，１が少なくとも１回ともに 現れる番号は全部でいくつあるか。
①００００～０９９９
・０１□□ 十の位、一の位ともに１０通りなので １０×１０＝１００通り
・０□１□ 百の位は１を除いた９通り、一の位は１０通りで ９×１０＝ ９０通り
・０□□１ 百の位、十の位ともに１を除くので９通り ９× ９＝ ８１通り
合計して、１００＋９０＋８１＝２７１通り
②１０００～１９９９
・１０□□
・１□０□
・１□□０
これらは、①の０と１を入れ替えたものなので、 ①と同じく２７１通り
③２０００～２９９９
・２０１□ １０通り
・２０□１ １以外の ９通り
・２□０１ ０以外の ９通り
・２１０□ １以外の ９通り
・２１□０ ０以外の ９通り
・２□１０ １，０以外の ８通り
合計して、 １０＋９＋９＋９＋９＋８＝５４通り
④３０００～９９９９
２０００番台（③）と同様なので、③とあわせて ５４×８＝４３２通り
⑤ ①、②、④を合計して、
２７１×２＋４３２＝９７４通り
（２）０から9999までの整数のうちで、０，１が少なくとも１回ともに現れる整数はいくつあるか。
（１）の場合の数から上位が０の場合を除けばいいので、
(a) ０～ ９ ０通り
(b) １０～９９ １０のみの １通り
(c) １００～９９９
・１０□ １０通り
・１□０ ９通り
・□０１ ８通り
・□１０ ８通り
合計して １０＋９＋８＋８＝３５通り
これに、（１）の②、④を加えると
１＋３５＋２７１＋４３２＝７３９通り
（自信がなかったので、エクセルで００００～９９９９についてカウントして確かめました。）
皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。
