数学奥林匹克升级题

到处瞎逛

03-5.试求所有的自然数n，使得n^n+1为不超过19位的质数。
===============
这一道题比较简单。
n^n+1不超过19位，也就是小于10^19，直接试验便可知n≤14。n不能含有大于1的奇因数，所以只要考虑1,2,4就可以了。
8不考虑，因为8=2^3,3是奇数，会与指数上的n结合，破坏了n不能含有大于1的奇因数的规则。
验算1,2,4均符合条件,这就是费马素数。

g99

RTRT

到处瞎逛

02-10。在（1）19x91；（2）19x92的方格中，每人每次涂黑1个或多个小方格，使之成为正方形。已被涂黑的方格不许再涂。谁涂黑了最后一个方格，就算谁赢，谁有必胜的策略？

============
(1)19*91，先手方有必须策略。先涂黑以最中心格为中心格的正方形（边长必为奇数），以后只要与对方呈中心对称地涂就可以了，只要他有地方涂黑，中心对称的地方就有。直到他没有地方涂黑为止。

(2)19*92，先手方有必须策略。先涂黑以最中心点为中心点的正方形（边长必为偶数），以后只要与对方呈中心对称地涂就可以了，只要他有地方涂黑，中心对称的地方就有。直到他没有地方涂黑为止。

shshsh_0510

122# 到处瞎逛


只要n有奇因子即可通过 (x^a+1)/(x+1)

shshsh_0510

要放假了，做个题休息一下

04－10.[ ★★★★] 设 S={1,2,…,n}, T是S的所有非空子集构成的集合。若函数f: T→S满足：对任意A,B∈T，如果A是B的真子集，则有f(A)≠f(B)，则称f为garish的。问有多少garish的函数，并证明你的结论。

如mathe所言，这题星多简单

考虑 子集序列{1,2,…,n}, {1,2,…,n-1}, ..., {1,2,3}, {1,2}, {1}, 它们显然赋值各不相同，构成至S的一一映射。

于是 f({2})=f({1}), 因为f({2})是上述序列中除{1}以外的其它成员的真子集。可以把 {2}在上述序列中与{1}并列，纵向扩展序列。

∴ f({1,3})= f({2,3})= f({1,2}), 因为{1,3},{2,3}是上述序列中除{1}, {1,2}以外的其它成员的真子集。又f({2,3})≠f({2})=f({1})≠f({1,3}), ......
   于是可以把{1,3},{2,3}与上述序列中{1,2}并列，纵向扩展序列。
∴ f({3})=f({1}), 因为f({3})是上述序列中除{1}, {1,2}以外的其它成员的真子集。又f({3})≠f({2,3})=f({1,2}), ......
   {3}得以与{1},{2}并列。

∴ {1,2,4},{1,3,4},{2,3,4}又与{1,2,3}并列, 因为它们中的任何一个都与扩展序列中的其它列中至少1个成员有真包含关系。
∴ {1,4},{2,4},{3,4}与 {1,2}并列，因为它们中的任何一个都与扩展序列中的其它列中至少1个成员有真包含关系。
∴ {4}与 {1}并列，同理。

依次递推，可得 f(A)=f(B) 当且仅当 |A|=|B|。
可见 f 的“等高线”与 T 的“等势线”同构，so, garish的函数共n!个。

mathabc

太强大了，有趣！！

到处瞎逛

那请 kenmark 再来算算 2009 。。。

或者找出所有周期为 3120 的四数字“幸运组合”。。。
gxqcn 发表于 2009-1-21 09:59

我算了一下。
总结出来的结果如下。

没有3120的四个数字。一共有三种情况：

当这4个数字是0，5的组合的时候，比如。0005，0500，5555，5050等等的时候周期是5.

当这4个数字是全是偶数的组合的时候，比如0020，0006，2228，6208的时候他的周期是312

其他的情况全是1560.

三位数的周期为124，62，31，4四种情况。
五位数的周期是4686，781，6.
最小的周期都是5和0的组合。
六位数的时候周期突然变小了，大多数是1456.呵呵
七位数的时候又大了，大多数周期是18744.
我添加附件她总是说是无效的图片文件。所以程序就没法看了。

