竞赛培训专题2----染色问题与染色方法.docx

该【竞赛培训专题2----染色问题与染色方法 】是由【小屁孩】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【竞赛培训专题2----染色问题与染色方法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。编号:时间:2021年x月x日书山有路勤为径,学海无涯苦作舟页码:第-2-页共10页第-2-页共10页竞赛培训专题2---染色问题与染色方法1.?-1(a),:存在一个矩形,?由抽屉原则,第1行的7个小方格至少有4个不同色,不妨设为红色(带阴影)并在1、2、3、4列(如图29-1(b)).在第1、2、3、4列(以下不必再考虑第5,6,7列)中,如第2行或第3行出现两个红色小方格,则这个问题已经得证;如第2行和第3行每行最多只有一个红色小方格(如图29-1(c)),那么在这两行中必出现四角同为蓝色的矩形,:(1)在上面证明过程中除了运用抽屉原则外,还要用到一种思考问题的有效方法,就是逐步缩小所要讨论的对象的范围,把复杂问题逐步化为简单问题进行处理的方法.(2)-,:时间:2021年x月x日书山有路勤为径,学海无涯苦作舟页码:第-2-页共10页第-2-页共10页例2??(第2届全国部分省市初中数学通讯赛题)证明:用15块大小是4×1的矩形瓷砖和1块大小是2×2的矩形瓷砖,不能恰好铺盖8×?将8×8矩形地面的一半染上一种颜色,另一半染上另一种颜色,再用4×1和2×2的矩形瓷砖去盖,如果盖住的两种颜色的小矩形不是一样多,?如图29-3,用间隔为两格且与副对角线平行的斜格同色的染色方式,,地面上黑、×1的矩形砖不论是横放还是竖盖,且不论盖在何处,总是占据地面上的两个白格、两个黑格,故15块4×,而与主对角线平行的相邻格总是异色,所以,不论怎样放置,一块2×2的矩形砖,×.??例3?(1986年北京初二数学竞赛题)如图29-4(1)是4个1×1的正方形组成的“L”形,用若干个这种“L”形硬纸片无重迭拼成一个m×n(长为m个单位,宽为n个单位)的矩形如图29-4(2).∵m×n矩形由“L”形拼成,∴m×n是4的倍数,∴m、n中必有一个是偶数,×n矩形中的m列按一列黑、一列白间隔染色(如图29-4(2)),则不论“L”形在这矩形中的放置位置如何(“L”形的放置,共有8种可能),“L”形或占有3白一黑四个单位正方形(第一种),或占有3黑一白四个单位正方形(第二种).设第一种“L”形共有p个,第二种“L”形共q个,则m×n矩形中的白格单位正方形数为3p+q,而它的黑格单位正方形数为p+3q.∵m为偶数,∴m×n矩形中黑、白条数相同,黑、+q=p+3q,从而p=“L”形的总数为2p个,即“L”形总数为偶数,所以m×n一定是8的倍数.????编号:时间:2021年x月x日书山有路勤为径,学海无涯苦作舟页码:第-3-页共10页第-3-页共10页2.?线段染色和点染色下面介绍两类重要的染色问题.(1)???“边染色”(或称“线段染色”),????????(1947年匈牙利数学奥林匹克试题)世界上任何六个人中,,而来看与之等价的下述命题例5?(1953年美国普特南数学竞赛题)空间六点,任三点不共线,任四点不共面,成对地连接它们得十五条线段,用红色或蓝色染这些线段(一条线段只染一种颜色).求证:无论怎样染,?设A、B、C、D、E、、AC、AD、AE、AF,由抽屉原则这五条线段中至少有三条颜色相同,不妨设就是AB、AC、AD,△BCD的三边,如其中有一条边例如BC是红色的,则同色三角形已出现(红色△ABC);如△BCD三边都不是红色的,则它就是蓝色的三角形,,不论在哪种情况下,,两人认识的连红线,不认识的连蓝线,??(第6届国际数学奥林匹克试题)有17位科学家,其中每一个人和其他所有人的人通信,:?用平面上无三点共线的17个点A1,A2,…,,y,z,两位科学家讨论x连红线,讨论y连蓝线,,A1A3,…,A1A17,由抽屉原则这16条线段中至少有6条同色,不妨设A1A2,A1A3,…,:时间:2021年x月x日书山有路勤为径,学海无涯苦作舟页码:第-4-页共10页第-4-页共10页2,A3,…,A7的15条线段,如其中至少有一条红色线段,则同色(红色)三角形已出现;如没有红色线段,则这15条线段只有蓝色和黄色,由例5知一定存在以这15条线段中某三条为边的同色三角形(蓝色或黄色).,将n点中每两点都用线段相连所得的图形叫做n点完全图,“顶点”,这些线段叫做“边”.现在我们分别用图论的语言来叙述例5、?若在k6中,任染红、蓝两色,?在k17中,任染红、蓝、黄三角,则必有一只同色三角形.(2)?(首届全国中学生数学冬令营试题)能否把1,1,2,2,3,3,…,1986,1986这些数排成一行,使得两个1之间夹着一个数,两个2之间夹着两个数,…,两个1986、之间夹着一千九百八十六个数??将1986×2个位置按奇数位着白色,偶数位着黑色染色,,同一个奇数要么都占黑点,,占据白点A1=993个,黑色B1=,占据白点A2=2a个,黑点B2=2b个,其中a+b=,共占白色A=A1+A2=993+=B1+B2=993+2b个,由于a+b=993(非偶数!)∴a≠b,从而得A≠、:时间:2021年x月x日书山有路勤为径,学海无涯苦作舟页码:第-5-页共10页第-5-页共10页“点”可以是有限个,也可以是无限个,?对平面上一个点,任意染上红、蓝、:?作出一个如图29-7的几何图形是可能的,其中△ABD、△CBD、△AEF、△GEF都是边长为1的等边三角形,CG=,如果B、E、D、F中有红色,、E、D、F都为蓝点或黄点时,又如果B和D或E和F同色,,在这种情况下,如果C或G为黄色或蓝点,则CB、CD、GE、GF中有两条是端点同色的单位线段,,C、G均为红点,,.?6×6的方格盘,能否用一块大小为3格,形如的弯角板与11块大小为3×1的矩形板,.?(第49届苏联基辅数学竞赛题)在两张1982×1983的方格纸涂上红、黑两种颜色,,有一个黑格与一个红格重合,.?有九名数学家,每人至多会讲三种语言,每三名中至少有2名能通话,.?如果把上题中的条件9名改为8名数学家,那么,这个结论还成立吗?为什么?5.?设n=6(r-2)+3(r≥3),求证:如果有n名科学家,每人至多会讲3种语言,每3名中至少有2名能通话,那么其中必有????.?(1966年波兰数学竞赛题)大厅中会聚了100个客人,他们中每人至少认识67人,证明在这些客人中一定可以找到4人,:时间:2021年x月x日书山有路勤为径,学海无涯苦作舟页码:第-7-页共10页第-7-页共10页7.?(首届全国数学冬令营试题):一定存在一个边长为1或的正三角形,、4行染红色、2、5行染黄色、3、6行染蓝色,′,其余的黑格(奇数个)均与第二张纸的黑格重合,那么由第二张纸上这一列的黑格个数为偶数,知必有一黑格与第一张纸上的红格重合,即在这一列,第一张纸上有一方格B与第二张纸上不同颜色的方格B′、B所在行上各有一个方格C、D,第二张纸上与它们重合的方格C′、D′的颜色分别与C、,A2,…,,就用线连结,并涂某种颜色,以表示不同语种。两人不通话,就不连线.(1)果任两点都有连线并涂有颜色,那么必有一点如A1,以其为一端点的8条线段中至少有两条同色,比如A1A2、,A2,A3之间可用同一语言通话.②如情况①不发生,则至少有两点不连线,比如A1、,,,,如图所示(图中每条线旁都有一个数字,以表示不同语种).、A2、…、A100表示客人,红、蓝的连线分别表示两人相识或不相识,因为由一个顶点引出的蓝色的线段最多有32条,(设为A1、A2、A3)(连同每条线段上的一个端点AI,I≠1,2,3),这样,在图中至少还剩下四个点,除A1、A2、A3外,设第四点为A4,这四个点中A1,A2,A3每一个点与其它的点都以红色的线段相连,于是客人A编号:时间:2021年x月x日书山有路勤为径,学海无涯苦作舟页码:第-7-页共10页第-7-页共10页1、A2、A3、"若平面上有两个异色的点距离为2,地么必定可以找到符合题意的三角形".(白色)为圆心,,,以OP为底作腰长为2的三角形OPR,则R至少与O、P中一点异色,:时间:2021年x月x日书山有路勤为径,学海无涯苦作舟页码:第-8-页共10页第-8-页共10页精品文档欢迎下载