Question

12、13届noip中的题目……急求解【要过程】

1．给定n 个有标号的球，标号依次为1，2，…，n。将这n 个球放入r 个相同的盒子里，不允许
有空盒，其不同放置方法的总数记为S(n,r)。例如，S(4,2)=7，这7 种不同的放置方法依次为
{(1),(234)}, {(2),(134)}, {(3),(124)}, {(4),(123)}, {(12),(34)}, {(13),(24)},
{(14),(23)}。当n=7,r=4 时，S(7,4)= _____________。
2．N 个人在操场里围成一圈，将这N 个人按顺时针方向从1 到N 编号，然后，从第一个人起，每
隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直
到操场只剩下一个人，记这个人的编号为J(N) ，例如，J(5)=3 ，J(10)=5 ，等等。则
J(400)=______________。
（提示：对 N=2m+r 进行分析，其中 0≤r<2m ）。
1．将2006个人分成若干不相交的子集，每个子集至少有3个人，并且：
（1）在每个子集中，没有人认识该子集的所有人。
（2）同一子集的任何3个人中，至少有2个人互不认识。
（3）对同一子集中任何2个不相识的人，在该子集中恰好只有1个人认识这两个人。
则满足上述条件的子集最多能有___________个？

Answer 1

1.350

n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数
设有n个不同的球，分别用b1,b2,……bn表示。从中取出一个球bn，bn的放法有以下两种：
1)bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为 S(n-1,m-1)
2)bn与别的球共占一个盒子；那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为 m*S(n-1,m)
S(n,m)=m*S(n-1,m)+S(n-1,m-1) (n>1,m>1)
边界条件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)

2.289人
把N写成2的K次方加X的形式
则J[N]=2X+1
400=2的8次方加144
所以是第2*144+1=289个人

3.取其中一个满足要求的子集A来分析：
A＝｛a1,a2,a3...an (n>=3)｝
a1,a2,a3中至少有2个人互不认识 ,假设a1和a2不认识！
则：A中必只有一个人am认识a1和a2!
而A中除了am所有的人都不认识a1和a2!
再看看，认识am的人都有谁，显然a1和a2认识！
若还存在一个am1认识am，则：am1不认识a1,不认识a2
所以：A中必定有且只有一个am2认识am1和a1!
而上面我们说到A中除了am所有的人都不认识a1和a2!
所以我们假设的am1不成立！
换言之，认识am的人就只有a1和a2!
假设集合中的另一个元素am3,显然他不认识am,
那么显然根据（3），集合中必有一个人认识am,和am3
而我们说了认识am的人就只有a1和a2!
所以我们假设的am3不成立！

所以A中只能有3个元素！｛a1,a2,am｝
但是这样的话am就认识了集合中的所有人，不符合（1）
所以这样的子集是不存在的！

Answer 2

第一题是第二类斯特林数

第三题每个子集最少5人，所以子集至多有401个

Answer 3

1.解法一：递推公式S(x,y)=S(x-1,y)*y+S(x-1,y-1)。因为把X个球放入Y个箱子，相当于先把X-1个球放好再放最后一个。最后一个有两种放法：放入前面已经有球的箱子或者独占一个箱子。前者对应S(x-1,y)*y (放入每一个不同的箱子都是一种不同的放法，因为箱子内原来的球不同)，后者对应S(x-1,y-1)。
解法二：将这n 个球放入r 个相同的盒子里，不允许有空盒，因为是"相同的盒子",所以是一个组合问题.既将n个球分成r份.这样当n=7，r=4时，将7个球分成4份,有三种分法:(1)分为4,1,1,1(2)分为3,2,1,1(3)分为2,2,2,1
第一种分法有C(7,4)=35种
第二种分法有C(7*3)*C(4,2)=210种
第三种分法有C(7,2)*C(5,2)*C(3,2)/A（3,3）=105种
S（7，4）= C(7,4)+C(7,3)*C(4,2)+C(7,2)*C(5,2)*C(3,2)/A（3,3）=350
C(n,m)表示从n个不同元素中取出m个元素的组合数
A(n,m)表示从n个不同元素中取出m个元素的排列数
2.解：若N是满足2^m<=N<2^(m+1)的正整数，N=2^m+r,其中0<=r<2^m;(1)当N=2^m时，明显地，每一轮让人离去时，由于这轮总人数都是2的倍数，编号为1的将总保留在操场上直到最后一轮场上只剩下1号一人为止，即J(N)=J(2^m)=1;(2)当N=2^m+r,r>0时，我们通过比较得出J(N)-J(N-1)=2.这是因为：当r-1为奇数时，操场上N-1个人，在第一轮中，编号为1，3，5，……，2^m+r-1的共2^(m-1)+r/2个人将不会离去，下一轮中，首先离去的将是1号，剩下的将会是编号为3，7，11，……等等；而当总的人数增加1人成为N=2^m+r人时，因N为偶数，那么在第一轮后同样留下编号为1，3，5，……，2^m+r-1的2^(m-1)+r/2个人，只不过下一轮中，1号将仍保留在操场上，使操场上人员编号成为：1，5，9，……等等。因此，对于总人数为N-1的情况（记为情形I）下第一轮后编号1，3，5，……，2^m+r-1首先去掉1与 对于总人数为N的情况（记为情形II）下第一轮后编号3，5，……，2^m+r-1，1首先去掉3相比，若情形I下最后所留编号为k，那么对应地，情形II下最后所留编号将一定是k+2(注：k不会为1）。即J(N)-J(N-1)=k+2-k=2.另外，当r-1是偶数时，操场上N-1个人，在第一轮中，编号为1，3，5，……，2^m+r-2的共2^(m-1)+(r-1)/2个人将不会离去，下一轮中，首先离去的将是3号，剩下的将会是编号为1,5,9,……(情形III）等等；而当总人数增加人成为N=2^m+r人时，N为奇数，第一轮后场上留下编号为1，3，5，……，2^m+r不会离去，下轮中首先离去的是1号，剩下3，7，11，……（情形IV）等等。情形IV中人数与情形III中人员编号都大2，同样若干轮后，若III中最后留下号码是k，那么IV中留下的编号将也是k+2,即，J（N）-J（N-1）=2.由以上分析，知，J(2^m),J(2^m+1),……，J(2^(m+1)-1)成等差数列，首项为1，公差为2，故J(N)=J(2^m+r)=1+2r.利用上述结果，因400在256=2^8与512=2^9之间，400=2^8+144因此，J(400)=2*144+1=289.