魔方吧·中文魔方俱乐部

标题: 第n层有多少个n？(Solved) [打印本页]

作者: superacid 时间: 2009-6-25 08:52:04 标题: 第n层有多少个n？(Solved)

如图，先写两个1，然后在每一层的两个数之间插入这两个数的和得下一层

1                                           1          第一层
1                   2                   1          第二层
1       3       2       3       1          第三层
1 4 3 5 2 5 3 4 1          第四层
1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1          第五层
..................................................          ..........
..................................................          ..........

问第n层有多少个n?  (n>1)

要看较完全的解答到35楼。

[ 本帖最后由 superacid 于 2009-6-28 18:31 编辑 ]

作者: 今夜微凉 时间: 2009-6-25 08:54:59

手机看不明白怎么排列的，先占楼~电脑上再解~
哦，看懂了~先草稿纸计算一下~
好吧好吧好吧~从早想到晚~我放弃~

[ 本帖最后由今夜微凉于 2009-6-25 20:30 编辑 ]

作者: 专业新手 时间: 2009-6-25 08:57:47

看不懂/。。。。。。。。。。。。。

作者: superacid 时间: 2009-6-25 09:10:49

楼上的......

[ 本帖最后由 superacid 于 2009-6-25 11:49 编辑 ]

作者: 今夜微凉 时间: 2009-6-25 09:30:01

楼主~不要急着公布部分答案嘛~让大家多想想更有意思~呵呵

作者: superacid 时间: 2009-6-25 09:47:10

这不应该算公布答案吧，也就是说了玩玩。
实际上2009和n是一样的。

作者: 四川绵阳 时间: 2009-6-25 11:03:54

~不要急着公布部分答案嘛~让大家多想想更有意思~呵呵

作者: superacid 时间: 2009-6-25 11:49:01

那好吧，应大家要求，把答案删掉

作者: 铯_猪哥恐鸣 时间: 2009-6-25 11:55:17

。。。全国数学竞赛银牌同学。。。你就不要再出这类题目杀死无辜的魔友们的脑细胞了啊。。。（本来看到题目还蛮兴奋。。一看出题的人就直接放弃了。。。）

作者: superacid 时间: 2009-6-25 12:30:55

没办法，先要骗一点积分，等级到蓝魔再出一些简单的。

作者: superacid 时间: 2009-6-25 12:32:00

建议大家先学一些初等数论再做这道题。

作者: lulijie 时间: 2009-6-25 12:50:12

我也抛砖引玉，说说我的思路。
用f(n,m)表示第n行第m个数。
那么得到以下递推公式
      f(1,1)=1，f(1,2)=1
      f(n+1,2k-1) =f(n,k)
      f(n+1,2k) =f(n,k)+f(n,k+1)

作者: lulijie 时间: 2009-6-25 13:08:38

f(n,1)=f(n-1,1)=......=f(1,1)=1
f(n,2)=f(n-1,1)+f(n-1,2)=1+f(n-1,2)=......=n-1+f(1,2)=n
f(n,3)=f(n-1,2)=n-1
f(n,4)=f(n-1,2)+f(n-1,3)=n-1+n-2=2n-3
f(n,5)=f(n-1,3)=n-2
f(n,6)=f(n-1,3)+f(n-1,4)=n-2+2n-5=3n-7
f(n,7)=f(n-1,4)=2n-5
f(n,8)=f(n-1,4)+f(n-1,5)=3n-8
f(n,9)=f(n-1,5)=n-3
。
。
。

作者: superacid 时间: 2009-6-25 13:21:31

楼上的做法......

作者: noski 时间: 2009-6-25 16:29:28

长得真像泰姬陵，哈哈

--------------
仿佛看到无数条抛物线从一头扔到另一头，慢慢算一算。。

[ 本帖最后由 noski 于 2009-6-25 16:40 编辑 ]

作者: nick159951 时间: 2009-6-25 16:41:12

原帖由 铯_猪哥恐鸣 于 2009-6-25 11:55 发表
。。。全国数学竞赛银牌同学。。。你就不要再出这类题目杀死无辜的魔友们的脑细胞了啊。。。（本来看到题目还蛮兴奋。。一看出题的人就直接放弃了。。。）

````·····幸好我一开始也没打算想·····

作者: superacid 时间: 2009-6-25 17:41:37

如果把题目改为问第2009行有多少个2009是不是可以用计算机编程算出来的吧......
铯_猪哥恐鸣作为一个高三全国联赛上海赛区计算机和物理名次都是N的人，数学不应该差到这道题都没有想法。
可以编程找规律的。

作者: Osullivan 时间: 2009-6-25 19:49:34

