2010-2012年全国高中数学联合竞赛试题(一试、加试(15)

1

max (n k),

n

1

n

n

11 k kn

k

， n

k

故

a A

kk 1

k 1

nAn Ak

k 1

n

A

k 1n 1

n 1

n

Ak An Ak

k 1

n 1

k n 1 1 2．

n k 1

4. 对于该种密码锁的一种密码设置，如果相邻两个顶点上所赋值的数字不同，在它们所在的边上标上a，如果颜色不同，则标上b，如果数字和颜色都相同，则标上c．于是对于给定的点A1上的设置（共有4种），按照边上的字母可以依次确定点A2,A3, ,An上的设置．为了使得最终回到A1时

的设置与初始时相同，标有a和b的边都是偶数条．所以这种密码锁的所有不同的密码设置方法数

等于在边上标记a，b，c，使得标有a和b的边都是偶数条的方法数的4倍．

设标有a的边有2i条，0 i ，标有b的边有2j条，0 j

2

n n 2i

．选取2i条边标 2

2i2j

记a的有Cn种方法，在余下的边中取出2j条边标记b的有Cn 2i种方法，其余的边标记c．由乘2i2j法原理，此时共有CnCn 2i种标记方法．对i，j求和，密码锁的所有不同的密码设置方法数为

n

2 i 0

n 2i

2

2i2j CC n n 2i ． ①

j 0

4

这里我们约定C0 1．

当n为奇数时，n 2i 0，此时

n 2i

2 j 0

C

2j

n 2i

2n 2i 1． ②

代入①式中，得

4

i 0

n 2

n 2i n n

2 2 2

2i 2j 2in 2i 12in 2iCC 4C2 2C2 nn 2inn

j 0i 0i 0