世界のナベアツな問題

1〜 $10^n$ のうち、mの倍数でもなく、mが位のどこにも含まれない個数は？

キモは0〜9のうちmでない数の個数は9であること。よって位の条件を満たす個数は $9^n$ 。実はこれだけで「とても大きな数になると、ほとんどの数はmをどこかに含む」ということがわかる。サイコロを何十回も振って一度も1の目を出さないようにすることは難しいのと、まあ似ているといえば似ている。

m=2だと？

$5\cdot{}9^{n-1}$ 。

m=3だと？

$\frac{2}{3}\cdot{}9^n+1$ 。+1は0をカウントせず $10^n$ をカウントしている影響。

m=4だと？

$63\cdot{}9^{n-2}$ 。n≧2なら $7\cdot{}9^{n-1}$ でもよい。

m=5だと？

$8\cdot{}9^{n-1}$ 。

m=6だと？

$69\cdot{}9^{n-2}+1$ 。+1は0をカウントせず $10^n$ をカウントしている影響。

m=7だと？

$[\frac{6}{7}\cdot{}9^{n}]+odd(n)+1$ 。ただしnが奇数なら $odd(n)=1$ 、nが偶数なら $odd(n)=0$ 。+1は0をカウントせず $10^n$ をカウントしている影響。

m=8だと？

$648\cdot{}9^{n-3}$ 。n≧3なら $8\cdot{}9^{n-1}$ でもよい。つまりm=5の場合とほぼ同じ。

m=9だと？

$8\cdot{}9^{n-1}+1$ 。+1は0をカウントせず $10^n$ をカウントしている影響。

だとは思うけど。