Search

Computer House Random
Computer House Random
  • Randomについて
  • ブログ
  • Project
  • 作品紹介
  • 部員紹介

任意の自然数 n について, 全ての桁の数字が奇数である n 桁の 5^n の倍数が存在することを示せ.

【25日目】既に曖昧な高校数学で学ぶ使えない証明問題

ytv
最終更新 2020/04/13

$n = 1$ のとき,

5 は 全ての桁の数字が奇数で,

$5^1 (= 5)$ の倍数かつ 1 桁の数です.

$n = 2$ のとき,

75 は 全ての桁の数字が奇数で,

$5^2 (= 25)$ の倍数かつ 2 桁の数です.

$n = 3$ のとき,

375 は 全ての桁の数字が奇数で,

$5^3 (= 125)$ の倍数かつ 3 桁の数です.

問題

任意の自然数 $n$ について, すべての桁の数字が奇数である $n$ 桁の $5^n$ の倍数が存在することを示せ.

証明

高校数学の範囲内での証明なので, 大学数学っぽい厳密性は考慮していません. ごめんなさい... なあなあでお願いします...

数学的帰納法によって示す.

① $n = 1$ のとき

自明である. (5 が題意を満たす)

② $n = l ( l\geqq2, l\in\mathbb{N}) $ で命題が成立すると仮定したとき

$5^l$ の倍数で, 各桁の数字が奇数である $l$ 桁の自然数を

$m = a \times 5^l (a\in\mathbb{N}) $ とする.

このとき,

$\mathbb{A} = $ {$b \times 10^l + m | b = 1, 3, 5, 7, 9$}

の各要素は各桁の数字が全て奇数である $l+1$ 桁の自然数であるから, これらの中に $5^{l+1}$ の倍数があることを示せばよい.

各要素を $5^l$ で割ると

$\mathbb{A’} = $ {$b \times 2^l + a | b = 1, 3, 5, 7, 9 $}

となる. ここで 5 を法として

$i \times 2^l + a \equiv j \times 2^l + a$

となる自然数 $i, j (i, j \in b, i < j)$ が存在すると仮定すると,

$(j - i) \times 2^l \equiv 0$ ・・・(式 1)

となるが, 任意の $l,i, j$ の組について $2^l$ と $(j - i)$ は 5 と互いに素であるから (式 1) は成立し得ない. よって, $\mathbb{A’}$ の各要素はそれぞれ 5 を法として互いに合同ではないので, これらの中に 5 の倍数は 1 つ存在する.

従って, $\mathbb{A}$ の要素の中には 1 つ $5^{l+1}$ の倍数が存在する.

①, ②より数学的帰納法から題意は示された.

追加問題

任意の正の奇数について, 各桁の数字が全て奇数である倍数が存在することを示せ.

証明

① 5 の倍数以外の奇数について

5 の倍数以外の奇数からなる集合を $\mathbb{K}$ とする. また自然数 $n$ を $m$ 回繰り返した数を $Rep(n, m)$ と定義する. 例えば

$Rep(33, 4) = 33333333$

である. ここで $\forall k \in \mathbb{K}$ について,

$\mathbb{M} = $ {$Rep(1, t) | t = 1, 2, 3, … , k + 1$}

を考える. 鳩ノ巣原理より, $\mathbb{M}$ の要素の中には $k$ を法として合同な組が少なくとも 1 つ存在するので, これらを $i, j \in t, i < j$ として

$Rep(1, i), Rep(1, j)$

とする. このとき,

$Rep(1, j) - Rep(1, i) = Rep(1, j - i) \times 10^i$

となり, これは $k$ の倍数でないといけない. $k$ と $10^i$ は互いに素であるから, $Rep(1, j - i)$ は $k$ の倍数であり, 各桁の数字が全て奇数である.

② 5 の倍数の奇数について

5 の倍数の奇数からなる集合を

$\mathbb{F} = $ {$b \times 5^l | b \in \mathbb{K}, l \in \mathbb{N}$}

とする. ここで $\forall f = b \times 5^l \in \mathbb{F}$ について先ほどの問題より,
すべての桁の数字が奇数である $l$ 桁の $5^l$ の倍数が存在するので, これを $x$ とする. そして,

$\mathbb{X} = $ {$Rep(x, t) | t = 1, 2, 3, … , b + 1$}

