浅葱色の計算用紙

数学(広義)を扱っています。

フィボナッチ数グラフ

注意:この記事では、0は自然数に含まないものとします。

 

次の動画で、以下の問題が提起された:

www.nicovideo.jp

問題:

全ての自然数に対して、それぞれに対応する頂点がちょうど1個存在するような(無限の大きさを持つ)グラフを考える。このグラフの辺は、和がフィボナッチ数であるような2頂点の間にのみ存在する。このとき、このグラフが三角形を含まない(次数3の完全グラフ\(K_3\)を部分グラフに持たない)ことを証明せよ。

 

 

解答:

背理法で証明する。グラフが三角形を含むものと仮定し、その相異なる3頂点に対応する自然数をそれぞれ\( a,b,c \)とする。また、\(F_n\)で\(n\)番目のフィボナッチ数を表すものとする。また、\(F_1=F_2\)であるから、\(F_n\)は\(n\geq 2\)で考えればよい。このとき、\(F_n\)は単調増加となる。

まず、1つの頂点が1だと仮定すると、1と1以外の数を足してフィボナッチ数にするためには\(1+2=3\)しかないが、このとき残りの1つの頂点との和を考えると差が1のフィボナッチ数が必要であることが分かる。これは1と2,2と3しか存在しないが、どちらの場合も\(a,b,c\)が相異なることに矛盾する。したがって、頂点の1つが1となることはない。

次に、以下の補題を証明する:

補題】\( F_m+F_n=F_l \)が成り立つとき、\(m\)と\(n\)の差は1である。

【証明】\(m\geq n\)として一般性を失わない。

このとき、\(F_l>F_m\)であるから\(l>m\)である。また、\(F_m\)より大きい最小のフィボナッチ数は\(F_{m+1}=F_m+F_{m- 1}\)であるから\(F_n\geq F_{m- 1}\)となる。

さらに、\(F_l\geq F_{m+2}\)とすると\(F_{m+2}=F_m+F_{m+1}\)であるから\(F_n\geq F_{m+1}\)が得られ、これは\(m\geq n\)に反するので

\(F_l=F_{m+1}\)である。したがって、\(n=m- 1,l=m+1\)となるので、\(m-n=1\)を得る。

 

ここから、3つの場合に分けて証明を行う。

(i) \(a,b,c\)の中にフィボナッチ数が2個以上含まれる場合

対称性より、\(a,b\)がフィボナッチ数で、 \(a=F_m, b=F_n \ (m>n) \)として一般性を失わない。

このとき、3つの整数\(s,t,u\)が存在し、

\( F_m+F_n=F_s \ \cdots(1) \)

\( F_m+c=F_t \ \cdots(2) \)

\( F_n+c=F_u \ \cdots(3) \)

となる。

まず、補題と(1)と\(m>n\)から、\(m=n+1, s=n+2\)がわかる。

次に、(2)-(3)より、

\( \begin{eqnarray} F_m-F_n&=&F_t-F_u \\F_{n+1}-F_n&=&F_t-F_u \\ F_{n-1}&=&F_t-F_u \\ F_{n+1}+F_u&=&F_t \end{eqnarray}\)

 となり、(3)より\(F_u>F_n\)であるから\(u=n+2,t=n+3\)を得る。しかし、これを(2)に代入すると\(F_{n+1}+c=F_{n+2}\)より\(c=F_n\)が得られ、これは\(a,b,c\)が相異なることに矛盾する。

(ii) \(a,b,c\)の中にフィボナッチ数が1個含まれる場合

対称性より、\(a\)がフィボナッチ数で、 \(a=F_m, b>c \)として一般性を失わない。また、\(b,c\)はフィボナッチ数ではない。

このとき、3つの整数\(s,t,u\)が存在し、

\( F_m+b=F_s \ \cdots(1) \)

\( F_m+c=F_t \ \cdots(2) \)

\( b+c=F_u \ \cdots(3) \)

となる。

このとき、(2)で\(t=m+1\)とすると\(c=F_{m- 1}\)、\(t=m+2\)とすると\(c=F_{m+1}\)となるから、( これらは\(c\)がフィボナッチ数でないことに矛盾するので ) \(t\geq m+3\)となる。同様にして、( \(b>c\)より ) \(s\geq m+4\)を得る。

また、(1)~(3)より\( F_s+F_t-2F_m=F_u \)であり、\(F_t\geq F_{m+3}, 2F_m<F_m+F_{m+1}=F_{m+2} \)から \(F_s<F_u\)を得る。

また、\(b>c\)より\(s>t\)であるから、\(F_s>F_t-2F_m\)である。よって、\(F_s<F_u<2F_s\)であり、これを満たすためには\(F_u=F_{s+1}, F_t-2F_m=F_{s-1}\)でなければならない。

 このとき、

\( \begin{eqnarray} F_{s-1}&<&2F_m+F_{s-1}=F_t \\ &=& F_m+F_m+F_{s-1} \\ &<& F_m+F_{m+1}+F_{s-1} \\ &=& F_{m+2}+F_{s-1} \\&\leq&F_{s-2}+F_{s-1}  \\ &=&F_{s} \end{eqnarray} \)

より、\(F_t=2F_m+F_{s-1}\)がフィボナッチ数であることに矛盾する。

(4行目から5行目への変形では\(s\geq m+4\)を用いた)

よって(ii)の場合でも示された。 

(iii) \(a,b,c\)の中にフィボナッチ数が0個含まれる場合

対称性より、\(a>b>c \)として一般性を失わない。また、\(a,b,c\)はフィボナッチ数ではない。

このとき、3つの整数\(s,t,u\)が存在し、

\( a+b=F_s \ \cdots(1) \)

\( b+c=F_t \ \cdots(2) \)

\( a+c=F_u \ \cdots(3) \)

このとき、

\( a=\frac{1}{2}(+F_s-F_t+F_u) \)

\( b=\frac{1}{2}(+F_s+F_t-F_u) \)

\( c=\frac{1}{2}(-F_s+F_t+F_u) \)

となる。ここで、\(a>b>c\)より、\(F_s>F_u>F_t\)である。また、\(s\geq t+3\)のとき、

\( F_t+F_u \leq F_{u-3}+F_{u} <F_{u-1}+F_{u}=F_{u+1}\leq F_s \)

となり、\(c<0\)となるので不適

よって\(s=t+2,u=t+1\)であるが、このとき

\( c=\frac{1}{2}(-F_{t+2}+F_{t+1}+F_u)=0 \)

となるので不適

よって矛盾が示せた

 

以上(i)~(iii)より、与えられたグラフには三角形は存在しない。