原帖由 lulijie 于 2009-6-25 12:50 发表
我也抛砖引玉，说说我的思路。
用f(n,m)表示第n行第m个数。
那么得到以下递推公式
      f(1,1)=1，f(1,2)=1
      f(n+1,2k-1) =f(n,k)
      f(n+1,2k) =f(n,k)+f(n,k+1)

12#用递推，不错~~~
我也有此想法~~~~
归纳猜想不知道行不行~~~~~
我还有个想法是从第n行开始，倒着看，晚上算算看行不？~~~~~

作者: kexin_xiao 时间: 2009-6-25 21:36:13 标题: 回复 15# 的帖子

你的帖子让我联想到《越狱》

作者: lulijie 时间: 2009-6-26 01:09:15

2009行共有2^2008+1个数，是个天文数字。
--------------------------------------------------------------------------------------
引入一个定义：
a，b
一次填充变为  a，a+b，b
两次填充：上述一次填充后的数列，每相邻的数之间填入1个数，值等于相邻两数的和。
      即变为：a，2a+b,a+b，a+2b，b
三次填充：  上述两次填充后的数列，每相邻的数之间填入1个数，值等于相邻两数的和。
。。。。。。
n+1次填充：上述n次填充后的数列，每相邻的数之间填入1个数，值等于相邻两数的和。
-----------------------------------------------------------------------------------------------
这2^2008+1个数，可以这样填充。
第一步填充：
1，2009，2008，2007，2006，......，4，3，2，1
第二步填充：
2009，2008之间不填充
2008，2007之间填充1次，即填入4015
2007，2006之间填充2次，即填入（2007），6020，4013，6019，（2006）三个数
......
   i ,    i -1       之间填充 2009-i 次
......
3，2之间填充2006次
2，1之间填充2007次。  （其实上述填充后的数列是以2为左右对称。可以不用填充，参照2左边的数列就可）
---------------------------------------------------------------------------------------------
第2009行数列中，第一个2009为第二个数
   第二个2009，为1005和1004之间填充入的数（1005，1004之间共需填充1004次，第1次填入的就是2009）
   第三个2009，为670和669之间填入的数
（670，669之间共需填充1339次，（670），2009，1339，2008，（669），第2次填入的数中有2009）
......
这是我的一个思路，还是比较复杂。

作者: Cielo 时间: 2009-6-26 01:42:40

想了一下也没什么头绪，瞎猜个吧：
n = 1 或 5 时，有 4 个 n，其余的都只有 2 个……

作者: superacid 时间: 2009-6-26 08:21:04

原帖由 Cielo 于 2009-6-26 01:42 发表
想了一下也没什么头绪，瞎猜个吧：
n = 1 或 5 时，有 4 个 n，其余的都只有 2 个……

再多些两行猜呢......n=7就不对，还有n>2

作者: superacid 时间: 2009-6-26 08:23:41

经过我的多次鼓励，铯_猪哥恐鸣已经猜出来了。

作者: Cielo 时间: 2009-6-26 09:54:36

原帖由 superacid 于 2009-6-26 08:21 发表

再多些两行猜呢......n=7就不对，还有n>2

呵呵我是写到第7行了，结果只注意了新加的数，没看见原来保留下来的数

作者: Osullivan 时间: 2009-6-26 18:31:31

如果每秒此题杀死我100个脑细胞，我上午思考了三个小时，白搭，脑细胞死了多少，LZ你帮我算算~~~~~~~~~

作者: superacid 时间: 2009-6-26 19:26:06

看来这道题有一点难，明天给出第一个提示

作者: r_517 时间: 2009-6-26 19:36:49

去掉每行最后一个1，变成Stern Brocot Tree（囧。。。这名字我搜了半天才搜出来怎么拼的。。。）。。继续思考思路去了。。

作者: 金眼睛 时间: 2009-6-28 00:17:32

数论对我来说太陌生了，我虽然不能给出证明过程，可以给出一个猜想的结果，呵呵！

再详细说一下我的思路吧，希望大家集思广益，把这道题证明出来。

1：先把第一行的两个1设成a和b，可以发现第N层是由两个数列累加而成，一个是a的系数，一个是b的系数。
2：比如第四层的一半 1 4 3 5 2，是由第三层1 3 2 3 1与0 1 1 2 1相加而成。
3：这个0 1 1 2 1是前两层的结合 0 （1 1）2 1 第一层出现了，0 1 （1 2 1）第二层出现了，也就是公用的1出现1次。
第N层可以由前N-1层由此递推关系构造出来！！

