数学奥林匹克升级题

到处瞎逛

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