創作整数問題#32解法&創作整数問題#33

突然ですが、当サイトの(ブログでの)公開記事数がいつの間にか100を超えていました!道楽とは言いながら、1年経たないうちに100記事が達成できるとは思っていませんでした(笑)。密度の低い記事も多くあるかとは思いますが、継続してサイトを運営できて何よりです。

これからも頑張って更新していきますので、どうぞよろしくお願いします!



さて、本日は1月16日なので、$116$という数字に関して小話を。

$116^2+1$(5桁)は素数です。$116!+1$(191桁)も素数です(この形の素数を「階乗素数」と言います)。その他、$116+(116+1)^3$(7桁)や $2^{116}-116-1$(35桁)、$(116+1) \times 116^{116}-1$(242桁)なども素数だったりします。

因みに$117$を使用した大きな素数としては $2^{117} \times (117+1)!-1$(230桁)などが知られています。

一般に、$n^2+1$ 型の素数や $n!+1$ 型の「階乗素数」が無限に存在するかどうかは2018年現在、数論の未解決問題ですし、$116$のように $n^2+1$ と $n!+1$ がともに素数となるような正の整数$n$が無数に存在するかどうかも分かっていません。この辺りの内容はホームページの「整数第4章」にも掲載しているので、興味のある方は是非ご覧になってください。



《問題#33》

自然数$n$に対して、$1$から$n$までの自然数で$n$と互いに素なものの個数を$\phi (n)$とする。例えば $\phi (2)=1$、$\phi (3)=2$、$\phi (8)=4$ である。このとき以下の問に答えよ。

(1)関数$\phi (n)$が乗法的であることを利用して、$\phi (1200)$の値を求めよ。ここで関数$\phi (n)$が乗法的であるとは、$\phi (1)=1$ であり、かつ、互いに素な自然数$m$、$n$について$$\phi (mn)=\phi (m) \phi (n)$$がつねに成り立つことをいう。

(2)$n \geqq 3$ のとき、$\phi (n)$は任意の自然数$n$に対して偶数値をとることを示せ。

(創作問題)


当シリーズ初の数論的関数の登場です。本問で登場した関数$\phi (n)$は「オイラーのトーシェント関数」、「オイラーのファイ関数」などと呼ばれており、数論の分野では結構お目に掛かる機会の多い関数です。

今回の問題はかなり易しめです。

 

 

» 答えはこちら

(1)の答えは $\color{red}{\phi (1200)=320}$ です。

(2)は証明問題につき、次回掲載。

» 閉じる


創作整数問題#32(解き方)


次の覆面算を解け。$$\begin{align}\ \ \ \text{八十八}_{\ } \\
\ \ \ \text{百二十}_{\ } \\
\underline{{+)}_{\ }\ \ \ \text{千八百十}_{\ }} \\
\ \ \ \text{二千十八}_{\ } \end{align}$$ただし、各文字には$0$~$9$までの異なる整数が入るものとし、同じ文字には同じ数字が入り、異なる文字に同じ数字は入らない。また、最上位の文字に$0$が入ることはない。

完全にパズルの問題ですが、条件の整理の仕方は整数問題に通ずるものがあります。数千通りもの入れ方があるので、当てずっぽうだと結構時間が掛かると思います・・・。

便宜上、以下では問題の覆面算を次のようにアルファベットに書き直します。漢数字のままでも混乱しない方はそのまま解答して頂いて全く構いません。

$$\begin{align}\ \ \ \text{ABA}_{\ } \\
\ \ \ \text{CDB}_{\ } \\
\underline{{+)}_{\ }\ \ \ \text{EACB}_{\ }} \\
\ \ \ \text{DEBA}_{\ } \end{align}$$


まず、一の位に注目しましょう。$$A+2B \equiv A \pmod{10}$$ $$\therefore 2B \equiv 0 \pmod{10}$$ $$\therefore B=0 \ \text{or} \ 5 $$これより$B$の値で場合分けしていきます。

●   ●   ●

