次の整数の問題の解説をお願いします

質問

問題

任意の正の整数nに対して,次の(A)と(B)をともに満たす正の整数Nが存在することを示せ.
(A)Nはn桁であり，各桁の数字は3または8である。
(B)Nは2^nで割り切れる。

数学的帰納法で解くと思うのですが、漸化式がどうもたちません。

お願いします。

回答No.6

178-tall · ベストアンサー

まだ、仕込みの途中？
大雑把にでも、まとめておく。

実は…これが成立…
　　　　　↓
>一桁の奇数 {1, 3, 5, 7, 9} から d 、一桁の偶数 {2, 4, 6, 8} から e を勝手に選抜。
>任意の正整数 n に対して、次の (A) と (B) をともに満たす正の整数 N が存在する。
>　(A) N は n 桁で，各桁の数字は d または e である。
>　(B) N は 2^n で割り切れる。

以下のような数的帰納のリピートで検証できる模様…。

[素材]

偶数 e ：　e*10^0 = (e/2)*2^(0+1)
　　　　if　　e*10^k = p*2^(k+1)
　　　　then　e*10^(k+1) = 10*p*2^(k+1) = 5p*2^(k+2)

奇数 d ：　d*10^0 = { (d-1)/2}*2 + 2^0
　　　　if　　d*10^k = q*2^(k+1) + 2^k
　　　　then　d*10^(k+1) = 10*{q*2^(k+1) + 2^k}
　　　　　　　= 5p*2^(k+2) + 10*2^(k+1)
　　　　　　　= (5p+2)*2^(k+2) + 2^(k+1)

[アルゴリズム]

(0) N(0) = e
(1) 題意を満たす n 桁 の N(n) = M*2^n を想定。
(2) 分岐。
　　M が偶数なら、N(n+1) = e*10^(n+1) + N(n)
　　M が奇数なら、N(n+1) = d*10^(n+1) + N(n)

以下、割愛…。

回答No.5

noname#232491

(素人による　体当たり的途中経過です。これにはまだ解決力は無いでしょう）
n　(2^n)　Nとその因数分解　
1 (2) 8
2 (4) 88=４×２×１１
3 (8) 888＝８×３×３７
4 (16) 3,888＝１６×３^５
5 (32) 33,888＝３２×３×３５３
6 (64) 333,888＝６４×３×３７×４７
7 (128) 3,333,888＝１２８×２×３^２×１４４７（素数）
8 (256) 83,333,888＝２５６×１１×１０１×２９３
9 (512) 383,333,888＝５１２×７×１０６,９５７（素数）
10 (1024) 3,383,333,888＝１０２４×１１×３００,３６７（素数）
11 (2048) 33,383,333,888＝２０４８×８×１７９×１１,３８３（素数）
12 (4096) 833,383,333,888＝４０９６×８×７×３,６３３,２６３（素数）
13 (8192) 8,833,383,333,888＝８１９２×８×３×４４,９２８,９１１　
14 (16384) 88,833,383,333,888＝１６３８４×８×６７７,７４４,９２９
15 (32768) 888,833,383,333,888＝３２７６８×８×３４９×９,７１５２,７３
16 (65536) 8,888,833,383,333,888＝６５５３６×８×３×５,６５１,３６８,０６７
17 (131072) 88,888,833,383,333,888
＝１３１０７２×８×２×１７×２２,３０８,１６９,７５１
18 (262144) 888,888,833,383,333,888
＝２６２１４４×８×２×２,１１９,２７６,２４５,４４７
…
…
気になるのは　１１桁から先。２^n×８×～の形になっていて実質２^(n+3)でも割り切れるようです。

回答No.4

178-tall

実は…これが成立つ…の？

　　　　　　↓

一桁の奇数 {1, 3, 5, 7, 9} から d 、一桁の偶数 {2, 4, 6, 8} から e を勝手に選抜。

任意の正整数 n に対して、次の (A) と (B) をともに満たす正の整数 N が存在する。
　(A) N は n 桁で，各桁の数字は d または e である。
　(B) N は 2^n で割り切れる。

回答No.3

178-tall

まずは「アルゴリズム」らしきものから…。

(0) 題意を満たす n桁 の N(n) = M*2^n を想定してみる。

(1) 分岐。
　　M が偶数なら、N(n+1) = 8*10^(n+1) + N(n)
　　M が奇数なら、N(n+1) = 3*10^(n+1) + N(n)

「課題」は？

N(n+1) は 2^(n+1) で整除可…であることを示せ。

回答No.2

noname#199771

ヒントを書きますから考えてみてください。

・3×(10^n)を2^(n+1)で割ると余りが2^n
・8×(10^n)は2^(n+1)で割り切れる

に気がつくかどうかがポイント。
これを利用して、一つ前のnについて作ったNに上の
どちらかの数を加えた数を考えます。

これでnに関する数学的帰納法により証明できます。

回答No.1

maho_m

＞＞(A)Nはn桁であり，各桁の数字は3または8である。
これの意味がよく分からない。

たぶん、帰納法は関係なさそうな気がするがｗ