gogdizzy

02-6。 30把椅子排成一行，随时又人走过来坐在空椅上。但是每当又一个人坐下时，便有一个坐在他邻座上的人起身离开（只要他的邻座上原来有人）。试问，最多可以有多少把椅子上同时坐着人，如果：1） 原来30把椅子全是空的； 2）原来有10把椅子坐着人。

我的理解是如果1，3坐着人，2空着，那么2来坐，3走1不动。

按照这个理解的话，就是29个了，因为最后一个空位总是无法填满的。

而前面可以按照如下规则填满：

如果前m个位置坐满，那么在m+2的位置坐一个人，接着在m+1的位置坐一个人，可以构成前m+1个位置填满。
如此往复一直到28的时候，再在30号位置坐一个人。

gogdizzy

01-1． 李庄的每一位男孩所认识的所有女孩都彼此认识，而每一个女孩所认识的男孩都比她所认识的女孩多。证明：李庄的男孩不少于女孩。  

证明： 将男孩抽象成蓝色点，女孩抽象成红色点，两人认识就连一条边，如此形成一个顶点着色的图。
条件1：每一个蓝色点所连的红色点连成局部完全图。
条件2：每一个红色点所连蓝色点比所连的红色点多。

找出连接蓝色点最多的1个红色点标记为Red1，然后找出Red1所连的所有蓝色点Blues1和所有红色点Reds1，组成人群S1，那么
不等式1：|Reds1|<|Blues1|(条件2)，
断言1：Blues1与Reds1之外的红色点无牵连(条件1)。

从余图里找出连接蓝色点最多的1个红色点标记为Red2, 然后找出Red2所连的所有蓝色点Blues2和所有红色点Reds2，组成人群S2，那么
不等式2：|Reds2|≤|Red2所连的全部红色点|<|Blues2|(条件2)，（“Red2所连的全部红色点”可能有部分属于Reds1，未被Red1带走的部分才是Reds2）.
断言21：Blues2与Reds2和Reds1之外的红色点无牵连(条件1)。
断言22：Blues2与Blues1无重叠（断言1）。

依次类推，从剩下的人里继续划分人群S3，S4，…，Sn，一直把人分完。

女孩数=(|Reds1|+1)+(|Reds2|+1)+...+(|Redsk|+1)≤(|Blues1|+|Blues2|+...+|Bluesk|=男孩数

gogdizzy

01-2．数列 1, 9, 8, 2, … 自第5项起，每一项都等于它前面四项之和的个位数。试问，是否在该数列中有连续的四项为3，0，4，4。

记 a(1)=1，a(2)=9，a(3)=8，a(4)=2，a(n+4)=(a(n+3)+a(n+2)+a(n+1)+a(n))%10.
计算机推算表明答案是肯定的，但是周期是1560, a(1561)~a(1564)重现1, 9, 8, 2。
所要寻找的 3, 0, 4, 4 最早出现在 a(1557)~a(1560), 刚好在黎明前的黑暗中。
暴力计算找到答案后，启发了下面的证明：

对于无限长的序列，必然存在循环。因为连续4项最多有10000种排列，到10001~10004累计会出现10001个排列，必然出现前面出现过的排列。一旦出现重复排列，就会从头开始循环。
既然产生循环，就能倒推。
a(n+4)=(a(n+3)+a(n+2)+a(n+1)+a(n))%10 → a(n)=(a(n+4)-a(n+3)-a(n+2)-a(n+1))%10

由倒推公式得
a(0)=(a(4)-a(3)-a(2)-a(1))%10=(2-8-9-1)%10=4
a(-1)=(8-9-1-4)%10=4
a(-2)=(9-1-4-4)%10=0
a(-3)=(1-4-4-0)%10=3
可见1,9,8,2的前4项就是3，0，4，4

这个问题的陷阱就在于循环的周期对于手工计算来说很长，它给的那个排列就在你的背后，如果顺推的话，得绕地球一圈回来才能发现背后的排列。
如果事先知道，直接回头就得到了。