ア)$B=0$ のとき十の位には繰り上がらないので、十の位について$$C+D \equiv 0 \pmod{10}$$が成り立ちますが、これが成り立つのは$C$と$D$の和が$10$になるときに限ります。$$\therefore C+D=10 \tag{1}$$これより百の位に繰り上がるので、$$2A+C+1 \equiv E \pmod{10} \tag{2}$$が成り立ちます。次に千の位について、繰り上がりを考えると $D=E+1$ または $D=E+2$ となりますが、$(1)$より$C$と$D$の偶奇は一致し、$(2)$より$C$と$E$の偶奇は一致しないので、$D$と$E$の偶奇は一致しません。故に$$D=E+1 \tag{3}$$の場合に限ります。よって$(1)$、$(3)$により、$C=9-E$ となるのでこれを$(2)$に代入して$$2A+1-E \equiv E \pmod{10}$$ $$2A \equiv 2E \pmod{10} \tag{2′}$$を得ます。

また、各位の和について$3$を法として考えると、$$3A+3B+2C+D+E \equiv A+B+D+E \pmod{3}$$ $$\therefore A+B-2C \equiv 0 \pmod{3}$$両辺に$3$の倍数である$3C$を加えても$3$で割った余りは変わらないので、$$\therefore A+B+C \equiv 0 \pmod{3} \tag{4}$$が必要となります。$(1)、(3)$より、$E \leqq 8$ が必要であることに注意します。

$E=1$ のとき $D=2 \ (\because (3))$、$C=8 \ (\because (1))$、$2A=2 \ \text{or} \ 12 \ (\because (2′))$ $$\therefore A=1 \ \text{or} \ 6$$となりますが、いずれも$E$と重複する、$(4)$を満たさないなどにより不適です。

$E=2$ のとき $D=3$、$C=7$、$2A=4 \ \text{or} \ 14$ $$\therefore A=2 \ \text{or} \ 7$$となりますが、いずれも$E$や$C$と重複するので不適です。

$E=3$ のとき $D=4$、$C=6$、$2A=6 \ \text{or} \ 16$ $$\therefore A=3 \ \text{or} \ 8$$となりますが、いずれも$E$と重複する、$(4)$を満たさないなどにより不適です。

$E=4$ のとき $D=5$、$C=5$ と重複するので不適です。

$E=5$ のとき $D=6$、$C=4$ となり、$2A=0 \ \text{or} \ 10$ $$\therefore A=0 \ \text{or} \ 5$$となりますが、いずれも$B$や$E$と重複するので不適です。

$E=6$ のとき $D=7$、$C=3$ となり、$2A=2 \ \text{or} \ 12$ $$\therefore A=1 \ \text{or} \ 6$$となりますが、いずれも$E$と重複する、$(4)$を満たさないなどにより不適です。

$E=7$ のとき $D=8$、$C=2$ となり、$2A=4 \ \text{or} \ 14$ $$\therefore A=2 \ \text{or} \ 7$$となりますが、いずれも$C$や$E$と重複するので不適です。

$E=8$ のとき $D=9$、$C=1$ となり、$2A=6 \ \text{or} \ 16$ $$\therefore A=3 \ \text{or} \ 8$$となりますが、いずれも$E$と重複する、$(4)$を満たさないなどにより不適です。

したがって $B=0$ のときは覆面算の解が存在しません。次に $B=5$ の場合を調べます。

●   ●   ●

イ)$B=5$ のとき十の位に繰り上がるので、十の位について$$C+D+1 \equiv 0 \pmod{10}$$が成り立ちますが、これが成り立つのは$C$と$D$の和が$9$になるときに限ります。$$\therefore C+D=9 \tag{5}$$百の位に繰り上がるので、$$2A+C+1 \equiv E \pmod{10} \tag{6}$$が成り立ちます。ア)のときと同様、千の位について、繰り上がりを考えると $D=E+1$ または $D=E+2$ となりますが、$(5)$より$C$と$D$の偶奇は一致せず、$(6)$より$C$と$E$の偶奇は一致しないので、結局は$D$と$E$の偶奇が一致します。故に$$D=E+2 \tag{7}$$の場合に限ります。よって$(5)$、$(7)$により、$C=9-E$ となるのでこれを$(6)$に代入して$$2A+8-E \equiv E \pmod{10}$$ $$2(A-E-1) \equiv 0 \pmod{10}$$を得る。これより $A-E-1$ は$5$の倍数であることが必要なので、$$A-E-1 \equiv 0 \pmod{5} \tag{8}$$です。

