高中数学竞赛_奥林匹克数学的技巧(下篇)

高中数学竞赛讲义

从而 1 (3r1) (3r2) … (3rn)

9( r1 r2 … rn) 9(S1 S2 … Sn) 得 (S1 S2 … Sn)

2

2

2

222

1 9

2-7-19 计算两次

对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的，这叫计算两次原理成富比尼原理。计算两次可以建立左右两边关系不太明显的恒等式。在反证法中，计算两次又可用来构成矛盾。

例2-168 能否从1，2， ，15中选出10个数填入图2-66的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所的的14个差恰好为1，2， ，14？

解 考虑14个差的和S，一方面S=1+2+ +14=105为奇数。

另一方面，每两个数a,b的差与其和有相同的奇偶性 a b a b(mod2)

因此，14个差的和S的奇偶性与14个相应数之和的和S’的奇偶性相同，由于图中的每一个数a与2个或4个圈中的数相加，对S’的贡献为2a或4a，从而S’为偶数，这与S为奇数矛盾，所以不能按要求给图中的圆圈填数。

例2-169 设a1,a2,…,an为1，2， ，n的一个排列，fk是集合aiai ak,i k元素的个数，而gk是集合aiai ak,i k元素的个数（k 1,2,…,n），证明

f g

kk 1

k 1

nn

k

证明 考虑集合S (ai,ak)ai ak,i k的元素个数S。一方面，固定k先对i求和，然后再对k求和，得S

n

n

f

k 1

n

k

；另一方面，固定i先对k求和，然后再对i求和，又得到

S gi gk，所以得 fk gk。

i 1

k 1

nn

k 1k 1

2-7-20 辅助图表

解题中作一些辅助性的图形或表格，常克使问题的逻辑结构直观地显现出来，并提供程序性操作的机会，例3-2的处理曾获冬令营特别奖，同样的方法可用来求和

Sn 12 22 … n2

n(n 1)(2n 1)

6

例2-170 设N 1,2,…,n ,n 2。N的子集Ai(i 1,2,…,t)组成集合F A1,A2,…,At 。如果对于每一对元素x,y N，有一个集合Ai F使得Ai x,y 恰含一个元素，则称F是可分的。如果N的每一个元素至少属于一个集Ai F，则称F是覆盖的。问使得有一个F A1,A2,…,At 既是可分的又是覆盖的t的最小值f(n)是多少？