を考える. 鳩ノ巣原理より, $\mathbb{X}$ の要素の中には $b$ を法として合同な組が少なくとも 1 つ存在するので, これらを $i, j \in t, i < j$ として

$Rep(x, i), Rep(x, j)$

とする. このとき,

$Rep(x, j) - Rep(x, i) = Rep(x, j - i) \times 10^{li}$

となり, これは $b$ の倍数でないといけない. $b$ と $10^{li}$ は互いに素であるから, $Rep(x, j - i)$ は $b$ の倍数であり, また $b$ と $5^{l}$ も互いに素であることから, $Rep(x, j - i)$ は $f$ の倍数であり, 各桁の数字が全て奇数である.

よって①, ②より題意は示された.

あとがき

解けましたでしょうか ? これは, 高 3 の頃にふと思いついた問題で案外簡潔に証明できたと思っていたものでした. 正直, あっている自信は無いのでもしより良い証明方法があったり, そもそも命題が成り立たないよって分かった方は是非ご連絡ください. 場合によっては土下座しないといけません. よろしくおねがいします.

競プロって結構整数問題を含んでいて, つらいなぁと感じます…

新歓2020

部員による新歓記事
数学 雑談 新歓ブログリレー2020 記事を共有
Avatar
ytv

弐寺やろうな

    Computer House Random はパソコンによる創作活動を行っている大阪府立大学の部活動です

    Avatar
    ytv

    弐寺やろうな

      数学 雑談 新歓ブログリレー2020 記事を共有

      News

      ICPC2020参加記

      ICPC
      pngn
      2021/05/08

      コンピュータハウスランダムってどんな部活?

      【1日目】5分でわかるランダムのこと
      NEGI
      最終更新 2020/04/18

      はじめまして、らんだむちゃんです!

      自己紹介と最初の動画
      らんだむちゃん
      最終更新 2020/03/19

      作品紹介

      【18日目】難波駅構内をblenderで再現してみた

      途中経過
      うっかり侍
      2021/08/31

      【17日目】ウィルダネスアドベンチャー(?)

      いつかリベンジする
      クマイザサ
      最終更新 2021/08/30

      【16日目】CHICKEN NIGHTS

      正直、すまんかった
      Marcus
      最終更新 2021/08/29

      Tag Cloud

      作品紹介 (48) 新歓ブログリレー2021 (46) 新歓ブログリレー2020 (37) 競技プログラミング (34) 新歓ブログリレー2022 (33) 雑談 (32) ゲーム (30) ゲーム制作 (24) 競プロ勉強会 (22) 作品展示リレー2021夏 (19)

      最新の投稿

      【38日目】OneDriveでファイルを管理して授業や部活で活用しよう!

      オム大、クラウド1TBくれるってよ
      Kwang
      最終更新 2022/04/29

      【37日目】受けループやらメタビートやらのすゝめ

      (ゲームにおいては)人の嫌がることをするのが最も楽しい
      クマイザサ
      2022/04/28

      【36日目】マイクラのMODパックで遊ぼう

      MODパックの導入は難しそうって思ってない?
      neuron
      2022/04/27

      【35日目】大阪公立大学 中百舌鳥図書館利用のススメ

      かなり長め
      Rikky
      2022/04/26
      READ MORE

      関連記事


      新入生必見!おすすめノートパソコン2020

      【29日目】まだ大学用のノートPC購入してない人向け

      Avatar

      PARIPIPPI CHALLENGE 2020 解説

      【28日目】ステガノグラフィーを用いた暗号化手法

      Avatar

      なつのおもいで

      【22日目】去年の夏、合宿に行きました

      Avatar

      YouTube Premiumを3ヶ月間使った感想

      【21日目】YouTube Premiumのいいところと悪いところ

      Avatar

      第 1 回 チキチキ☆ランダムって外から見たらどうなんじゃい !!? って聞いてみま SHOW

      【16日目】ゲスト : 情報工学課程 新 3 回生 ヤマダさん (仮称)

      Avatar

      ほい卒でもわかる!歴史の刻み方

      [14日目]人生

      Avatar

      Random
      Randomについて
      ライセンス
      Privacy Policy
      お問い合わせ
      部員専用サイト
      Project
      新入生向けブログリレー2022
      作品展示リレー2021夏
      競プロ勉強会
      Web
      らんだむちゃん
      ブログ
      作品紹介
      LT会
      グラフィック
      DTM
      タグ一覧
      Copyright © 2020 Computer House Random
      引用
      コピー ダウンロード