また、$$\therefore A+B+C \equiv 0 \pmod{3} \tag{4}$$はここでも必要条件です。$(5)、(7)$より、$E \leqq 7$ が必要であることに注意します。

$E=1$ のとき $D=3 \ (\because (7))$、$C=6 \ (\because (5))$、$A-2 \equiv 0 \pmod{5} \ (\because (8))$ $$\therefore A=2 \ \text{or} \ 7$$となります。$A=2$ のときは$(4)$を満たさないため不適です。$A=7$ のとき、$$\begin{align} \ \ \ 757 \\
\ \ \ 635 \\
\underline{+)\ \ \ \ 1765}\\
\ \ 3157 \end{align}$$を解として得ます。

$E=2$ のとき $D=4$、$C=5$ となり、$B$と重複するので不適です。

$E=3$ のとき $D=5$ となり、$B$と重複するので不適です。

$E=4$ のとき $D=6$、$C=3$ となり、$A=0 \ \text{or} \ 5$ となりますが、いずれも$B$と重複する、$(4)$を満たさないなどにより不適です。

$E=5$ のとき$B$と重複するので不適です。

$E=6$ のとき $D=8$、$C=1$ となり、$A=2 \ \text{or} \ 7$ となりますが、いずれも$C$や$E$と重複するので不適です。

$E=7$ のとき $D=9$、$C=0$ となり、$A=3 \ \text{or} \ 8$ となりますが、いずれも$(4)$を満たさないので不適です。

●   ●   ●

以上ア)、イ)より、求める解は$$\begin{align} \color{red}{\ \ \ \ 757 \\
\ \ \ \ 635 \\
\underline{+)\ 1765}\ \ \ \\
\ \ 3157} \end{align}$$の一組のみとなります。



かなり息の長い計算となりましたが、やっていることはそれほど複雑ではありません。大抵の場合、覆面算の解はただ一つ(一意に定まる)なので、条件に当てはまるか否かを試していって候補をズバズバ消していけば、場合分けが少し面倒なだけで単純作業なので思考力はほとんど不要です。

覆面算の解法は基本的に「条件を出してからシラミ潰し」だと思います。定石なんてものがあるのかは知りませんが、条件を炙り出しやすい位の数に着目して式化し、絞り込みを掛ける、・・・というのがセオリーなのでは。あとは「数字根」(これは創作整数問題#20で扱いました)若しくは$3$の剰余に着目して候補を絞り込むことも忘れないようにしましょう。一般に、最高位の数字か、一の位の数字が絞り込みやすければ比較的容易に解けると思います。本問は一の位が絞り込めるので、繰り上がりに関してはかなり簡単に場合分けできたことと思います。

 

●   ●   ●   ●   ●

 

ここからは余談です。覆面算を語る際には外せない人物がいるのをご存知でしょうか?

その名はヘンリー・アーネスト・デュードニー(Henry Ernest Dudeney:1857~1930)。イギリス、イースト・サセックス州で生涯を過ごしたパズル作家であり数学者です。

Henry Ernest Dudeney (1857~1930)

覆面算というもの自体は古くから存在していたと思われますが、文字が意味を持った覆面算を世界に広めた人物はデュードニーだと言われています。月刊誌「The Strand Magazine」の1924年の6月号で彼が出題した覆面算が、恐らく世界で最も有名なものでしょう。それは次のようなものでした。$$\begin{align}\ \ \ \text{SEND}_{\ } \\
\underline{{+)}_{\ }\ \ \ \text{MORE}_{\ }} \\
\ \ \ \text{MONEY}_{\ } \end{align}$$何ともユーモラスな覆面算ですね!こちらは特に複雑な場合分けも不要で、今回解説した#32が解けた方ならすんなり解けると思います。

 

» デュードニーの覆面算の答えはこちら

答えは$$\begin{align} \color{red}{\ \ \ 9567 \\
\underline{+)\ 1085}\ \ \ \\
\ 10652} \end{align}$$の一組のみです。お楽しみ頂けたでしょうか?

» 閉じる


解が一意となる覆面算を作るのは大変ですが、結構楽しいものです。皆さんも作問に挑戦してみてはいかがでしょうか?

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です