我来出几道题

superacid

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 编辑 ]

lulijie

对于第一题，网上找到一个解答。
它就是第40届IMO第三题。
第40届IMO试题解答.pdf (219.49 KB, 下载次数: 57)

2009-9-11 20:57:24 上传

下载次数: 57
解答下载

tm__xk

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

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


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

zxl0714

第四题我是用编程观察出来的。这个问题等效为给出一个序列{ 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 )

superacid

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

lulijie

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

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

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

lulijie

我第四题的思路：
    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种画法
－－－－－－－－－－－－－－－－－－－
这才仅仅是思路。不知能不能通罗马。

zxl0714

4. ( 2n - 1 )!!

superacid

6楼答案是正确的