|
（１）0000から9999までの10000通りの電話番号のうち、
０，１が少なくとも１回ともに現れる番号は全部でいくつあるか。
（２）０から9999までの整数のうちで、
０，１が少なくとも１回ともに現れる整数はいくつあるか。 解答
上記サイトより Orz〜
・わたしの...
１）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 個
（２）０から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 個 想いの外、手こずりました...^^; ・uchinyanさんのもの Orz〜...そのいくつかをピックアップ...^^
(解法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 個
になります。
*いつもながら巧いなぁ☆ |
- >
- Yahoo!サービス
- >
- Yahoo!ブログ
- >
- 練習用
コメント（1）
