すうがくなどについてのメモ

数学を調べたり、教えたり、教えてもらったことのメモです

「室外機問題」についての考察

こちらは12/6の日曜数学会のadvent calenderです。まず、投稿が遅れたことをtsujimotterさんにお詫びするとともに、このような機会を頂けたことを感謝します。また今回のテーマである「室外機問題」の考案者であり、この問題についてadvent calenderに書くことを快く許可して頂いた鯵坂もっちょさんにも感謝いたします。

 

「室外機問題」とは

一ヶ月くらい前のphicafe数学デーに参加した時に、鯵坂もっちょさんから「室外機問題」という問題を教えてもらいました。その問題は身近な日常の問題を数学的に考えるもので、なんとなく興味を惹かれて最近チラチラと考えていたのですが、見通しよく解けることが分かったので、今回はそれについて書きます。

f:id:triprod1829:20181219144426p:plain

(室外機のイメージです。問題そのものは純粋に数学の問題です)

 

なお、「室外機問題」は私が考えるより前に数学デーで解かれている問題で、ここに書くことはもしかしたらその時に考えられていた皆さまの考察の範囲内なのかもしれませんが、以下に書く内容は自分で考えたものなので、お許しを。

 さて、「室外機問題」とは次のような問題です:

「真夏の蒸し暑い夜、B氏はマンションの一室で寝ようとしている。B氏はエアコンが嫌いなため、窓を開けて寝ようとした。しかし、両隣の部屋の住人がエアコンをつけているようで、両隣の部屋のベランダに置かれた2つの室外機がブォンブォンと音を出し、B氏の睡眠を妨げている。
2つの室外機をM_1, M_2としよう。室外機M_1は5分音を出したのち5分静かになり、を10分の周期で繰り返し、室外機M_2は7分音を出したのち7分静かになり、を14分の周期で繰り返しているとする。この時、室外機の音が無い(B氏が静かな時間を過ごせる)時間の割合はどれだけあるか?ただし、簡単のため、2つの室外機が動き始めたタイミングは揃っているとする。」
(元々の問題の細部は忘れてしまったので、数学的内容が変わらない範囲で創作しています) 

f:id:triprod1829:20181220104241p:plain

(眠れないB氏のイメージ)

 

 「室外機問題」の解法

以下ではこの問題とその一般化の解法を書きます。この問題を考えていて個人的にグッときたポイントを先に書いておくと、この問題は初等整数論や、代数学の初歩的な知識を用いることにより、スッキリ捉えることができます。

室外機M_1の出す音の周期的な挙動を、\mathbb{Z}/10\mathbb{Z}を使って表しましょう。室外機M_1が最初の5分は音が出て、後半の5分は音が無い、という状況を、音が出ない時間に注目して S_1:=\{5,6,7,8,9\} \subset \mathbb{Z}/10\mathbb{Z}で表すことにします。同様に、室外機M_2の状況を、音が出ない時間に注目して S_2:=\{7,8,9,10,11,12,13\} \subset \mathbb{Z}/14\mathbb{Z}で表します。

室外機M_1, M_2は周期10,14を持つ(「分」は省略しました)ので、この二つを合わせると周期70(=10と14の最小公倍数)で音の有る無しの挙動が繰り返されます。このうちの音が無い時間がどれだけあるかを求めたいわけです。そこで、周期70で音が無い時間全体をSと置きます。この時、室外機の音が無い時間の割合は|S|/70なので、|S|が求まればこの問題は解けたことになります。

 さて、周期70のうちのあるタイミング xで音が無かった(つまり x \in S)としましょう。この条件は、 xをmod 10で見直すと x \hspace{2mm} \text{mod }10  \in S_1であり、かつ、mod 14で見直すと x \hspace{2mm} \text{mod }14  \in S_2になる、という条件と同値です。

 この状況を一般化した上で、写像の言葉を使って書き直します:
室外機 M_1の周期を N_1、室外機 M_2の周期を N_2とし、 S_1, S_2  \mathbb{Z}/N_1\mathbb{Z},\mathbb{Z}/N_2\mathbb{Z}の部分集合とする。 また、 N_1,N_2の最小公倍数を Lとする。

 写像\phi:\mathbb{Z}/L\mathbb{Z} \to \mathbb{Z}/N_1\mathbb{Z} \times \mathbb{Z}/N_2\mathbb{Z}を、

\begin{align}
 \phi(x)=(x \hspace{2mm} \text{mod }N_1,x \hspace{2mm} \text{mod }N_2)
\end{align}

と定めると、これはアーベル群の準同型写像であり、

\begin{align}
 x \in S \Leftrightarrow \phi(x) \in S_1 \times S_2
\end{align}

となる。