也许有朋友会问，这有什么用啊？呵呵，对于计算机编程来说，这个发现好处是显而易见的，后面附上解此题的Matlab程序，5秒可以算到25，然后由于数列太长，1.6*10^16这么长，out of memory了，不过前面这些结果足够发现一些规律了。

结论：
1：对于质数m来说，第m层含有m的个数为：N=m-1。
下面列出到25的结果，前面是层数m，后面是含有m的个数。
2-1，3-2，4-2，5-4，6-2，7-6，8-4，9-6，10-4，11-10，12-4，13-12，14-6，15-8，16-8，17-16，18-6，19-18，20-8，21-12，22-10，23-22，24-8，25-20……
2：既然对于质数规律这么明显，一定想到对各个合数进行质因数分解，通过观察找到如下规律：
对于某个合数的一个分解，例：m= 2^a * 3^b * 5^c ……
则m层含有m的个数为：N=(2-1)*2^(a-1)*(3-1)*3^(b-1)*(5-1)*5^(c-1) ……

对于2009，由于2009=7^2*41 故 N=(7-1)*7^(2-1)*(41-1)*41^(1-1)=1680。

以上结论仅为猜想，希望能对大家有所启发，下面给出计算程序，会Matlab的人可以借鉴。
_________________________________________________________________________________

clear;
a=[0,1,1];b=[1,2];
for i=1:24
c=b;c(end)=[];c=[c,fliplr(b)];b=a+c;c(1)=[];a=[a,c];
2*length(find(b==(i+1)))
end
_________________________________________________________________________________

[ 本帖最后由金眼睛于 2009-6-28 00:20 编辑 ]

作者: Cielo 时间: 2009-6-28 01:07:23

哇！金眼睛的结果是欧拉函数，估计就是对的了！

作者: edmond-xym 时间: 2009-6-28 07:22:27

这个题目没问题么？
开始是两个1，那从第三行起为什么中间都有2？
另外，开始只有两个1，下面都是上面的两个数字之和，这不就是杨辉三角么？求第n层，用二项式就好了，但别忘了你的要求比二项式少一层，就是+1和-1的问题了。

作者: lulijie 时间: 2009-6-28 12:34:17

假设第一行为a，b
那么第N行，首尾之间的所有数都可表示为i*a+j*b， i、j为正整数
且当i<=N，j<=N时，所有满足i和j互质的 i*a+j*b 值都存在，所有i和j不互质的 i*a+j*b 值都不存在。
----------------------------------------
当a=b=1，N=2009时，就是楼主的例子：
也就是求满足 i+j=2009，i、j为小于2009的正整数且 i和j互质的所有组合数。
i=1，j=2008
i=2，j=2007
i=3，j=2006
......
i=2007，j=2
i=2008，j=1
因为2009=7*7*41
当i为7的倍数时，j也为7的倍数，i与j不互质，所以i不能等于7的倍数，
当i为41的倍数时，j也为41的倍数，i与j不互质，所以i不能等于41的倍数，
所以所求的总可能数为2008-（2009/7-1）-(2009/41-1)+(2009/(7*41)-1)=2008-286-48+6=1680

作者: lulijie 时间: 2009-6-28 12:53:15

对于N，假设N的第i个因数为ai，指数为ki
那么，总的个数=N-1- ∑(N/ai-1) + ∑(N/(ai*aj)-1) - ∑(N/(ai*aj*av)-1)+......
若N为素数，那么总的个数=N-1+（1-1）=N-1
N=3，那么总的个数=2-（1-1）=2
N=4，那么总的个数=3-（4/2-1）=2
N=5，那么总的个数=4-（1-1）=4
N=6，那么总的个数=5-（6/2-1)-(6/3-1)+(6/6-1)=5-2-1+0=2
N=8，那么总的个数=7-（8/2-1)=7-3=4
N=30,那么总的个数=29-（30/2-1)-（30/3-1)-（30/5-1)+(30/6-1)+(30/10-1)+(30/15-1)-(1-1)=29-14-9-5+4+2+1=8
化简 N-1- ∑(N/ai-1) + ∑(N/(ai*aj)-1) - ∑(N/(ai*aj*av)-1)+......
应该得到金眼睛的计算公式。

[ 本帖最后由 lulijie 于 2009-6-28 13:10 编辑 ]

作者: ggglgq 时间: 2009-6-28 17:19:03

　　
　　

好主题！


   a                                                                                                                                                    b
   a                                                                      a+b                                                                      b
   a                            2a+b                               a+b                               a+2b                            b
   a       3a+b          2a+b          3a+2b          a+b          2a+3b          a+2b          a+3b       b
   a 4a+b 3a+b 5a+2b 2a+b 5a+3b 3a+2b 4a+3b a+b 3a+4b 2a+3b 3a+5b a+2b 2a+5b a+3b a+4b b
                                                   ..................................................
                                                   ..................................................
　　
  　　

