数学竞赛
2005年第1
期9
命题与解题
一类染色问题的计数公式
邹 明
(山东省青岛第二中学,262101)
给彼此相连的若干区域染色,且任何相
邻的2个区域或间隔的2个区域染不同的颜色,是近年来高考和数学竞赛中的一类常见问题.下面运用排列组合的两个基本原理———加法原理、乘法原理,给出此类问题的几个一般情形的计数公式.
命题1 用m(m≥2)种不同的颜色,证明:如图1,记符合要求的染色方案为
an种,则区域A1有m种染法,区域A2,A3,
…,An各有m-1种染法.这包括了An与A1染同色或不同色两类:若区域An1染同色,AnA1n-1an-;若An1,则符合要求,有
n种染法.故有
an+an-1=m(m-1)
n-1
中n(的区域1,…,n色,且任何相邻的2个区
图1
.
域染不同的颜色.则不同的涂色方案种数为
nn
an=(-1)(m-1)+(m-1).
收稿日期:2004-01-19
n
两端同乘以(-1)得(-1)nan-(-1)n-1an-1
=-m(1-m)
n-1
.
两端求和得
nk=3
∑
kk-1
[(-1)ak-(-1)ak-1]
(提示:设有1,2,3,4,5五种颜色给四棱锥
S-ABCD染色.由于S、A、B所染颜色不同,则有
270,在条件7|xi(1≤i≤4),且13|xj(5≤j≤7)下的
正整数解的组数.由条件,设x1+x2+x3+x4=7m,
x5+x6+x7=13n(m≥4,n≥3).于是,m、n即是不
5×4×3=60种染色方法.设S、A、B已染好,再分类
讨论,C、D有7种染法.共有60×7=420种染法.)
4.在世界杯足球赛前,F国教练为了考察A1,A2,…,A7这7名队员,准备让他们在3场训练比赛
定方程7m+13n=270的一组正整数解.m=
≥
4,易得3≤n≤18,(n∈N).解方程组得
7
23232
共有正整数解C332C2+C19C9+C6C16=42244组.)
(每场90分钟)中都上场.假设在比赛的任何时刻,
这些队员中有且仅有1人在场上,且A1,A2,A3,A4每人上场的总时间(以分钟为单位)均能被7整除,
A5,A6,A7每人上场的总时间(以分钟为单位)均能
5.如图2,在1个正六
边形的6个区域栽种观赏植物,要求同1区域种同一种植物,相邻的2区域种不同的植物.现有4种不同植物可供选择.则有
种栽种方案.
(2001,全国高中数学联赛)
图2
被13整除.如果每场换人次数不限,那么,按每名队员上场的总时间计算,共有多少种不同的情况?
(2002,全国高中数学联赛)
(提示:设第i名队员上场的时间为xi分钟(i=1,2,…,7),问题即求不定方程x1+x2+…+x7=