次にこの条件を、問題が解きやすくなるように書き換えていきます:
まず、

\begin{align}
\phi(x) \in S_1 \times S_2 \Leftrightarrow x \in \phi^{-1}(S_1 \times S_2)
\end{align}

なので、

\begin{align}
S=\phi^{-1}(S_1 \times S_2)
\end{align}

です。

今必要なのは |S|なので、 |\phi^{-1}(S_1 \times S_2)|が分かれば良いのですが、ここで \phi単射であることがすぐに分かる(xが10でも14でも割り切れるなら、70でも割り切れる)ので、 

\begin{align}
|\phi^{-1}(S_1 \times S_2)|&=|\phi(\phi^{-1}(S_1 \times S_2))|\\
&=|\text{Im}\phi \cap S_1 \times S_2 |
\end{align}

となります。

従って、色々と書いてきましたが、この問題を解くには、( S_1,S_2は最初に与えられているデータなので)結局  \text{Im}\phiが何なのかがわかれば良いことになります。

 そして、これについて、とても都合の良い初等整数論の次の命題が成り立ちます:
命題1.  DN_1,N_2の最大公約数とし、写像\psi:\mathbb{Z}/N_1\mathbb{Z} \times \mathbb{Z}/N_2\mathbb{Z} \to \mathbb{Z}/D\mathbb{Z} を 

\begin{align}
 \psi(x_1,x_2)=x_1 \hspace{2mm}\text{mod }D - x_2\hspace{2mm}\text{mod }D   
\end{align}
と定める。この時、以下は完全:

\begin{align}
0{ \longrightarrow } \mathbb{Z}/L\mathbb{Z} \stackrel { \phi } { \longrightarrow } \mathbb{Z}/N_1\mathbb{Z} \times \mathbb{Z}/N_2\mathbb{Z} \stackrel { \psi } { \longrightarrow } \mathbb{Z}/D\mathbb{Z} \rightarrow 0.
\end{align}

(証明の概略)
\phi単射であることは上で触れたのと同様に分かる。\psi全射であること、\text{Im}\phi \subset \text{Ker}\psiは明らか。また、N_1N_2=LDより|\text{Ker}\psi|=L=|\text{Im}\phi| となり、両者は一致する。(証明の概略終了)

Remark. 証明中にN_1N_2=LD(2つの正の整数の積はその最小公倍数と最大公約数の積に等しい)というよく知られた事実を用いましたが、この命題はこの事実のアーベル群バージョンと見ることができると思います。また、N_1,N_2が互いに素なら中国剰余定理の特別な場合になっていて、中国剰余定理の仲間に位置付けられる命題でもあります。

さて、この命題を用いて「室外機問題」を解きます。命題1より、求めたかった\text{Im}\phi\text{Ker}\psiに等しく、\psiの定義よりそれは

\begin{align}
x_1 \equiv x_2 \hspace{2mm}\text{mod }D   
\end{align}

を満たす(x_1,x_2)  \in  \mathbb{Z}/N_1\mathbb{Z} \times \mathbb{Z}/N_2\mathbb{Z} 全体となります。つまり、

\begin{align}
|S|=|\{(x_1,x_2 ) \in S_1 \times S_2 \hspace{1mm}|\hspace{1mm} x_1 \equiv x_2 \hspace{2mm}\text{mod }D \}|   
\end{align}

により|S|が求められます。

これを最初の問題設定で具体的に求めてみると、N_1=10,N_2=14よりD=2であり、\{5,6,7,8,9\} \times \{7,8,9,10,11,12,13\}の元のうち、各成分の偶奇が一致しているもの、つまり

\begin{align}
 \{6,8\} \times \{8,10,12\} \cup  \{5,7,9\} \times \{7,9,11,13\}
\end{align}

の元の個数が求める|S|となります。よって、|S|= 2 \times 3+3 \times 4=18です。以上より室外機の音が無い時間の割合は18/70≒25.7%となり、問題はめでたく解決されました。

 

…と、ここまでたどり着いた瞬間はとても嬉しかったのですが、今この記事を書いていて、なんだかすごく当たり前のことをしただけのように思えてきました。自分の考えたことなんて何も無かったのではないか、、というような。数学を勉強していると良くあることです。

しかし、勢いに任せて当初書こうと思っていたことを一通り書こうと思います。 

 

「室外機問題」の一般化およびその解法

問題をさらに次のように一般化します。室外機がk台あり、その周期や音がでるタイミングもバラバラだとしましょう。この時に全ての室外機が音を出していない静かな時間|S|はどのように求められるでしょうか?

f:id:triprod1829:20181220120134p:plain

(k台の室外機からの騒音に悩まされるB氏のイメージ)

 

