回复 10# gxqcn 的帖子
thank you :)第三个问题的一些补充
看来第三个问题还是要再说明一下：1、规定：凡是没有说明的任意点，都不会和其他两点共线；凡是没有说明的任意直线，都不会和其他两线共点；凡是没有说某点在某线上，就是表示某点一定不在某线上。
2、我胡乱起一个名字吧，呵呵。将同学们一定得5分的图（参见4层），叫做限定图；反之，将同学们可能得4分的图，叫非限定图。因此图1是非限定图，图2和3是限定图。
3、关于所谓的关系M（参见1层，也就是同学们电话里的内容），的确用矩阵表示比较好。比如说图1可以表示为1乘4矩阵{{1,1,1,1}}；图2可以表示为3乘3矩阵{{0,1,1},{1,0,1},{1,1,0}}。如此，比方说{{0,0},{0,0}}表示任意两点和两直线，矩阵中的0表示点一定不在线上。这种表示方法无法表示只有点或只有线的情况，我们就去掉这些情况吧。
这样问题就变成了给定矩阵M，求它是不是对应于限定图（我们定义为S(M)吧，同时可以设定如是限定图时为1，不是的时候为0，根本画不出来为-1）？
有了输入输出，就可以求算法了。呵呵。 利用gxqcn给出的链接中的内容https://math.la.asu.edu/~checkman/SquareFibonacci.html，我们可以证明，对于任意满足递推式$a_{n+1}=a_n+a_{n-1}$的整数序列${a_n}$,最多都只含4个平方数。 同样采用链接中记号，记$F_n$为菲波那挈数列中第n项,其中$F_0=0,F_1=F_2=1$，记$L_n$为第n个Lucas数.
根据链接，我们知道
i) 如果k是2的倍数而且3不整除k,那么必然有$L_k -= 3 (mod 4)$.
ii) $F_{m+2k} -= - F_m (mod L_k)$
对于数列${a_n}$，我们有
$a_n = F_2xxa_{n-1} + F_1xxa_{n-2} = F_2xxa_{n-2} + F_2xxa_{n-3} + F_1xxa_{n-2} = F_3xxa_{n-2}+F_2xxa_{n-3}$
$... = F_{n-h}xxa_{h+1} + F_{n-h-1}xxa_h = ... = F_{n-1}xxa_2 + F_{n-2}xxa_1$
所以对于$n=h+2xx3^rxxk$,其中k是偶数,$r>=0$,而且k不是3的倍数(那么$n=h(mod 4)$ ),我们有
$a_n = F_{n-1}xxa_2 + F_{n-2}xxa_1$
$-=-F_{h-1}xxa_2-F_{h-2}xxa_1(mod L_k)$
$-=-a_h (mod L_k)$
对于k是偶数而且k不是3的倍数的情况，根据i)我们知道-1不是$L_k$的二次剩余,
所以如果$a_h$是完全平方数，那么对于任意的n满足$n=h(mod 4)$,我们可以知道存在不是3的倍数的偶数k使得
$a_n -= - a_h (mod L_k)$ 不是$L_k$的二次剩余，从而$a_n$不是完全平方数。
也就是说对于4的每个剩余系构成的子数列${a_{4k+h}}$最多只含有一个完全平方数。
于是我们证明了数列中最多只有4个完全平方数。
至此，我们证明了zgg__第一个问题中矩阵每行最多只有4个平方数。（至于是否至多只有3个平方数就不知道了） 想到一个问题，证明中还有一个问题，那就是$L_k | a_h$的情况没有考虑，在这个情况下，我们得到$a_n -= 0 (mod L_k)$,
还没有想好怎么去解决这个问题.看来证明还是没那么容易。 :)
mathe，还能找到 广义卢卡斯－雷麦序列 这本书么？ 原帖由 无心人 于 2008-7-15 15:05 发表 http://bbs.emath.ac.cn/images/common/back.gif
:)
mathe，还能找到 广义卢卡斯－雷麦序列 这本书么？
好像我没有见过 这本书就是专门讲 广义卢卡斯－雷麦序列 的
书比较厚，讲得很多
可惜就在快毕业那半年在学校图书馆见到过
后悔没多读几天
现在网上有复印本，要80，贵阿 原帖由 mathe 于 2008-7-15 13:22 发表 http://bbs.emath.ac.cn/images/common/back.gif
利用gxqcn给出的链接中的内容https://math.la.asu.edu/~checkman/SquareFibonacci.html，我们可以证明，对于任意满足递推式$a_{n+1}=a_n+a_{n-1}$的整数序列${a_n}$,最多都只含4个平方数。
该结论在初始条件为 $a_0 = a_1 = 0$ 不成立，希望有助于 mathe 修补上面证明中的漏洞。 原帖由 gxqcn 于 2008-7-16 09:01 发表 http://bbs.emath.ac.cn/images/common/back.gif
该结论在初始条件为 $a_0 = a_1 = 0$ 不成立，希望有助于 mathe 修补上面证明中的漏洞。
是的,在#15我已经发现了证明过程中的一个bug.
也许在除掉0序列以后,4个平方数还不是下界.