中に、9 以下の任意の正整数 q について、
「この数には q 未満の数字が q 回以上登場する」
という命題が真であるを満たすものはいくつあるでしょう、求値してください。
一応、例示も置いときます。
例１： 602214076 は、
1 未満の数字が 2 回、2 未満の数字が 3 回、3 未満の数字が 5 回、4 未満の数字が 5 回、
5 未満の数字が 6 回、6 未満の数字が 6 回、7 未満の数字が 8 回、8 未満の数字が 9 回、
9 未満の数字が 9 回、登場するので条件を満たす。
例２： 299792458 は、1 未満の数字が 0 回だったり、7 未満の数字が 4 回だったり、偽に
なる命題が存在するので条件を満たさない。
例３： 101325 は、9 桁表示の 000101325 で個数をカウントするので、条件を満たす。
（コメント） 条件を満たす最大の数は、「８７６５４３２１０」かな？
ＧＡＩ さんからのコメントです。（令和６年９月１１日付け）
99,999,999(個)でしょうか？
1〜10 では、9(個)
1〜10^2 では、80(個)
1〜10^3 では、700(個)
1〜10^4 では、6,000(個)
1〜10^5 では、50,000(個)
1〜10^6 では、400,000(個)
1〜10^7 では、3,000,000(個)
1〜10^8 では、20,000,000(個)
1*10^8+1〜2*10^8では 15,217,031(個)
2*10^8+1〜3*10^8では 13,119,879(個)
3*18^8+1〜4*10^8では 11,708,091(個)
4*10^8+1〜5*10^8では 10,546,875(個)
5*10^8+1〜6*10^8では 9,453,125(個)
6*10^8+1〜7*10^8では 8,291,909(個)
7*10^8+1〜8*10^8では 6,880,121(個)
8*10^8+1〜9*10^8では 4,782,968(個)
9*10^8+1〜10^9-1では 0(個)
よって、10^8+1〜10^9-1では、79,999,999(個)
以上から、1〜999,999,999で条件を満たすものは、20,000,000+79,999,999=99,999,999(個)
の模様です。正しく、9に纏わるDD++さんらしい問題でした。
DD++ さんからのコメントです。（令和６年９月１１日付け）
正解です、お見事！
問題も正解も投稿日時もキューだらけの問題でした。
りらひいさんからのコメントです。（令和６年９月１２日付け）
きっとスマートな解法があるのでしょうが、思いつかないので力技です。
n ≧ m ≧ 1 とする。0、1、・・・、m の m+1 種類の数を重複を許して一列に n 個並べると
き、1 ≦ q ≦ m となる任意の整数 q について、q 未満の数を q 個以上含むような並べ方の
数を f(m,n) とおく。
[1] m = 1 のとき、条件を満たさないものは並べる数のすべてが "1" となる場合の 1 通りな
ので、f(1,n) = 2^n - 1 となる。
[2] m ≧ 2 のとき、並べる数のなかの "m" の個数を k 個として、k で場合分けする。
k＞n-m の場合は、m 未満の数が m 個未満となってしまうため、条件を満たさない。
0 ≦ k ≦ n-m の場合、数 "m" の配置方法が nCk 通りあり、その各々に対して残りの数
の並べ方が f(m-1,n-k) 通りある。よって、f(m,n) = Σ[k=0,...,n-m] nCk * f(m-1,n-k) となる。
[1]、[2] を用いて順次計算していくと、次のようになる。
f(1,1) = 1 、f(1,2) = 3 、f(1,3) = 7 、f(1,4) = 15 、f(1,5) = 31 、f(1,6) = 63 、f(1,7) = 127
f(1,8) = 255 、f(1,9) = 511
f(2,2) = 3 、f(2,3) = 16 、f(2,4) = 61 、f(2,5) = 206 、f(2,6) = 659 、f(2,7) = 2052
f(2,8) = 6297 、f(2,9) = 19162
f(3,3) = 16 、f(3,4) = 125 、f(3,5) = 671 、f(3,6) = 3130 、f(3,7) = 13686 、f(3,8) = 57867
f(3,9) = 240049
f(4,4) = 125 、f(4,5) = 1296 、f(4,6) = 9031 、f(4,7) = 54062 、f(4,8) = 301321
f(4,9) = 1616764
f(5,5) = 1296 、f(5,6) = 16807 、f(5,7) = 144495 、f(5,8) = 1059261 、f(5,9) = 7196785
f(6,6) = 16807 、f(6,7) = 262144 、f(6,8) = 2685817 、f(6,9) = 23343742
f(7,7) = 262144 、f(7,8) = 4782969 、f(7,9) = 56953279
f(8,8) = 4782969 、f(8,9) = 100000000
f(9,9) = 100000000
求めるものは、 m = 9、n = 9 の場合の数から並べる数のすべてが "0" となる 1 通りを
除いたものなので、
f(9,9)-1 = 99999999（通り） となる。
＃計算結果を見ると、 f(m,m) = (m+1)^(m-1) になるみたいですね。
DD++ さんからのコメントです。（令和６年９月１３日付け）
なるほど、そういうこともできるんですね。結論にスパッと切り込む方法としては、
(314159265, 425260376, 536371487, ……, 203048154)
のように数字を 1 つずつずらした数からなる 10 個組を作ると、9 個の命題のうち何個満た
されるかが全て異なることを証明することでしょうか。
そうすれば 999,999,999 個のうちゾロ目を除いた 999,999,990 個中 10 個に 1 個が条件を
満たすことから 99,999,999 個であるとすぐにわかります。
まあ、満たされる命題数が全て異なることの証明が手間になるわけですけども。
ＧＡＩ さんからのコメントです。（令和６年９月１３日付け）
りらひいさんの漸化式が面白かったので、これでいろいろ遊んでいたら、OEISで「A373086」
がたまたまヒットした。
ここにリンクで張られた論文が関連するように思われるんですが、自分にはわからない部
分が多くて手ごわくて、りらひいさんならよく理解されるのではないかと思いました。
以下、工事中！
