|
uchinyan |
|
(結論が間違っていました。#28055, #28063をご覧ください。なお、誤りの箇所を明示しました。)
少し時間が取れたので、#28047のアプローチで詰めてみました。 ただ、長くなってしまったし、ちょっと論理的にも不安です。どうかなぁ．．． 0 以上の整数 n を10進数表記したときの各桁の和を s(n) とします。 すると、a, b を 0 以上の整数として、s には次の性質があります。 1) a が 1 桁の数ならば s(a) = a 2) s(10^b * a) = s(a) 3) b が 1 桁の数ならば s(10a + b) = s(10a) + s(b) = s(a) + s(b) 4) s(a + b) <= s(a) + s(b), 等号は a + b の計算で桁の繰上りがない場合 5) s(a * b) <= s(a) * s(b), 等号は a * b の計算で桁の繰上りがない場合 1), 2)は、s の定義から明らかでしょう。 3)も、b が 1 桁の数なのと、s の定義及び2)から明らかでしょう。 4)の証明 桁に関する数学的帰納法を使います。 a, b が 1 桁の数、0 〜 9、の場合には、実際にやってみれば、等号条件も含めて成立します。 a が k 桁以下の数、b が m 桁以下の数で、成立するとします。 この仮定の下で、a を k+1 桁の数としてみます。 a = 10c + d、c は k 桁の数、d は 1 桁の数、 b = 10e + f、e は m-1 桁の数、f は 1 桁の数、 と書けるので、 s(a + b) = s((10c + d) + (10e + f)) = s(10(c + e) + (d + f)) ここで、0 <= d, f <= 9 なので、d + f は、1 桁の数か 2 桁の数になります。 ・d + f が 1 桁の数の場合 1), 3)より、 s(a + b) = s(10(c + e) + (d + f)) = s(c + e) + s(d + f) = s(c + e) + (d + f) c は k 桁の数、e は m-1 桁の数、だったので、帰納法の仮定から、 s(a + b) = s(c + e) + (d + f) <= s(c) + s(e) + d + f 等号は、c + e に桁の繰上りがない場合です。さらに、1), 3)より、 s(c) + s(e) + d + f = (s(c) + s(d)) + (s(e) + s(f)) = s(10c + d) + s(10e + f) = s(a) + s(b) となり、 s(a + b) <= s(a) + s(b) 等号は、d + f に桁の繰上りがないので、a + b に桁の繰上りがない場合になります。 ・d + f が 2 桁の数の場合 d + f = 10g + h, ただし、g, h は 1 桁の数 と書けるので、 1), 3)より、 s(a + b) = s(10(c + e) + (d + f)) = s(10(c + e + g) + h) = s(c + e + g) + s(h) = s(c + e + g) + h c は k 桁の数、e は m-1 桁の数、g は 1 桁の数だったので、e + g は高々 m 桁の数であることに注意すると、帰納法の仮定から、 s(a + b) = s(c + e + g) + h =<= s(c) + s(e + g) + h <= s(c) + s(e) + s(g) + h 等号は、c + e + g に桁の繰上りがない場合です。さらに、1), 3)より、 s(c) + s(e) + s(g) + h = s(c) + s(e) + s(10g + h) = s(c) + s(e) + s(d + f) d + f に帰納法の仮定を使って < s(c) + s(e) + s(d) + s(f) = (s(c) + s(d)) + (s(e) + s(f)) = s(10c + d) + s(10e + f) = s(a) + s(b) となり、 s(a + b) < s(a) + s(b) d + f に桁の繰上りがあるので、等号は成立しません。 以上より、a が k+1 桁の数、b が m 桁以下の数で、不等式が示せました。 さらに、与えられた式は a, b について対称なので、a が k 桁以下の数、b が m+1 桁の数の場合は、a と b とを入れ替えればOKです。 以上で証明は終わりです。 5)の証明 やはり、桁に関する数学的帰納法を使います。 a, b が1桁の数、0 〜 9、の場合には、実際にやってみれば、等号条件も含めて成立します。 a が k 桁以下の数、b が m 桁以下の数で、成立するとします。 この仮定の下で、a を k+1 桁の数としてみます。 a = 10c + d、c は k 桁の数、d は 1 桁の数、 b = 10e + f、e は m-1 桁の数、f は 1 桁の数、 と書けるので、 s(a * b) = s((10c + d) * (10e + f)) = s(100 * ce + 10 * (de + cf) + df) 4)より <= s(100 * ce) + s(10 * (de + cf)) + s(df) 2)より = s(ce) + s(de + cf) + s(df) 再び、4)より <= s(ce) + s(de) + s(cf) + s(df) ここで、c は k 桁の数、d は 1 桁の数、e は m-1 桁の数、f は 1 桁の数、なので、帰納法の仮定が使えて、 <= s(c) * s(e) + s(d) * s(e) + s(c) * s(f) + s(d) * s(f) = (s(c) + s(d)) * (s(e) + s(f)) 3)を使って = (s(10c + d)) * (s(10e + f)) = s(a) * s(b) 等号は、いろいろありましたが、a * b の計算で一回でも桁の繰上りがあった場合には成立しないので、 結局は、a * b に桁の繰上りがない場合です。 以上より、a が k+1 桁の数、b が m 桁以下の数で、不等式が示せました。 さらに、与えられた式は a, b について対称なので、a が k 桁以下の数、b が m+1 桁の数の場合は、a と b とを入れ替えればOKです。 以上で証明は終わりです。 さて、苦労しましたが、ここまで来ればもう少しです。 s(n) = 1000, s(n^2) = 1000^2 だったので、 s(n^2) = (s(n))^2 つまり、等号が成立する場合です。そこで、n^2 の計算で桁の繰上りがあってはいけません。 実際の計算を考えてみると、4 以上の数字がどこかの桁にある場合には、明らかに 4^2 = 16 で繰り上がるので、すべての数字は 3 以下です。 この場合、n を k 桁とすると、 0 < s(n) <= 3k となり、k >= 1000/3 > 333 で、n は 334 桁以上の数です。 この k 桁の数で、より具体的に、桁の数字が 0 でない個数は、 334 個；3 が 333 個で 1 が 1 個、又は 3 が 332 個で 2 が 2 個 〜 1000 個：1 が 1000 個 になります。 次に n^2 の計算を考えてみると、 n = 10^(k-1) * a(k-1) + 10^(k-2) * a(k-2) + ... + 10^2 * a(2) + 10^1 * a(1) + 10^0 * a(0) = ��[i=0,k-1]{10^i * a(i)} として、 n^2 = (��[i=0,k-1]{10^i * a(i)})^2 = ��[0<=i,j<=k-1]{10^(i+j) * a(i) * a(j)} = ��[m=0,2k-2]{10^m * ��[max(0,m-(k-1))<=i<=min(k-1,m)]{a(i) * a(m-i)}} 桁の繰上りがあってはいけないので、m = 0, ..., 2k-2 に対して、 0 <= ��[max(0,m-(k-1))<=i<=min(k-1,m)]{a(i) * a(m-i)} <= 9 特に、m = k-1 の場合、 0 <= ��[0<=i<=k-1]{a(i) * a(k-1-i)} <= 9 0 <= a(i) <= 3 を考慮すると、上記の k 項の和のうち 0 でないものは、高々 9 項で、少なくとも k-9 項は 0 でなければなりません。 a(i) に関して考えると、a(i) * a(k-1-i) は、i <-> k-1-i に関して対称なので、少なくとも (k-9)/2 or (k-8)/2 個が 0 でなければなりません。 そこで、最大 (k+9)/2 or (k+8)/2 個が 0 ではありません。 (ここからが誤りです。「(k+9)/2 が 1000 を超えないので」というのは、論理的に根拠がありません。) したがって、先ほどの 0 でない桁の個数から、(k+9)/2 が 1000 を超えないので、 k/2 < (k+9)/2 <= 1000 これから、 333 < k < 2000 です。 (ここまでが誤り。) その一方で、 0 < s(n) < 10^k 0 < s(n^2) = (s(n))^2 < 10^(2k) なので、 0 < s(n^2) = 1000^2 = 1000000 <= 9 * 2k = 18k k >= 1000000/18 = 500000/9 > 55555 (ここからも誤り。結局、k > 55555 しかいえず、存在するかどうかは分からないままです。) これは矛盾です。 したがって、s(n) = 1000, s(n^2) = 1000^2 となるような n は存在しません。 (ここまでが誤り。) 最後の評価が少し不安です。 いずれにせよ、もう少しうまくできそうですね。 |
|
ネコの住む家
8月10日（木） 20:11:24
MAIL:uchi@sco.bekkoame.ne.jp 28052 |