免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[数列] 染色&递推数列

本帖最后由 hbghlyj 于 2019-11-2 22:43 编辑

将一个$2\times n$个方格组成的带形的某些方格染色,使得其中任何$2\times2$的四个方格都没有全染,以$P_n$来记所有满足要求的染色方案数,求证$P_{1989}$为3的倍数并$P_{1989}$所含3的次幂
无标题.png
2019-11-2 22:35

(如果有坛友配一下解答图就好了,我不懂技术,这是用系统自带的画图工具作的,略显简陋)
思路
记$a_n$为最后一列全染的方案数,$b_n$为最后一列不全染的方案数,$a_n$所计每个方案的最后一列有1种可能,倒数第二列不能全染,故$a_n=b_{n-1}$.$b_n$所计每个方案的最后一列有$2\times2-1=3$种可能,由于最后一列和倒数第二列的四个方格不会全染,前n-1列的染色方案等于$P_{n-1}$,故$a_n=b_n=3P_{n-1}$,代入$P_n=a_n+b_n$得$P_n=3(P_{n-1}+P_{n-2})$
现在转化为一个递推数列问题
$P_n=3(P_{n-1}+P_{n-2}),P_2=15,P_3=9+48=57$,求证$P_{1989}$为3的倍数并$P_{1989}$所含3的次幂
  1. IntegerExponent[LinearRecurrence[{3, 3}, {15, 57}, 100], 3]
  2. {1, 1, 3, 2, 3, 3, 4, 4, 6, 5, 6, 6, 7, 7, 10, 8, 9, 9, 10, 10, 12, \
  3. 11, 12, 12, 13, 13, 15, 14, 15, 15, 16, 16, 19, 17, 18, 18, 19, 19, \
  4. 21, 20, 21, 21, 22, 22, 24, 23, 24, 24, 25, 25, 29, 26, 27, 27, 28, \
  5. 28, 30, 29, 30, 30, 31, 31, 33, 32, 33, 33, 34, 34, 37, 35, 36, 36, \
  6. 37, 37, 39, 38, 39, 39, 40, 40, 42, 41, 42, 42, 43, 43, 46, 44, 45, \
  7. 45, 46, 46, 48, 47, 48, 48, 49, 49, 51, 50}
复制代码
如果将奇数项,偶数项分开,就看出规律了:
  1. First[Multicolumn[IntegerExponent[LinearRecurrence[{3,3}, {15, 57}, 100], 3], {2,Automatic}]]
复制代码
输出
{{1, 3, 3, 4, 6, 6, 7, 10, 9, 10, 12, 12, 13, 15, 15, 16, 19, 18, 19, 21, 21, 22, 24, 24, 25, 29, 27, 28, 30, 30, 31, 33, 33, 34, 37, 36, 37, 39, 39, 40, 42, 42, 43, 46, 45, 46, 48, 48, 49, 51},
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50}}
奇数项$P_{2n+1}$含3的次幂为n(偶数项没发现什么规律,请高手指教
这个规律容易用归纳法证明:$P_{2n+3}=3P_{2n+2}+3P_{2n+1},P_{2n+2}=3P_{2n+1}+3P_{2n},P_{2n+1}=3P_{2n}+3P_{2n-1}$,从以上三式消去两个偶次项得$P_{2n+3}=15P_{2n+1}-9P_{2n-1}$(这是不够的,因为$15P_{2n+1},9P_{2n-1}$由归纳假设含3的次幂都为n+1),以n-1代n,$P_{2n+1}=15P_{2n-1}-9P_{2n-3}$,消去$P_{2n+1}$,$P_{2n+3}=216P_{2n-1}-135P_{2n-3}$,因为$216P_{2n-1}$含3的次幂为n-1+3=n+2,$135P_{2n-3}$含3的次幂为n-2+3=n+1,所以$P_{2n+3}$含3的次幂为n+1,由归纳原理命题对一切正整数n成立
所以本题答案为$\frac{1989-1}2=994$
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

本帖最后由 hbghlyj 于 2019-11-4 12:15 编辑

$P_{2n}$含3的次幂记为$a_n$,$a_n$ - n:
= 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0
n含3的次幂记为$b_n$,$b_n$:
0, <0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0>, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 4, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1

TOP

希望此贴不沉。。重复一遍问题:
如何证明$a_n-n$等于n+1含3的次幂?
无标题.png
2019-11-4 22:40

TOP

返回列表 回复 发帖