フィボナッチ数グラフ
注意：この記事では、0は自然数に含まないものとします。
次の動画で、以下の問題が提起された：
問題：
全ての自然数に対して、それぞれに対応する頂点がちょうど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\geq n+1\)を得る。しかし、これは補題と矛盾する。
(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)より、与えられたグラフには三角形は存在しない。
