魔方吧·中文魔方俱乐部

标题: 我来出几道题 [打印本页]

作者: superacid 时间: 2009-9-1 08:45:10 标题: 我来出几道题

1.n是偶数，在n*n的格子纸的某些的格子内有一个魔方，满足每个格子的邻格中至少有一个魔方，问至少有多少个魔方？

2.n个球放入了若干个盒子中，可进行如下操作：对于两个盒子A,B，可以从B中取出与A中个数相同个数的球放入A中。求n满足的充要条件，使得开始时无论n个球如何分配，最终均可使n个球置于一个盒子内。

3.求满足下列3个条件且项数为2005项的数列的个数：(1)数列中没有连续的三项相等；(2)每项要么为1，要么为-1；(3)2005项的和至少为666。

4.n*n的格子纸，每行每列都恰有一个魔方，作一条从左上角到右下角的沿着格子边的折线(长度为2n)，使得所有魔方都在折线下方，对于所有的魔方摆法，求折线的总数。(不同魔方摆法产生的同一折线要重复计数，所有魔方都是一样的)

zxl0714在6楼和9楼给出的答案都正确

[ 本帖最后由 superacid 于 2009-9-1 17:12 编辑 ]

作者: migl 时间: 2009-9-1 09:22:33

先提些问题：
题1：
那些魔方的阶数可以任意设置？
允许不同阶数的魔方同时存在？
只要放得下的魔方就可以放？
包括1*1、1*2、2*3的魔方吗？

=========

唉~~多虑了
原来一个魔方只占用一格，而不是按体积占用格子~~

被魔方误导了~

[ 本帖最后由 migl 于 2009-9-1 10:48 编辑 ]

作者: zhwnuaa 时间: 2009-9-1 09:36:09 标题: 回复 1# 的帖子

不知道，路过一下

作者: noski 时间: 2009-9-1 09:38:43

第三题，50349166?

----
知道问题所在了-_-

[ 本帖最后由 noski 于 2009-9-1 12:52 编辑 ]

作者: superacid 时间: 2009-9-1 10:09:34

不对

作者: zxl0714 时间: 2009-9-1 11:00:34

2.n是2的幂
3.8471248182

作者: 封魔之阳 时间: 2009-9-1 11:16:35

提示: 作者被禁止或删除内容自动屏蔽

作者: superacid 时间: 2009-9-1 12:16:00

6楼答案是正确的

作者: zxl0714 时间: 2009-9-1 16:37:01

4. ( 2n - 1 )!!

作者: lulijie 时间: 2009-9-1 21:32:18

我第四题的思路：
1、2、3.、....、n.  共n个数随机排列。所有的可能有n!种。每一种代表魔方的一种摆法。
比如n＝5，  21453 代表第一列第2行、第二列第1行、第三列第4行、第四列第5行、第五列第3行各有一个魔方。
列从左到右计数，行从下到上计数。
－－－－－－－－－－－－－－－－－－－－－－－－－－－

对于任一排列  a1a2a3......an
先确定最大的数n的位置，比如ai＝n  （表示第i列第n行有一个魔方）
那么从左上角到第i列的魔方的折线只有一种画法。
接着找ai后面最大的数，比如是aj=m1.，再找aj后面最大的数m2，。。。。。。直到mk是最后一个数an
那么折线的画法只跟n、m1、m2......、an的排列即它们之间的距离有关。可以在它们之间填入0。
比如  n＝7    4571263排列    n＝7，m1＝6，an＝3
               折线的画法只跟 70063 有关。  只有5种画法
－－－－－－－－－－－－－－－－－－－
这才仅仅是思路。不知能不能通罗马。

作者: lulijie 时间: 2009-9-3 23:12:32

第4题：n=2 只有两种魔方摆法。一种摆法折线画法1种，另一种摆法折线画法2种，所以总共3种折线画法。所以9楼的答案(2n-1)!! 应该不对。

--------------------------
看错了。!!表示连续奇数的乘积。
n=2 3种
n=3 15种
9楼的计算公式是符合的。能否说说你的原理。

[ 本帖最后由 lulijie 于 2009-9-3 23:50 编辑 ]

作者: superacid 时间: 2009-9-4 11:04:43

实话说我第4题忘了怎么做了，是来征集答案的

作者: zxl0714 时间: 2009-9-4 22:33:28

第四题我是用编程观察出来的。这个问题等效为给出一个序列{ An }，计算有多少个不降的序列{ Bn }使得Bi >= Ai，设F( i, j )为{ Bn }中第i个数为j的不同序列数，那么有
F( i, Ai ) = sum{ F( i - 1, k ), 1 <= k <= Ai }
F( i, j ) = F( i - 1, j - 1 ) + F( i, j - 1 ), j > Ai
最后F( n, n )就是所求序列个数。
然后对每一个{ An }都求一遍，即将这n个数做全排列，最后最后将所有的F( n, n )加起来就得出了答案，设S( n )为答案，有
S( 1 ) = 1
S( 2 ) = 3
S( 3 ) = 15
S( 4 ) = 105
S( 5 ) = 945
S( 6 ) = 10395
S( 7 ) = 135125
S( 8 ) = 2027025
S( 9 ) = 34459425
S( 10 ) = 654729075
观察得S( n ) = ( 2n - 1 )S( n - 1 )

作者: tm__xk 时间: 2009-9-8 00:59:41

对n,删掉首列魔方所在行列,得到n-1.

事实上,后者一个局面对应前者2n-1个.

想清楚就行了..不多说了..

作者: lulijie 时间: 2009-9-11 20:57:24

对于第一题，网上找到一个解答。
它就是第40届IMO第三题。

第40届IMO试题解答.pdf (219.49 KB, 下载次数: 57)

附件: [解答下载] 第40届IMO试题解答.pdf (2009-9-11 20:57:24, 219.49 KB) / 下载次数 57
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NjgxNTB8MzQ1N2I2MTN8MTc0MDc5OTYwMXwwfDA%3D

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