可以证明，上面的 pa+qb 中 p、q 为互素的自然数，且 同一行中不存在

相同的 pa+qb ！且所有 p、q 为互素的自然数的 pa+qb 全部都在其中！


金眼睛、lulijie 理解得很透彻，加分支持！同时给楼主的主题加精！请大家

继续探讨研究！


　　
　　

[ 本帖最后由 ggglgq 于 2009-6-28 21:28 编辑 ]

作者: 金眼睛 时间: 2009-6-28 18:26:48 标题: 回复 33# 的帖子

谢谢G老师了！呵呵。LZ的题好，Cielo提到欧拉函数，就可以想到互质，lulijie给出证明，精华！o(∩_∩)o...

作者: superacid 时间: 2009-6-28 18:30:05

我一天没来就有人做出来了，看来大家水平很高啊！
贴一下解答。

附件: 第n层有几个n.rar (2009-6-28 18:30:05, 6.02 KB) / 下载次数 24
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTcwMjl8ZmQ2ZTgyOTd8MTc0MDc4NjY3OHwwfDA%3D

作者: lulijie 时间: 2009-6-28 23:34:14

没学过高等数学，不知道欧拉函数是什么，确实孤陋寡闻。
百度了一下，明白了本题的答案就是求N的欧拉函数。
i+j=2009
i与j互质，就是i与2009互质，也就是求<=2009的与2009互质的所有正整数的个数，即求2009的欧拉函数。答案就是金眼睛的结果。
学习了。

作者: edmond-xym 时间: 2009-6-28 23:35:30

是我没有审清题目么？
麻烦问一下根据“如图，先写两个1，然后在每一层的两个数之间插入这两个数的和得下一层”，第三层中间的2是哪里来的？

作者: ursace 时间: 2009-6-28 23:38:34

这个不是杨辉三角？

作者: ggglgq 时间: 2009-6-29 02:18:19

原帖由 edmond-xym 于 2009-6-28 23:35 发表
是我没有审清题目么？
麻烦问一下根据“如图，先写两个1，然后在每一层的两个数之间插入这两个数的和得下一层”，第三层中间的2是哪里来的？

原帖由 ursace 于 2009-6-28 23:38 发表
这个不是杨辉三角？

　　
　　

这个可不是什么“杨辉三角”

  呀！请两位参考：


   a                                                                                                                                                    b
   a                                                                      a+b                                                                      b
   a                            2a+b                               a+b                               a+2b                            b
   a       3a+b          2a+b          3a+2b          a+b          2a+3b          a+2b          a+3b       b
   a 4a+b 3a+b 5a+2b 2a+b 5a+3b 3a+2b 4a+3b a+b 3a+4b 2a+3b 3a+5b a+2b 2a+5b a+3b a+4b b
                                                   ..................................................
                                                   ..................................................
　　
  　　
　　
　　
　　

作者: Cielo 时间: 2009-6-29 04:45:51

原帖由 lulijie 于 2009-6-28 23:34 发表
没学过高等数学，不知道欧拉函数是什么，确实孤陋寡闻。
百度了一下，明白了本题的答案就是求N的欧拉函数。
……

在不知道的情况下给出证明更是难能可贵啊

大家都很厉害啊！

作者: xh176233756 时间: 2009-6-29 05:04:28

传说中的法雷序列？？？

作者: nick159951 时间: 2009-6-29 05:07:01

这道题目可真令我晕了····

作者: lulijie 时间: 2009-6-30 23:22:34

第N行的第m个数，表示成 p*a+q*b 的形式。
百度了一下法雷序列。发现：
所有的q/p或p/q都是N级法雷序列中的数。
难道仅仅是巧合么？

[ 本帖最后由 lulijie 于 2009-6-30 23:30 编辑 ]

作者: superacid 时间: 2009-7-1 07:59:01

原帖由 lulijie 于 2009-6-30 23:22 发表
第N行的第m个数，表示成 p*a+q*b 的形式。
百度了一下法雷序列。发现：
所有的q/p或p/q都是N级法雷序列中的数。
难道仅仅是巧合么？

这不是巧合，是必然

作者: cjwjy007 时间: 2009-7-1 10:54:58

很强。。。。
数学白痴飘过

作者: noski 时间: 2009-7-7 02:02:45

好题，再顶，可惜没做出来。。

作者: 357433865 时间: 2009-7-7 03:50:25

这么都这么难啊？？？大脑会崩溃的

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)