k台の室外機のそれぞれの周期をN_1,N_2\cdots,N_k(ただし、N_iたちは全て正の整数)とし、それぞれの室外機についての音の無い時間がS_i \subset \mathbb{Z}/N_i \mathbb{Z}で指定されているとします。また、k台の室外機全体の周期L:=LCM(N_1,\cdots,N_k)の中で、音が無い時間全体をSと置きます。上記と同様に、写像\phi:\mathbb{Z}/L\mathbb{Z} \to \prod_{i=1}^{k}\mathbb{Z}/N_iを、

\begin{align}
 \phi(x)=(x \hspace{2mm} \text{mod }N_1,\cdots,x \hspace{2mm} \text{mod }N_k)
\end{align}

とすると、S\phi^{-1}(S_1  \times \cdots  \times S_k)に一致します。また、\phi単射もすぐに分かるので、

\begin{align}
|\phi^{-1}(S_1 \times S_2 \times \cdots S_k)|&=|\phi(\phi^{-1}(S_1 \times S_2 \times \cdots S_k))|\\
&=|\text{Im}\phi \cap S_1 \times S_2 \times \cdots S_k |
\end{align}

となります。 従ってこの場合にも\text{Im}(\phi)が分かれば良いことになります。さらに、これについても、上記の命題1を一般化した次の命題が成り立ちます:

命題2.  D_{ij}N_iN_jの最大公約数とし、写像 \psi:\mathbb{Z}/N_1\mathbb{Z} \times \cdots \times \mathbb{Z}/N_2\mathbb{Z} \to \prod_{i , j} \mathbb{Z}/D_{ij} \mathbb{Z} を 

\begin{align}
 \psi(x_1,\cdots,x_k)=(\cdots,x_i \hspace{2mm}\text{mod }D_{ij} - x_j\hspace{2mm}\text{mod }D_{ij},\cdots)   
\end{align}
と定める。この時、以下は完全:

\begin{align}
0{ \longrightarrow } \mathbb{Z}/L\mathbb{Z} \stackrel { \phi } { \longrightarrow } \mathbb{Z}/N_1\mathbb{Z} \times \cdots \times \mathbb{Z}/N_k\mathbb{Z} \stackrel { \psi } { \longrightarrow } \prod_{i , j} \mathbb{Z}/D_{ij} \mathbb{Z} .
\end{align}

(証明は省略。気になる方は高木貞治, 初等整数論講義 第2版, 共立出版, 第1章§6. [問題 2] などを参照されると良いと思います。)

この命題より、「一般化された室外機問題」も解決されました。つまり、与えられたS_1 \times \cdots \times S_k \subset  \mathbb{Z}/N_1\mathbb{Z} \times \cdots \times \mathbb{Z}/N_k\mathbb{Z}の元(x_1,\cdots,x_k) のうち、全てのi,jで

\begin{align}
x_i \equiv x_j \hspace{2mm}\text{mod }D_{ij}   
\end{align}

を満たすものの個数が求める|S|の値となります:
\begin{align}
|S|=|\{(x_1,\cdots,x_k ) \in S_1 \times \cdots\times S_k \hspace{1mm}|\hspace{1mm} x_i \equiv x_j \hspace{2mm}\text{mod }D_{i,j} \hspace{2mm}(i,j=1,\cdots,k) \}|.   
\end{align}

kが増えれば手順は室外機が2個の時よりも複雑にはなりますが、この方法で求めることができます。

 

最後に

これでこの一般化に対する「室外機問題」はできたと思うのですが、「室外機問題」自体はまだまだ考える余地がある面白い問題だと思います。
例えば、今回は周期が正の整数で、室外機が動き出すタイミングも揃っている前提で考えましたが、そうではなく、周期が無理数のものが混じっていたり、動き出すタイミングが揃っていない場合に、音の出ない時間の割合や集合がどのようなものになるか、という問題は興味深いと思います。

 また、これはもはや「室外機問題」と関係ないかもしれないのですが、個人的に一番気になっているのは、命題1や命題2で出てきた完全系列は、層( 層 (数学) - Wikipedia )の定義を完全系列を用いて書いたものによく似ているということです。
これらの命題は本質的には高木貞治, 初等整数論講義の第1章§6. [問題 1][問題 2]の内容なのですが、今回問題を考えている際にそれを上記のような完全系列に書いてみたところ、層の定義ととても似ていることに気づきました。
実際、命題1の完全系列の場合は3点集合に適当な位相を入れた時の層の条件とみなすことができるのですが、これは一般的に言えることなのでしょうか?
本当はこれについて理解して書くことも記事のモチベーションだったのですが、一般の場合はすぐには分からなかったので一旦記事をアップします。もしご存知の方がいましたら教えていただけると幸いです。

それではお読みいただきありがとうございます。