Combinatorial Problems In Mathematical Competitions Pdf

Combinatorial Problems in Mathematical Competitions

Yao Zhang

How much do you like this book?

What's the quality of the file?

Download the book for quality assessment

What's the quality of the downloaded files?

This book focuses on combinatorial problems in mathematical competitions. It provides basic knowledge on how to solve combinatorial problems in mathematical competitions, and also introduces important solutions to combinatorial problems and some typical problems with often-used solutions. Some enlightening and novel examples and exercises are well chosen in this book. With this book, readers can explore, analyze and summarize the ideas and methods of solving combinatorial problems. Their mathematical culture and ability will be improved remarkably after reading this book.

Publisher:

World Scientific

Series:

Mathematical Olympiad

The file will be sent to your email address. It may take up to 1-5 minutes before you receive it.

The file will be sent to your Kindle account. It may takes up to 1-5 minutes before you received it.

Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.

          Combinatorial Problems in Mathematical Competitions  Mathematical Olympiad Series ISSN: 1793-8570 Series Editors: Lee Peng Yee (Nanyang Technological University, Singapore) Xiong Bin (East China Normal University, China)  Published  Vol. 1  A First Step to Mathematical Olympiad Problems by Derek Holton (University of Otago, New Zealand)  Vol. 2  Problems of Number Theory in Mathematical Competitions by Yu Hong-Bing (Suzhou University, China) translated by Lin Lei (East China Normal University, China)  Vol. 3  Graph Theory by Xiong Bin (East China Normal Un iversity, China) & Zheng Zhongyi (High School Attached to Fudan University, China) translated by Liu Ruijang, Zhai Mingqing & Lin Yuanqing (East China Normal University, China)  Vol. 4  Combinatorial Problems in Mathematical Competitions by Yao Zhang (Hunan Normal University, P. R. China)  Vol. 5  Selected Problems of the Vietnamese Olympiad (1962-2009) by Le Hai Chau (Ministry of Education and Training, Vietnam) & Le Hai Khoi (Nanyang Technology University, Singapore)  Vol. 6  Lecture Notes on Mathematical Olympiad Courses: For Junior Section (In 2 Volumes) by Xu liagu  Yao Zhang Hliliall Norlll,1i U lliversifY,  Vol.  41  PR  (hillil  Mathematical Olympiad Series  Combinatorial Problems in Mathematical Competitions  ~ East China Normal ~ University Press  ,~World Scientific  Published by East China Normal University Press 3663 North Zhongshan Road Shanghai 200062 China and World Scientific Publishing Co. Pte. Ltd. 5 Toh Tuck Link, Singapore 596224 USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601 UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE  British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library.  COMBINATORIAL PROBLEMS IN MATHEMATICAL COMPETITIONS Copyright © 2011 by East China Normal University Press and World Scientific Publishing Co. Pte. Ltd.  All rights reserved. This book, or paris thereof, may not be reproduced in any/orm or by any mea; ns, electronic or mechanical, including photocopying, recording or any in/ormation storage and retrieval system now known or to be invented, without writ/en permissionjromthe Publisher.  For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher.  ISBN-13 978-981-283-949-7 (pbk) ISBN-IO 981-283-949-6 (pbk)  Printed in Singapore by Mainland Press Pte Ltd.  Copy Editors NI Ming East China Normal University Press, China ZHANG Ji World Scientific Publishing Co., Singapore WONG Fook Sung Temasek Polytechnic, Singapore KONG Lingzhi East China Normal University Press, China  This page intentionally left blank  Introduction  This book consists of three parts: fundamental knowledge, basic methods and typical problems.  These three parts introduce the  fundamental knowledge of solving combinatorial problems,  the  important solutions to combinatorial problems and some typical problems with often-used solutions in the high school mathematical competition respectively. In each chapter there are necessary examples and exercises with  solutions. These examples and exercises are of the same level of difficulty as the China Mathematical League Competitions which are selected from mathematical competitions at home and abroad in recent years. Some test questions are created by the author himself and a few easy questions in China Mathematical Olympiad (CMO) and IMO are also included. In this book, the author pay attention to leading readers to explore, analyze and summarize the ideas and methods of solving combinatorial problems. The readers' mathematical concepts and abilities will be improved remarkably after acquiring knowledge from this book.  This page intentionally left blank  Preface  Combinatorial Mathematics has a long history. Thousands of years ago, some simple and interesting combinatorial problems started to be involved in the ancient Chinese masterpieces such as He Tu and Luo Shu. In the recent 20 years, owing to the rapid development of know ledge such as Computer Science, Coding Theory, Programming Theory, Digital Communication and Experimental Designing, a series of theoretical and practical problems need to be solved by discrete mathematics. Moreover, the questions which were raised by the logic of  combinatorial  mathematics  itself  and  other  branches  of  mathematics, has made the research about combinatorial mathematics to flourish and very rich. The problem-solving techniques and methods are daedal, transforming this ancient mathematical idea into a rigorous mathematical subject. The combinatorial questions in the mathematical competitions are always straightforward, but the people who solve these problems should be endowed with the power of acute observation,  rich  imagination and necessarily skills . There are no fixed methods that can be followed, and various questions of different level of difficulties are very rich. Hence, combinatorial questions have been included in different levels of intelligence test and mathematical competition. This book focus on the combinatorial problems in the mathematics competition, and consists of three parts: fundamental knowledge, basic methods and typical problems. This book is a translation from the author 's book of the same title (in Chinese), with a few amendments ix  x  Combinatorial Problems in Mathematical Competitions  and supplements. It not only emphasizes the fundamental knowledge of solving combinatorial problems in mathematical competitions, but also introduces to the readers the important solutions to combinatorial problems and some typical problems with solutions that are often used. In the choice of examples and exercises, except the questions which strikingly newer have been selected as far as possible, but the novel test questions which are the same difficult level as the China Mathematical League Competitions in the mathematical competition at home and abroad in recent yeas have been chosen deliberately. Some test questions created by the author himself and a few easy questions in China Mathematical Olympiad (CMO) and IMO are also included. In this book, the author pays attention to leading the readers to explore, analyze and summarize the ideas and methods of solving combinatorial problems. The readers' mathematical concepts and abilities will be improved remarkably after acquiring the knowledge from this book.  Introduction  Vll  Preface PART ONE  Chapter 1 Chapter 2 Chapter 3 Chapter 4  PART TWO  Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9  IX  Fundamental Knowledge  Principles and Formulas of Counting  1  Exercise 1  16  Pigeonhole Principle and Mean Value Principle  20  Exercise 2  31  The Generating Functions  33  Exercise 3  38  Recurrence Sequence of Numbers  40  Exercise 4  54  Basic Method  Classification and Method of Fractional Steps  56  Exercise 5  65  Correspondent Method  67  Exercise 6  84  Counting in Two Ways  87  Exercise 7  98  Recurrence Method  100  Exercise 8  109  Coloring Method and Evaluation Method  112  Exercise 9  121 xi  xii  Combinatorial Problems in Mathematical Competitions  Chapter 10  Reduction to Absurdity and the Extreme Principle  123  Exercise 10  130  Local Adjustment Method  132  Exercise 11  141  Construction Method  143  Exercise 12  151  Chapter 11 Chapter 12  PART THREE  Chapter 13 Chapter 14  Chapter 15  Typical Problems  Combinatorial Counting Problems  153  Exercise 13  165  Existence Problems and the Proofs of Inequalities  in Combinatorial Problems  167  Exercise 14  179  Combinatorial Extremum Problems  182  Exercise 15  199  Solutions to Exercises  201  Chapter  Principles and Formulas of Counting  1  1.1  Two  Ba~ic  Countin9 Princigles  The Addition Principle  If there are  11 I  different objects in the first set,  second set, ... , and  11  In  11 2  objects in the  objects in the m th set, and if the different sets  are disjoint, then the number of ways to select an object from one of  + 11 2 + ... + 11  the m sets is 11 I  In •  The Multiplication principle  Suppose a procedure can be broken into m successive (ordered) stages, with  11 I  outcomes in the first stage,  stage, ... , and  11  In  11 2  outcomes in the second  outcomes in the m th stage. If the composite  outcomes are all distinct, then the total procedure has  11 1112 ... 11  In  different composite outcomes. How many ways are there to choose 4 distinct positive  Example 1  integer numbers 500 } such that  XI '  XI '  X2 '  x} '  X2' X } , X4  X4  from the set S  =  {1, 2, ... ,499,  is an increasing geometric sequence and  its common ratio is a positive integer number? Solution Let a I , a I q, a 1 q2 , a 1 q } (a 1 , q E N+ ,  q  ? 2) be the four  . are chosen by us, then a 1 q } :;( 500, q :;( ~SOO numbers whIch :;( 13 500. a1  Hence 2 :;( q :;( 7, and 1 :;( a 1  :;(  J, that is the number of the  [SqO}O  J.  geometric sequences with the common radio q is [SqO}O  By the  addition principle, the number of the geometric sequences satisfying  Combinatorial Problems in Mathematical Competitions  2  the conditions is 7  ~ [5(~O ] = q~2  q  62  + 18 + 7 + 4 + 2 + 1  = 94.  So the answer to the question is 94. How many 4-digit odd numbers with distinct digits are  Example 2  there? A 4-digit number is an ordered arrangement of 4 digits  Solution  (leading zeros not allowed). Since the numbers we want to count are odd. the unit digit can be anyone of 1. 3. 5. 7. 9. The tens digit and the hundreds digit can be anyone of O. 1 •...• 9, while the thousands digi t can be anyone of 1. 2. . ..• 9. Thus there are 5 choices for the unit digit. Since the digits are distinct. we have 8 choices for the thousands digit. whatever the choice of the unit digit is. Then there are 8 choices for the hundreds digit. whatever the first 2 choices are. and 7 choices for the tens digit. whatever the first 3 choices are. Thus by the multiplication principle. the number of 4-digit odd numbers with distinct digits is equal to 5 x 8 x 8 x 7  2240.  Permutation Without Repetition and  1. 2  Permutation m (m ~ n)  =  An ordered arrangement of n distinct objects taking  distinct objects at a time is called a permutation of  n  distinct objects taking m distinct objects at a time. Since the objects is not repeated, the permutation is also called the permutation without repetition. and the number of "permutation of n distinct objects taking m distinct objects" is denoted by P;;, or 1\;;, * • then P;~ =  *  p~, (A;~)  n(n -1)(n -2)"'(n -m +1)  is also written as  P;~  CA;;') in some countries.  n!  en - m)!'  Principles and Formulas of Counting  where m ,::;;; n , and there is a convention O! Especially, when m  =  =  3  1.  n, the permutation of n distinct objects  taken n distinct objects is called all permutation of n distinct objects. The number of all permutation of n distinct objects is equal to  P;:  An unordered selection of n distinct objects taking  Combination m (m ,::;;; n)  =n(n-1)(n-2)···2·1 =n!  distinct objects at a time is called a combination of n  distinct objects taking m distinct objects at a time. Since the objects is not repeated, a combination of n distinct objects taking m distinct objects is also called a combination without repetition. The number of "combination of by  C:),  then  (n ) m  P"m m!  n  distinct objects taking m distinct objects" is denoted  n(n -1)(n -2)···(n -m m!  Example 3  + 1)  n! m!(n -m)!·  How many 5-digit numbers greater than 21300 are there  such that their digits are distinct integers taken from {1, 2, 3, 4, 5}. Solution  I  We divide these 5-digit numbers satisfying the  required conditions into 3 types: The number of 5-digit number whose ten thousands digit may be anyone of 3, 4 or 5 is equal to Pf pt. The number of 5-digit number whose ten thousands digit be 2 and thousands digit be anyone of 3, 4 or 5 is equal to Pf P~ . The number of 5-digit number of ten thousands digit be 2, and thousands digit be 1 is equal to  P~  By the addition principle,  . the number of 5-digit numbers  satisfying the required conditions is equal to PI Pi Solution]I  + PI P~ + P~  =  96.  Since the number of 5-digit numbers with distinct  digits taken from 1, 2, 3, 4, 5 equals  P~,  and there are only pt  numbers (their ten thousands digit are equal to 1) not exceeding 21300. Hence the number of 5-digit numbers satisfying the required  Combinatorial Problems in Mathematical Competitions  4  conditions equals  p~  - Pi = 96. ,  1.3  Repeated Permutation and ReQeateel G0mbinati0f1 __  -.J  An ordered arrangement of n distinct  Repeated Permutation  objects taking m objects at a time (each object may has a finite repetition number) is called a repeated permutation of n distinct objects taken m objects at a time. The number of this repeated permutation is equal to n '" . This conclusion could be proved easily by the multiplication principle. An unordered selection of n distinct  Repeated Combination  objects taking m objects (each object may has a finite repletion number) is called a repeated combination. The number of this n + m - l) repeated combination is equal to ( m .  Proof  Denote the n distinct objects by 1, 2, ... , n. Then  repeated combination of n distinct objects taken m objects has the following form: {iI ' i 2 , ... , i ",}  (1 ~ il ~ i2 ~ ..• ~ i ", ~ n).  Since  the selections could be repeated, so that the equality holds. Set j ii' j n  2  +m  = i 2 + 1, ... , j ", = i ",  + (m  - 1 , and the {j 1 , j 2  ••• ,  '  - 1),  then 1 ~ j 1 < j  2  < ...  I  < j '"  = ~  j ",} is just the combination without  repetition of n + m - 1 distinct objects: 1, 2, ... , n distinct objects .  +m  - 1 taken m  Hence the number of the required repeated combination equals  All Permutation of Incomplete Distinct Objects  Suppose that 11  objects consist of k distinct objects ai' az, ... , a k with repetition numbersn l ' 112> ... , n ", (11 1 + 112 + ··· + n", = 11)respective!y, the all permutation of these n objects is called the all permutations of the incomplete distinct objects.  We denote the number of all such  Principles and Formulas of Counting  permutation  by  5  then  n! n)!n2!'''nk!'  Proof Let f denote the number of the all permutation satisfying the conditions, If we exchange the same objects in each kind for the  mutually distinct objects and rearrange them, then we get n 1 ! n 2 ! .. 'n k ! all permutations of n distinct objects. By the multiplication principle, the number of the all permutation of n distinct objects is equal to f . n ) !  ! .. 'n k1. But the number of all permutation of equal to n !. Hence f . n 1 ! n 2 ! "'n k! = n1. Thus n  2  n  distinct objects is  Let's classify n distinct objects into k (k < n) distinct kinds, such that there are n i objects in ith kind Ci = 1, 2, ,,' , k, n ) + n 2 + .. , + n k = n). Then the number of the classify Multiple Combination  . equal to ( ways IS  n  )  n),n2, ... ,nk  distinct objects is equal to  n',....  1) .  n  ,.  nk.  distinct objects taken  n)  en) ). Then, the number of ways taking n 2  distinct objects from the residual n - n  ,  n ) .n2.  Since the number of ways of the  Proof  (  =  n -  n)  distinct objects is equal to  If we continue like this and invoke the multiplication  n2  principle, we find that the number of distinct partitioned kinds equals (  n )  C-  nl  n)) .. ,  n2  n! nl(n - n)!  C-  n) - n  2 -  .. , -  n k-))  nk (n -nl)! n2!(n -n ) -n2)!  (n - n) - ... - n k-) )  !  nk!(n - n) - ... -nk)!  n!  Remark  The counting formulas of all permutation of incomplete  Combinatorial Problems in Mathematical Competitions  6  distinct objects and multiple combination are the same, but their significance is different. We may prove the counting formula of the multiple combination by applying the same method of proving the formula of all permutation of incomplete distinct objects. Example 4 In how many ways can one chose 10 paper currencies from the bank and the volumes of these paper currencies are 1 Jiao, 5 Jiao, 1 Yuan,S Yuan, 10 Yuan 50 Yuan and 100 Yuan respectively? (Remark: The Jiao and Yuan are the units of money in China. ) Solution We are asked to count the repeated combinational number of ways to take 10 paper currencies from 7 distinct paper currencies. Using the formula of repeated combinatorial number, we get that the number of required distinct ways equals (7  + 10 -  1)  =  10  (16) 6  =  16 x 15 x 14 X 13 x 12 X 11 lX2X3 X 4 x 5 x 6  =  8008.  Example 5 Suppose that 3 red-flags, 4 blue-flags and 2 yellow-flags are placed on 9 numbered flagpoles in order (every flagpole hangs just one flag). How many distinct symbols consist of these flags are there? Using the formula of all permutation number of Solution incomplete distinct objects, we get that the number of distinct symbols equals  91 (3,4,9) = 314i21 2 ...  = 1260.  Example 6 How many are there to choose 3 pairs of players for the doubles from n ( ;? 6) players. Solution I The number of taking 6 players from n distinct players equals  G).  The 6 players is classified into three groups such  that each group contains exactly 2 players and the number of methods equals (  6 ), but the 3 groups are unordered, so the number 2, 2, 2  required ways is equal to  n! 61 1 6!(n - 6)! ·2!2!2! ·3!  n! 48(n - 6)!'  Principles and Formulas of Counting  Solution ]I  7  The number of ways of taking 6 players from n  distinct players equals  G).  Within the 6 players, there are  (~)  ways  to choose 2 players, and within the remaining 4 players there are (;)  (~)  ways to choose 2 players. Finally, there are  ways to choose 2  players with in the remaining 2 players. But the 3 pairs are unordered, so that the number of required ways is equal to  G)(~) G)(~)  n! 48 •  3! Remark  (n -  6)!'  If we change this problem to the following problem  "How many are there to choose 3 pair of player who serve as top seed players, second seed players and third seed players respectively, from n ( ~6) players?" Then the number of different ways equals  Since these 3 pair players are ordered, it is not divided by 3 !  1. 4 Circular Permutation of Distinct Elements - -and N!:"JlT'lber-0f N~e~eJ$:k!.§la~e~es§: -  ====:...:::::::::.;  Circular Permutation of Distinct Elements  If we arrange the n  distinct objects in a circle, then this permutation is called a circular permutation of n distinct objects. The number of circular permutation of  n  distinct objects equals p;: n  Proof  =  (n -  1) !.  Since n linear permutations AlA 2 ... A,,- l A " , A2A 3 ...  A "A l , ... , A,Al .. ·A ,,-2A,,- l give rise to the same circular permutation  and there are P;: linear permutations. Thus the number of circular  Combinatorial Problems in Mathematical Competitions  8  permuta tions of  distinct objects equals p;:  n  n  =  (n -  1) !.  Number of Necklace  Suppose that a necklace consists of n distinct beads which are arranged in circle, then the number of distinct necklaces is 1 (if n or 2) or ~ • Proof  that n  ~  (n  -1)! (if  If n  n  =  1  ~ 3).  1 or 2, then the number of necklace is 1. Assume  =  3. Since a necklace can be rotated or turned over without any  change, the number of necklaces is one-half of the number of circular permutation of Example 7  n  distinct objects, i.e. ~ •  (n  - 1)!.  How many ways are there to arrange 6 girls and 15  boys to dance in a circle such that there are at least two boys between any two adjacent girls? Solution  First, for every girl, we regard two boys as her dancing  partner such that one is at the left of this girl and another is at the right. Since 6 girls are distinct, we can select 12 boys from 15 boys in P~ ~  ways. Next, every girl and her two dancing partners are considered  as a group, each of residual 15 - 12  =  3 boys are also considered as a  group. Thus the total of groups is 9, and we can arrange them in a circle in (9 - 1)!  =  8! ways. By the multiplication principle, the  number of permutations satisfying the conditions equals  p~ ~  • 8!  =  15! • 8!  3!  1. 5  The Number of Solutions of the  The number of Solutions of The Indefinite Equation nonnegative integer solutions equation  X l + X2 + "' + X",  (Xl'  X2'  •.. ,  X",)  The number of  of the indefinite  = n (m, n EN+) is equal to  ( n + m - l) m - 1  =  9  Principles and Formulas of Counting  C  + :l - 1).  We consider that each nonnegative integer solution  Proof  X l' ... , X "' )  of the equation  XI + Xl  corresponds to a permutation of  Where  11  + ... + x'"  =  circles "0" and 177  (177,11  11 -  (x I  E N+)  1 bars" I " :  is the number of circles "0" at the left of first bar" I " ,  X I  ,  X ,+1  + 1) th  is the number of circles "0" between the i th bars" I" and the (i bars" I",  "', x '" is the number of circles "0" at the right of the (177 bar "I" . Since the correspondence IS an one-to-one  1 ) th  correspondence, the number of nonnegative integer solutions X l' ... , X "' ) 11  of the indefinite equation  XI  + Xl + ... + X'"  E N+) equals the number of the permutations of 1 ) bars " I ", i. e .  (m -  (l1 +m- 1) (11 -m 177- +1) 1 =  11  =  ( XI ' (177,  11  circles "0" and  .  11  The number of nonnegative integer solutions  Remark Xl ' ... , X"' ) 11  of the indefinite equation  XI  + X 2 + ... + x '"  =  ( x 11  I ,  (m,  E N+) is equal to the number of the repeated combinations from  11  distinct objects taken m objects (each object may has a finite repletion number) . The number of positive integer solutions  Corollary x "' ) m)  of the indefinite equation X I  equals  (11 -  + X2  + ... +x'"  (X I ' X2 ' ... ,  = 11 (m, 11  E N+,  71  ;;?  1 ).  m - 1  Proof Setting y ; = y ",  =  11  -  m.  X2 ' ... , X"' ) 11  E N+,  11  1  (i  = 1, 2, "',  m),  we get y I  + y 2 + ... +  Thus the number of positive integer solutions of the indefinite equation  X I + X2  + ... + x '"  =  11  (x 1 , (m,  ;;? m) equals number of nonnegative integer solutions (y I  Y2' ... , y", )  ( (71 - m)  X; -  of the indefinite equation YI  +m- 1) = - 1).  m - 1  (71  m-1  + Y 2 + ... + Y ",  = 11 - m, 1.  ,  e.  Combinatorial Problems in Mathematical Competitions  10  Applying above formula, we give another solution of example 7. Second Solution of Example 7  Suppose that 15 boys are divided  into 6 groups such that the leader of every group is a girl and there are at least two boys in every group. Denote the number of the boys in every group by + X2  XI  + ...  X l ' X 2' '"  = 15  + X6  X 6  ,  (x;  respectively, then  E N+ andx;  ~ 2,  i = 1,2,  ... ,  6) .  CD Setting y; = Y  I  Xi -  2  (i  = 1, 2, ... , 6), we get  + Y 2 + ... + Y 6 = 3  (y;  E Z and  y, ~  0, i = 1, 2, ... , 6). (2)  Thus the number of the integer solutions of CD is equal to the number 6 - 1) = of the nonnegative integer solutions of (2), i. e. ( 3 + 6 -1  (8)5 =  G). Hence the 15 boys are divided into 6 groups such that there are at least two boys in every group in C) ways. We arrange the 6 groups in a circle in (6 - 1)! = 5! ways. (The leader of every group is a girl and her position is definite.) 15 boys stand in this circle in 15! ways. By the multiplication principle,  we get that the number of the  (8)  Of ylllg reqmrement equa Is 3 • 5 .• I 15.I = 81·151 . permutatIOns satls . 3! '. °  °  Example 8  How many 3-digit integers are there such that the sum of digits of each integer is equal to 11 ? Solution  the  X I ' X2'  We denote the hundred digit , ten digit and unit digit by X3  respectively, then  CD Setting y I =  X I -  1, y 2 =  X 2'  Y3 =  X 3 ,  we get  Thus the number of integer solutions of CD equals the number of  Principles and Formulas of Counting  11  nonnegative integer solutions of @, i. e. ( 10 3+ _3 1- 1)  (12) 2 . But the  =  3-digit numbers cannot consist of the following 5 integer solutions of CD : (11, 0, 0), (10, 1, 0), (10,0,1), (1, 10,0), (1,0,10), so that the number of the 3-digit numbers satisfying conditions equals (122) _ 5  =  61.  1. 6  ~h e  Incltlsiofl - EXQltlsiofl Principle  The Inclusion - Exclusion Principle Let A I , A 2 , finite sets. We denote the number of elements of Ai by 2, ... , n). Then  IAI  ••• ,  A" be n  IAi I  (i  =  1,  "  I = ~ I A i 1- ~ I Ai n A j I  U A 2 U ... U A"  i=l  J,;;;;i<j ...n  + ~  IAi nA j nA k  1- '"  CD  t ... i <jd.;;;n  +(Proof  IAI  1) n-I  n A2 n .. , n A"  I.  For any x EA I UA 2 U'" UA " , we show that x contributes  the same count to each side of CD . Since x belongs to at least one set of A I , A 2 , ••• , A". Without loss of generality, let x belongs to A I , A 2 , ••• , Ak and not belong to other sets. In this case, x is counted one time in A I U A 2 U ... U A".  k  But at the right side of CD , x is counted: ( ) times in 1  times in ~ I A 3 l .;;;i<j<koGI Consequently, at the right side of CD, x is counted in  ~ I A n A I, "', (k)  " ~  j  ,~I  I A i I ,(  ( _ 1)k - 1  j  (~)  =  (~) - ((~) - (~) + (~) - (~) - ... + ( _ 1)k(~))  =  1 - (1 - 1)k  =  1 time.  2  times  n A n A k I,  l .;;;i<j"'n  C) - (~) + (~) - ... +  k)  Combinatorial Problems in Mathematical Competitions  12  Obviously for any .r EtA I UA2 U ... UA", at the left side and right side  CD  of  .r is counted zero time.  Therefore, for any element .r, at the two sides of the same time and the equality Remark  CD  CD  .r is counted  is verified.  The above method to prove equality  CD  is called the  contributed method. Successive Sweep Principle (Sieve Formula)  A, (i  C =  SCi  1,2, ... , 11) and denote the complement of A, in S by A,  =  1, 2, ... ,  71),  then  I AI n A2 n ... n A" I  Proof  Let S be a finite set,  =  I S I- I AI  =  I S 1-  I:"  U A2 U ... U A"  I Ai I+  I:  I Ai  n Aj  I  Since  I AI  U A2 U ... U A"  I = I 5 I-I  AI U A2 U ... U A"  I  Q)  By De Morgan's Laws, we obtain  I A I U A2 U ... U A" I = I ~ n A 2 n ... n A" I Combining Q) and @ with Example 9  CD,  @  we deduce the equality (2) immediately.  Determine the number of positive integers less than  1000 which are divisible by neither 7 nor 5. Solution by i}, Ci  =  Let S  =  {1, 2, ... , 999 }, A i  =  {k I kE 5, k is divisible  5 or 7). Then the answer to this problem is  I As n A 7 I.  Applying the sieve formula, we get  I A s n A7 I  Example 10  =  I S I-I As I- I A7 I +1 As n A 7  =  999 -  =  999 - 199 - 142  [9~9 ] - [9~9 ] + [59~97 ]  + 28  =  686.  (Bernoulli-Euler problem of misaddressed letters)  How many ways to distribute  11  distinct letters into  71  corresponding  13  Principles and Formulas of Counting  envelops so that no letter gets to its corresponding envelops? Removing the words" letter" and" envelops" from this  Solution  problem, we really want to know that how many permutations of {1, 2, ... , n } there are such that k is not at k th place for any k (1 < k < n )? These permutations are called the derangements, and we denote  the number of derangements by D". Let S be the set of permutations of {1, 2, ... , n } and A i the set of permutations {a I ' a2' ... , a,, } of {1, 2, ... , n} satisfying a i Ci = 1, 2, ... , n). Obviously, we have  I S I= I Ai,  I Ai I =  n!,  n A i2 n .. · n Ai  k  (n -1) !,  1=  (n  I Ai  - k)!(1  n Ai  I=  =  l  (n - 2)!, "',  < i < i2 < ... < ik < 71). l  By the sieve formula, we get D"  =  I ~ n A2 n ... n A" I = I S I-I Al  " =1 S 1- ~  ~  -  I Ai 1+ ~ I Ai  n Ai  U A 2 U ... U A"  I  I  I A i n Ai n Ak I ... + ( - 1)" I A l n A 2 n ... n A" I  !t;;;i<jdQI  =  nl -  .  (n)(n - 1)1. + (n)Cn - 2)1. - (n)C 1 2 3 n - 3)1.  + "' + ( - 1)"(:)0! =  n1  .  (1 - -1I! + -1 _ -1 + ... + C- 1)" ) 2! 3! 71!'  Permutation and its fixed point  Let X  =  {1, 2, ... , n } , cp be a  bijective mapping between X and X. Then cp is called a permutation on X and we usually write a permutation as follows: (  123  ...  n)  cp(1) cp(2) cp(3)"'cpCn) . For i EX, if cpCi)  =  i, then i is called a fixed point of permutation cp  on X. From example 10, we have the following corollary.  Combinatorial Problems in Mathematical Competitions  14  The number of permutations with no fixed point of X  Corollary  is equal to  D  = n'(l - ~ +~- ~ + ... + ( - 1)") . 1! 2! 3! n!·  "  Suppose that X  Example 11  {I, 2, ... , n } and denote the  =  number of permutations with no fixed point of X by  i",  the number  of permutations with exactly one fixed point of X by g". Prove g"  1  1  i" -  1. (The 14th Canadan Mathematical Olympiad)  =  Proof  Let g,,; denote the number of permutations with exactly  one fixed point i (i  1, 2, ... ,  =  g"  n),  g,,1 + g,,2  =  then  + ... + g"".  By the above corollary, we have  i" = D",  g,,; = D,, -I(i  =  1,2, ... , n) andg" = nD,, -I.  Hence 1  i" -  g" 1  =  1D"  - nD ,, -1 1 1  = n! l -  TI  (  1  1  ( - 1)" )  ( - 1) "- 1)1 ( 1 - -1 + -1 - -1 + ... + -'---=--c_  - n • (n - 1)'  .  - 1)" = n ! .( -,n.  1  1  Example 12  1  + 2! - 3! + ... + -n-!1!  2!  3!  (n - 1)!  = 1.  A new sequence { a,,} is obtained from the sequence  of the positive integers {I, 2, 3, ... } by deleting all multiples of 3 or 4 except 5. Evaluate Solution  a200Y .  I (Estimate Value Method)  2, ... , n } , andA;  =  {k  1  Let a 2009 = n, 5 = {I,  k E 5, k is divisible by i } (i  =  3,4,5),  then the set of numbers which are not deleted is (A 3 nA4 nA s ) UA s . Applying the sieve formula, we get 2009  =  1  = 1  (A 3  A3  n A4 n As) U As n A4 n As 1+1 As  1  1  15  Principles and Formulas of Counting  =1 S +1 =  n -  I-I A3 I-I A4 I-I As 1+1 A3 n A 41+1 A3 nAs I A4 n As I-I A3 n A4 n As I +1 As I  [~ J- [~ J+ [3 :  4J+ [3 : 5J+ [4 : 5J- [3 X  Applying the inequality a - 1 2009  <  n -  (~  <  ~ X 5].  CD  [a ] ~ a, we obtain  - 1) -  (~  - 1) + 3 : 4  and 2009  >  n_.!J.-3 _.!J.-4 + (_n - - 1 ) + (_n - - 1) 3X5 3x5 + (4 :  =  3 Sn  5 - 1) - 3  X  ~  X  5  -3.  Uniting CZ) and (3), we get 3343  ~ <  n  <  3353  ~.  If n is the multiple of 3 or 4 but not 5, then n is not a term in new  sequence {a,,} , so the required n is only one of the following numbers: 3345, 3346, 3347, 3349, 3350, 3353.  Substituting these numbers to the equation is the solution of equation  CD,  CD,  we know that n = 3347  and the answer to this problem is  unique. Hence a2lHO = 3347. Solution ]I (Combinatorial Analysis Method)  Since the least  common multiple of 3,4 and 5 is 60. Let So = {1, 2, ... , 60}, A, = {k IkE So, k is divisible by i}, Ci  =  3,4, 5), then the set of numbers  which are not deleted in So is (A 3 n A4 n As) U As. Applying the sieve formula, we get  Combinatorial Problems in Mathematical Competitions  16  I (A 3  n A4 n A) U A  I = I A3  n A4 n As  I+1 As I.  =15 I-I A3 I-I A4 I-I As 1+1 A3  +1 A3 n As 1+1 A4 n As -I A3 n A4 n As I +1 As = 60 -  [6~) ] - [6~) ] +  n A4  I  I I  [3 6~ 4 ] + [3 6~ 5 ]  , [ 60 ] [ 60 ] 4x5 - 3X4x5  -t-  36.  =  Hence there are 36 terms of new sequence {a,,} in 5,,:  Let P  =  {a  l'  a1' .•• , a36}  integers and 1 ~ r  ~  and a"  =  60k  + r(k ,  r are the nonnegative  60). Since (a", 12) = (60k + r, 12) = (r, 12) =  1, or (a", 12) = (r, 12) ::;i: 1, but 5Ia", then 51 r. Hence rEP.  On the other hand, for any positive integer with the form as 60k r (k, r are the nonnegative integers and rEP). If (r, 12) (60k  + r,  12)  =  1, thus 60k  + r is a  =  +  1, so  term of new sequence {a,,}. If (r ,  12) ::;i: 1, then 5 I r (since rEP ), so 5 I 60k  + r,  then 60k  + r is also a  term of new sequence {a,,} . Therefore new sequence {a,,} consist of all positive numbers with the form as 60k  +r  (k, r are the nonnegative integers and rEP). For the  given k, we obtain 36 successive terms of new sequence {a,,} as r ranges over the set P. Note 2009 = 36 X 55 + 29, so a11W = 60 X 55 + a2'J. But a3f>  = 60,  a35  = 59,  = 58,  a33  = 55,  a32  = 53,  a31  = 50, a311 = 49,  a2~  = 47,  a3-1  thus a 211119 = 3300 + 47 = 3347.  Exercise 1 1  A teacher gave out n  + 1 prizes  to n students such that each  student has at least one prize. Then the number of distinct sending  Principles and Formulas of Counting  ways is ( (A)  2  17  ). nP;:+!  (B) (n  + 1)P;:  (C) P~+!  (D)  (n  +l)p" 2  "  Suppose that a teacher selects 4 students from 5 boys and 4  girls to form a debate team. If at least one boy and one girl must be selected, then the number of distinct selecting ways is ( ). (A) 60 (B) 80 (C) 120 (D) 420 3  If the 5-digit numbers greater than 20000 which are not the  multiples of 5 have the following properties: their digits are distinct and each digit is one of the numbers 1, 2, 3, 4, 5, then the number of these 5-digit numbers is ( ). (A) 96 (B) 76 4  (C) 72  (D) 36  If the coefficients A and B of the equation of a straight line  Ax + By = 0 are two distinct digits from the numbers 0, 1, 2, 3, 6, 7, then the number of distinct straight lines is - - - 5 If the base a and the variable x of the logarithm logax are two distinct digits from 1, 2, 3, 4, 5, 7, 9, then the number of distinct values of the logarithm logax is - - - 6 In a table tennis tournament, each player plays exactly one game against each of the other players. But during this process, there are 3 players who have withdrawn from the tournament and each of them participates in exactly two matches. If the total of matches is 50, then the number of matches whin the above 3 players is ( ). (A) 0  (B) 1  (C) 2  (D) 3  (China Mathematical Competition in 1994) 7 c  =  Suppose that a, b, c in the equation of straight line ax  + by +  0 are three distinct elements of set { - 3, - 2, -1, 0, 1, 2, 3} and  the inclination of straight line is an acute angle. Then the number of distinct straight lines is in 1999) 8  A2  X  . (China Mathematical Competition  3 rectangle is divided into six unit squares A, B, C, D,  E, F. Each of these unit squares is to be colored in one of 6 colors such that no two adjacent squares have the same colors. Then the  Combinatorial Problems in Mathematical Competitions  18  number of distinct coloring ways is _ _ __ 9 Two teams A and B participate in a table tennis tournament. There are 7 players of each team to engage in this tournament in a determined order. Firstly. 1st player of A team plays against 1" player of B team and the loser is eliminated. Afterward. the winner plays against 2nd player of another team. On subsequent steps. the play is similar. Thus the game does not end until all players of some team are eliminated. and another team wins. Then the number of the distinct processes of game is . (China Mathematical Competition in 1988) In a shooting tournament. eight clay targets  10  are arranged in two hanging columns of three each and one column of two. as pictured. A marksman is to break all eight targets according to the following rules:  (1) The  marksman first chooses a column from which a target is to be broken. (2) The marksman  (loth problem)  must then break the lowest remaining unbroken target in the chosen column. If these ruses are flowed. in how many different orders can the eight targets be broken. (8 th American Invitational Mathematical Examination in 1990) 11  How many ways are there to paint the five vertices of a regular quadrangular pyramid with 5 colors such that each vertex is exactly painted with one of 5 colors and the vertices with a common edge must be painted with different colors? (Remark A coloring is the same as another which is from the rotation of the former). It is given that there are two sets of real numbers A  12  =  {al •  andB = {b l • b 2 • •••• b so }. If there is a mapping j from A to B such that every element in B has an inverse image and jCal) ~j(a2) ~ ... ~j(alllll)' then the number of such mappings is  a2' •••• alOO}  (  )  .  (A)  ( 100) 50  CB)  G~)  (C) ( 100) 49  CD)  G~)  Principles and Formulas of Counting  19  (China Mathematical Competition in 2002) 13  A natural number a is called a "lucky number" if the sum of  its digits is 7. Arrange all "lucky numbers" in an ascending order, and we get a sequence al , a2' a3 , .... If an = 2005, then as" (China Mathematical Competition in 2005) 14  =  ----  How many ways are there to arrange n married couples in a  line such that no man is adjacent to his wife? 15  Suppose that all positive integers which are relatively prime  to 105 are arranged into a increasing sequence: aI' a2' a3' .... Evaluate a l(JO(J. (China Mathematical Competition in 1994) 16  How many n-digit numbers are there consisting of the digits  1, 2, 3 with at least one 1, at least one 2 and at least one 3?  and  Pigeonhole Principle also is called Drawer Principle or Dirichlet's Principle. Pigeonhole Principle is a basic and important principle of combinatorial mathematics which is widely used to prove many existence problems. The First Pigeonhole Principle  then at least one box contains  If m objects are put into n boxes,  [m ;; 1 ] + 1 or more objects, where [x]  denotes the largest integer less than or equal to x. If each of n boxes  The proof is by contradiction.  Proof  contained at most  [m ;; 1] of the objects,  objects would be at most n [m ;; 1 ]  ~  then the total number of  n • m ;; 1  =  m - 1. Since we  started with m objects, this is impossible. Corollary of The First Pigeonhole Principle  Let m  l'  m  2' ••• ,  m"  + ... +m" + 1 objects are put into n boxes, then the first box contains at least m + 1 objects, or the second box contains at least m 2 + 1 objects, ... , or the nth box contains at least m + 1 objects. be n positive integers. If m 1 +m2  1  n  Proof m  1  the  Proof by contradiction. If the first box contains at most  objects, and the second box contains at most m 2 objects, ... , and nth  box contains at most m" objects, then the total of objects would  be at most m  1  + m 2 + ... + m"  Since we start with m  1  + m 2 + ... +  Pigeonhole Principle and Mean Value Principle m"  + 1 objects,  21  it is impossible.  The Second Pigeonhole Principle  If m objects are put into n boxes,  then at least one box contains [: ] or less objects. Proof  Proof by contradiction . If each of n boxes contains at least  [ : ] + 1 objects, n • m  n  =  then the total of objects would be least n ( [ : ] + 1 ) >  m. Since we start with m objects, it is impossible.  Let m  Corollary of The Second Pigeonhole Principle  I '  m  2 '  •.• ,  m " be n positive integers. If ml + m 2 + ... + m " - 1 objects are put into n boxes, then the first box contains at most m  I  -  1 objects, or the  second box contains at most m 2 - 1 objects, ... , or the nth box contains at most m" - 1 objects. Proof Proof by contradiction. If the first box contains at least m I objects, and the second box contains at least m 2 objects, ... , and the nth box contains at least m" objects, then the total of objects would be at least m I + m 2 + ... + m " Since we start with m I + m 2 + .. , + m" - 1 objects, it is impossible. Example 1 (Ramsey's Theorem) There are six points in a 3dimensional space no four points of which are coplanar. Two distinct points determine a line segment, and let each line segment be colored red or blue. Then there exist a triangle such that the 3 sides of this triangle are all colored red or blue. Proof Consider a given point A. By Pigeonhole Principle , of the 5 line segments meeting A, either at least [5 ; 1  J+ 1  =  3 are colored  red or at least 3 are colored blue. For the sake of argument let us suppose that there are 3 line segments AB, AC and AD are colored red. Consider the triangle BCD, if a side of D BCD, say BD, is colored red, then the 3 sides of D ABD are all colored red. Otherwise, the 3 sides of D BCD all are colored blue. This completes the proof. It seems convenient to list some basic concepts of the graph theory that will be used throughout the book. The set V" of n points in a  22  Combinatorial Problems in Mathematical Competitions  plane is called the set of vertices. A complete graph on n vertices, denoted by K" , consists of a set V" of vertices and a set E of edges (or sides) connecting each pair of distinct vertices in V. A closed broken line which consists of m edges of K" is called an m -sided polygon, and the 3-sided polygon is also called a triangle. Let each of edges of a complete graph K" be colored in one of m colors, then this graph K n is called an m -colored complete graph. Let each side of an m -sided polygon P be colored red (or blue), then this m-sided polygon P is called a red (or blue) m-sided polygon. Applying the concepts of the graph theory, the Ramsey's theorem can be described equivalently as follows. Ramsey's Theorem  There exists a monochromatic triangle in a 2-  colored complete graph K 6. On the other hand, as in figure 2. 1, we can exhibit a 2-colored complete graph K 5 which has no a red triangle no a blue triangle (the solid lines colored red and the dashed lines colored blue). Generally, if there exists a smallest positive integer n with the following property: there exists a monochromatic  Figure 2.1  triangle in an m -colored complete graph K", then the smallest positive integer n is called Ramsey's number, denoted by Rn. So we getR 2 = 6 from the above conclusion. But it is very difficult to find the Ramsey's numbers. We only know a few Ramsey's numbers: R2 = 6, R3 = 17, R4 = 65, .... Suppose that we represent a people with a point. If two people are mutually acquainted, then two corresponding points are connected by a red line segment, and if two people are mutually unacquainted, then two correspondent points are connected by a blue line segment. Thus the above Ramsey's theorem becomes the following Hangary's mathematical competition problem: Prove that among any 6 persons there exist 3 persons who form  G)  mutually unacquainted persons.  =  3 pair of mutually acquainted or  (Acquaintance is a symmetric  23  Pigeonhole Principle and Mean Value Principle  relation. ) Let k be a given positive integer number. Find the  Example 2  smallest value of n such that among any n positive integer numbers there exist two numbers whose sum or difference is divisible by 2k . Let  Solution  aI' a2' ... , an  remainders modulo 2k be  rl'  be any n positive integers and their  r2'  ••• ,  then  rn ,  ri  E S  =  1,  {(),  2, ... , 2k - 1 }. Consider the following classifications of S: { () }, {1, 2k - 1 } , {2, 2k - 2}, ... ,{ k - 1, k  +  If n ::?- k  + 1} , {k }.  2, by the pigeonhole principle, among n integers r I  ,  Ci # j, i, j E S) which belong to the same group. So the sum or difference of ai and aj is divisible by 2k. On the other hand, it is not difficult to show that among k + 1 numbers (), 1, 2, ... , k there are not two numbers a and b such that a + b or a - b is divisible by 2k. It follows that the required smallest value is k + 2 . Example 3 Let a be a positive real number and n be a positive integer. Prove that there exist two positive integers p and q satisfying r2' ••• , rn  there exists two numbers  Firstly, we prove the following proposition: Given n  Proof  real numbers xo' such that I  is divided into  Xl' •.• , Xn  Xi -  X j  I<  E [0, 1), there exist i, j (0  that  i  =  nsmall intervals: [ 0,  [ia J, i  =  ~),  - m i)  -  [  Xi'  ~  X j -  ~),  , (0  X j  ... ,  <i <  (ka - m k)  1)  [n ~ 1, 1). < n)  which  < ia < m + 1 , i. e. 0 < there exist 0 < k < l < n such  I < ~, i. e. I (l n  j  <  I < ~. n  0, 1, . . . , n, then m,  < 1. By the above proposition,  I (la  <j  n  belong to same small interval. Thus I Xi Let m i  <i  +1  ~. In fact, suppose that the interval [0,  By Pigeonhole Principle, there exist  ia - m  rj  Ia _!i I < np --.L. p  the following inequality:  n)  ri'  i  - k)a -  em  i -  m k)  1<  Combinatorial Problems in Mathematical Competitions  24  1 n  Set p = l - k, q = m  I -  m  k ,  then p, q are positive integers and  ~_1 . l a _ 2...1 P np Remark  Since p )'0 1,  Ia - ; I ~ ~.  In other words, any real  number can be approximated to arbitrary precision by a ration number. Suppose that n numbers are deleted in the set S  Example 4  =  {1 ,  2, ... , 2005 } such that among the remaining numbers, no number equals to the product of other two. Find the smallest positive integers n with the above properties.  Consider the following 43 triples of S: {44, 45, 44  Solution  45 }, {43, 46, 43  X  46 }, {42, 47, 42  X  47 }, ... , {3, 86, 3  X  X  86}, {2,  87, 2 X 87 }. If the number of positive integers which are deleted in the  S is less than 43, then among the remaining numbers, there exist three numbers in a triple such that one of them equals the product of the other two. Hence, we must delete at least 43 elements in S. On the other hand, if we delete the following 43 number: 2, 3, 4, ... , 44 in S . Since the product of any two of the remaining numbers is at least 45  X  46 = 2070 or 1  X  a = a (a E {45, 46, ... ,  2005 }), among the remaining numbers, no number equals the product of the other two. Therefore the required smallest positive integers n is 43. Example 5  Suppose that at, a2' ... , a" (n )'0 4) are n distinct  integers in open interval (0, 2n). Prove that there exists a non-empty subset S of {at, a2' ... , a,, } such that the sum of all elements in S is divisible by 2n.  Proof  (1)  Case 1. n rf: {at, a2' ... , a,, }. Since 2n integers at,  a2' ... , a " , 2n - at, 2n -a2 ' ... , 2n - a" E { 1, 2, ... , 2n - t}, by  Pigeonhole Principle, it follows that there exist two of them who are equal. But no two of the numbers at, a2 ' ... , a" are equal and no two of the numbers 2n - at, 2n - a2' ... , 2n - a" are equal, so there is an  Pigeonhole Principle and Mean Value Principle  i and a j such that a i = 2n - a j. Since a i *- n, a j = 2n. In this case, the conclusion is valid. (2) Case 2. n E an =  {al' a2' ... , an}.  n. Consider n -1 numbers  any 3 numbersai  25  *- n, i *- j  aj  and a i  +  Without loss of generality, let  al , a2' ... , a n-l  (n - 1 ~ 3). If for  are divisible by n, then  <aj <ak' aj -ai andak -aj  + (aj - ai) ~ 2n. It is impossible. Hence there a i < a j (i , j E {1, 2, ... , n -1 }) such that a j - a  ak - ai = (ak - aj)  exist two numbers  i  is not divisible by n. Without loss of generality, let a 2 divisible by  -  a 1 be not  Consider the following n numbers:  11.  ( I ) If the n numbers module n are distinct, then there exists one of these numbers which is divisible by n. Suppose that this number is kn (k E N+). If k is an even, then the conclusion is valid. If k is an  odd, then k  + 1 is  an even and kn  + an  =  (k + Un is divisible by 2n .  The conclusion is also valid.  ( II) If there are two of the module  n,  n numbers which are congruent with  then their difference is divisible by  n.  But  a2 -  a  1  is not  divisible by n. Hence this difference is equal to the sum of some (at least one) of the numbers  al' a2' ... , a n-l (n -  1  ~  3). Thus this  conclusion is also valid as ( I ) .  Remark n  =  In this problem, the condition n  ~  4 is necessary. When  3, for set {1, 3, 4} the conclusion of this problem is not valid. Example 6  Let 49 students solve 3 problems and the score of each  problem is one of these nonnegative integers 0, 1, 2, 3, 4, 5, 6, 7. Prove that there exist two students A and B such that for each of the problems the scores of A is not less than B. (The Problem Prepared for 29 th IMO in 1988) Proof  Suppose that there are two students A and B such that for  first and second problem, their scores are the same. If the score of the third problem A get is not less than B's, then for each of the problems the scores of A is not less than B's. Now, suppose that for any two students, their scores of first and  26  Combinatorial Problems in Mathematical Competitions  second problems are not all the same and we represent each of the 49 students by a point Ci, j) (0  ~  i, j  ~ 7)  in a plane where i , j are his  (or her) scores of the first and second problems respectively. Thus the 49 students correspond to 49 distinct integer points in plane. Set S = {(i,j) I i, j are integer numbers and 0 ~ i, j ~ 7 }; M\ = { Ci, j)  Ci, j)  M2 = { Ci,j)  (i, j) E S, 0  M3 ={ Ci,j)  Ci, j)  M4 = {( i, j)  Ci, j) E S, 0  = 7,1 ~ j ~  7 };  ~j ~  7};  = 2ori = 5, 3  ~j ~  7};  4, j = 3 or i = 4, 4  ~j ~  7};  ES,O ~ i ~7 ,j ~  i  ~  6, j =lori = 6, 2  ES,O ~ i~5,j  ~  i  ~  = Oori  Ms ={ Ci,j) 1 (i, j) E S,  = 2,3 and 4  ~j ~  M6 = {Ci,j) I (i, j) E S,  = 0, 1 and 4  ~  7};  j ~ 7}.  Thus the 49 integer points belong to the set  By Pigeonhole Principle , there are at least [49 ;: 1] + 1  =  9 integral  points all of which belong to the same set, denoted by M. Since IM  5  I = I M 6 I = 8, where 1M i I denote the numbers of elements in  Mi' M is one of M \ , M 2 , M3 or M 4 • Since the 9 integral points in M  correspond 9 distinct students whose score of the third problem are 0, 1, 2, 3, 4, 5, 6, 7, there are at least two students whose scores of the third problem are the same. By the constructions of M \' M M 4' we know that there exists one (denoted by  2'  M 3 or  of the two  A)  students, such that for the first and second problems, the scores of A are not less than another student's (denoted by B). Therefore, for each problem, the scores of A are not less than B's. Example 7  Let nand  positive integer m  r  be two positive integers. Find the smallest  satisfying the following condition:  classification of the set {1, 2, ... , m } into r subsets A I (A;  nA  j  =  0,  ,  For each  A2,  ••• ,  Ar  i =1= j ), there exist two numbers a and b in a subset  27  Pigeonhole Principle and Mean Value Principle  Ai C1  ~  b  i ~ r) such that 1 ~ - ~ 1 a  + -n1 .  Denote the smallest value of m by m () ethe value of m 0 can  Proof  <  be obtained from the following analysis). Suppose that m  m (). Let  Aj = {i I i -jemodr), i ~ m } ej = 1, 2, ... , r). Then for any two  numbers a, b in a subset with a > b, we have b  ~a  - r  <mu-  r. Thus  ~=l+a - b>l + r b b m o- r  Hence when m  =  II  nr  + r,  al we h ave b > 1 + -;;. Therefore the  condition in the question cannot hold. Next, For m consider the er  + 1)  numbers nr, nr  + 1,  ... , nr  m  =  + r.  0  =  nr  + r,  By Pigeonhole  Principle, there exists a > b such that a and b are in the same subset. Then a - b 1  ~  r, b  ~  nr, so  < ~ = 1 +a b  - b <: 1 b ~  +~ ~ 1 +~ b nr  = 1 + 1-. n  Therefore, the required smallest value of m is m 0 Example 8  =  nr  + r.  Let a space figure G consist of n e ~ 4) vertices, no 4  vertices of which are coplanar and there are  [~2 ]+ 1 line  segments  connecting these vertices. Prove there exist two triangles with a common side in the figure G. Proof We will prove the statement by induction on n. For the basic case n  [~ 5  =  J+1  =  =  4, suppose the 4 vertices are A, B, C, D and there are  5 line segments connecting these vertices. Thus only (;)-  1 pair of these vertices is not connected by a line segment.  Without loss of generality, suppose that there is not a line segment connecting the vertices C and D . In this case, there exist two triangles ABC and ABD with a common side AB. Thus the basic case is proved. Now we assume that the statement is true for n k  + 1,  let a space figure G consist of k  =  k ~ 4. For n  + 1 vertices  =  and there are  28  [ (k  Combinatorial Problems in Mathematical Competitions  +4 1)2] + 1 l'me segments  . t h ese vertlces. . Then t h e sum connectmg  )2] + 1 ). By Pigeonhole Principle, there are at most [k ~ 1 ( [(k : 1 )2] + 1) ] line  of the line segments meeting each vertex equals 2 (  [(k :  1  segments meeting some vertex A. By deleting the vertex A and all line segments meeting vertex A, then among residual figure, there are k vertices and at least  line segments connecting these vertices. If k = 2m (m ?': 2) is even, then  If k  =  2m  -1 (m ?': 3) is odd, then  In a word. there are at least  [~ ] +  1 line segments connecting k  vertices. By the inductive hypothesis, there exist two triangles with a common side. Thus the statement is proved. Remark If n ( ?': 4) is even, then this becomes a question in the 2nd selection examination for the national team of China.  The mean value principle numbers and A  =  1 -Cal +a2 n  ( 1) Let a l ' az, ... , an be n real  + ...  +a n ), then at least one of the  29  Pigeonhole Principle and Mean Value Principle  numbers a 1 , a 2' ... , a" is greater than or equal to A and also at least one of these numbers is less than or equal to A . (2) Let al' a2' ... , a" be n positive real numbers and G :jala2 . .. a" , then at least one of the numbers al' a2' ... , an IS  gerater than or equal to G and also at least one of these numbers is less than or equal to G. Proof ( 1) Min {a,} ~ A ~ Max {a, }, (2) Min {a,} ~ G ~ l,;;i,;;n  l.;;iQl  1,,;;i';;l1  Max{a,}. 1.;;io0I  Suppose that 10 distinct numbers 1, 2, 3, 4, 5, 6, 7,  Example 9  8, 9, 10 are arranged in a circle with any order. Show that there exist 3 successive numbers whose sum is not less than 18. Suppose that al' a2' ... , alll are 10 numbers 1, 2, 3, 4, 5,6,7,8, 9, 10 in a circle. Without loss of generality, let al = 1, Proof 1  1  then3[(a2 +a3 +a+) +(as +a6 +a7) +(aH +a~ +allJ)] =3(2+3 + 4 + ... + 10) = 534 = 18. By the mean value principle, one of a2 +a3 + a +, a 5 + a 6 + a 7 and a 8 + a 9 + a 111 is not less than 18.  Example 10  Suppose that there are n (;? 4) distinct points in the  plane and each pair of them is connected by a line segment. If among all lengths of these line segments, only n + 1 lengths equal d. Prove that there exists a point P such that there are at least 3 line segments meeting P their lengths all equal d. Let n points be P l ' P 2' ••• , P n and the number of the line segments meeting P, with length d be d, (i = 1, 2, ... , n). Then Proof  d 1 +d 2  + ... +d"  =  2(n +1)  and  ~ (d 1 + d 2 + ... + d,,) = 2 (n + n  n  1)  > 2.  By the mean value principle, there existsd, ;?3, i.e. there are at least 3 line segments meeting P, their lengths all equal d . Example 11 Let fez) = CoZ" + C1Z,,-1 + ... + C,,-lZ + e" be a  30  Combinatorial Problems in Mathematical Competitions  polynomial of n degree with complex coefficients. Prove that there exists a complex number I  c"  Zo  such that I Zo 1<1 and I jCz o ) I ~ I CII 1+  I. .. 2rr k 2k rr .. 2k rr L et W = cos -2rr + Ism - , W k = W = cos + Ism -  P roo f I  n  Ck =0,1, ... ,  n-1), a  n  n  n  =cosa+isina. CWecan determine the value  ofafromthefollowinganalysis.) Thenw il =w" =l,w J *1 Cj =2, 3, . . . , n - 1) and 1/-·1  ~ wi  n  =  Cj  0 or n) ,  =  k~O  n-l  11-1  ~wi  =  l-(wj)"  ~WJk  k~1I  ------'-- = 0 (j = 2, 3, ... , n - 1) , 1  k~O  -Wj  1/-1  ~jCawk ) k~1I  = nCcoa"  +C,J.  We may select the argument  aof a such that the principle values of the  arguments of clla" and c" are equal. (In fact, let the principle values of the arguments of (  ~ Ca" - aII ).  )  CII  and c" be a o and  a"  respectively, then we set  a=  Hence  71-1  n-1  ~ I j(aWk) I ~I ~j(aWk) I =n I clla"  +C"  I  = nC I CII 1·1 a I" +1 c" I) = nCI  1+1  CII  C"  I).  By the mean value principle, there exists k II such that I j(awkl)  I~  Setzo =aWk' then I completes the proof. I)  Proof  II  Zll  1/-1  ~ ~ n  k~O  I jCawk) I = I CII 1+1 c" I.  1= 1, and I jCz o ) I~I  Let the complex number  u  CII  1+1  C"  I. This  satisfy that I u I = I CII 1+1  c"  I  Pigeonhole Principle and Mean Value Principle  31  and u has the same argument with e". Let  and the  n  complex roots of g (z) be Zj'  Thus  zz • .••• z".  1=lc,,-ul =llc"I-lull =~=1 1Co 1 1Co 1 1Co 1 . By the mean value principle. there are a k C1 ,s;;; k ,s;;; n) such that 1Zk" I,s;;; ;;1 ZIZZ ••. Z" 1 = 1. Setzo =Zk then 1Zo 1,s;;;1 andg(zo) = f(zo) -u =0, i.e. 1f(zo) 1=1 u 1=1 Co 1+1 c" I. This completes the IZlzz"'Z  "  0  0  tl '  proof.  Exercise 2  1 In a group of 17 scientists each scientist sends letters to the others. In their letters only three topics are involved and each couple of scientists makes reference to only one topic. Show that there exists a group of three scientists which send each other letters on the same topic. (6 th IMO) 2  Is it possible to choose  4; (2) 5 distinct positive integers  (1)  such that the sum of any three numbers of them is a prime? 3  Given 7 points in  ~ABC.  no three of which are collinear.  Prove that there exists 3 points of these points which determine a triangle with the area less than or equal to 4  Let S  =  !S  6.4BC.  {I. 2, ... , 2009}. Find the largest positive integer n  such that there is an n-elements subset A of S with the following property: the sum of any two numbers in A is not divisible by their difference. S Let M be the subset of S  =  {1, 2, ... , 2000} such that the  differente of any two numbers of M is neither 5 nor 8. How many elements of M at most are there? 6  Suppose that each of 7 boys has 3 brothers among the  32  Combinatorial Problems in Mathematical Competitions  remaining 6 boys. Prove that the 7 boys are all brothers. Suppose 10 persons buy 30 books at a book-shop satisfying the following conditions: 7  ( 1) Each of them buys 3 books,  Among the books which were bought by any two of them,  (2)  there are at least one is same. Suppose the number of purchasers who bought some book is largest. Determine what that smallest value of the largest number is? (8 th CMO) 8  Every point in a plane is colored red or blue. Prove that  (1)  For any positive real number a there exists a triangle with the  sides of lengths a , (or blue). (2)  13a,  2a such that its 3 vertices all are colored red  There exist two similar triangles such that 3 vertices of each of  two triangles are colored in the same color. (The question (2) is a question of China Mathematical Competition in 1995) Suppose a convex polyhedron has 6 vertices and 12 edges. Prove that each facet is a triangle. 9  Let the set S be a set with finite number of point in the plane. If the distances between any two points in S is determined, 10  then the set  S  is called stable. Let M" be a set of n ( ~ 4) points in the  plane and no three points of M" be collinear. Suppose that the number of pairs of points having the determined distances inM" is ~  n(n - 3)  +  4. Show that M" is stable. (China Shanghai Mathematical Competition  in 1999)  Let j(x) j(x) =  Then j  C1  =  ~ (n )Xk k~O  k  (x)  function j  = (n)  0  By applying the binomial theorem, we gain  + (n)x + (n )X2 + ... + ( ~ 1  2  n  corresponds to the sequence { (~), 0 (1  (x )  sequence {  + x)".  + x)"  1  )x"-t + (nn )x'"  ~ k ~ n }.  Thus the  is called the generating function of the  G) }.  In general, for the finite sequence ao, aI' a2' ... , a", its generating function is defined to be the following polynomial: j(x)  " ~akxk =ao+atx+a2x2+·"+a"x".  =  k~O  For the infinite sequence ao, aj' a2' ... , a", ... , its generating function is defined to be the following formal power series: =  j(x)  =  ~a"x"  =  all +atx +a2x2  + ... +a"x" + ....  1I=()  =  Letjex)  =  ~a"x'"  =  g(x)  =  ~b"x" be two formal power series, we  define (l)j(x) =g(x) if and only ifa" =b,,(n =0, 1, 2, ... ),  34  Combinatorial Problems in Mathematical Competitions =  (2)  f(x) ±g(x)  =  L: (a"  ±b,,)x",  1!=0  =  (3) cf(x)  L: (ca,,)x"  =  (c is a constant),  11=0 00  '"  (4) f(x)g(x)  L-Jcnx, "  where c"  "  ~ akb,,-k' n  =  0, 1,  k~O  2, ....  When we solve the problems using the generating functions, besides the binomial theorem, we also need the following formulas:  I  (The summation formula of the infinite geometric series with the common ratio q satisfying - 1 < q < 1) Formula  _1_ 1 -x  =  :Sx" ,,~(),  Formula ]I  =  1 +x  + x 2 + ... + x" + ...  (-1  <  x  <  1).  Let k be a positive integer, then =:s(k+n-1)X" ,,~o k-1 =  1  +(  k )x + (k + 1 )X2 + ...  k-1  k-l  + (n +k -l)x" k -1  + ...  (-l<x<1).  the derivative of the formula I at x and divided by 1) ! , we get the formula II .  With the (k -  (k - 1)  Example!  Letao =-1, al =1, a" =2a,,-l +3a,,-2+3"(n  ~2).  Find a". Solution  Then  Letf(x) =ao +alx +a2x2 - 2xf(x)  =-  + ... +a"x" +''',  2aox - 2alX2 - .. , - 2a,,-lx" -"',  -3x 2f(x) =-3aox2 - ... -3a,,-2 x " - ....  Adding the above three equations and applyingao =-1, al = 1, a"  The Generating Functions 2a,,-1  + 3a,,-2 + 3"  (n ~  35  2), we have  (1-2x -3x 2 )j(x) =-1 +3x +3 2 x  2  + ...  +3"x"  + ...  =_1+~=6x-1, 1 -3x 1 - 3x  j(x)  =~+  6x-1  (1  + x)( 1 -  3x ) 2  (1 - 3x ) 2  Multiplying both sides of  CD by 1 + x and setting x  Multiplying both sides of  CD by (1  B  Multiplying both sides of  o= =  - 3X)2  -11  6x 1 +x  =  CD by  .r~t  =  =  ;  ,  we obtain  ~  x and setting x  x(6x -1) (1 +x)(1 -3X)2  + (1  1, we get  4'  lim  lim (Ax 1 +x  1 - 3x .  = -  and setting x  .r-+oo  .r_+00  +_C_  B  +x  1  Bx  - 3x)  2  -+  00,  we obtain  + ~) 1 - 3x  1  =A -3C, HenceC  =  3A 7  j(x)  16(1 +x) 00  +  =_2 ~(-l)"x" 16 ,,~n =  3  4(1 -3X)2 00  +~ ~(n 4 n~n  21 16(1 -3x)  +1 1  ~[(4n -3) ·3,,+1 -7(-1)"J " 16 x .  ~ 11=0  Therefore we yield a"  =  00  )(3x)" _21 ~(3x)" 16 ,,~()  116 [(4n -3)·3,,+1 -7(-1)"J.  36  Combinatorial Problems in Mathematical Competitions  Example 2  Show that for all positive integers n, we have  i= (2n2z+ 1) (2,iz )2  (4n + 2). 2n + 1  =  2,,-2i+1  i~()  Proof  + x )-1,,+2  Firstly, in the equality C1  coefficient of  is equal to  X 2,,+1  (4n + 2) . 211 + 1  (4n + 2 )Xk, the  ~  -1,,+2  =  k~()  k  On the other hand, in  the equality  the coefficient of  i= (2112l~ 1) (2,i )2 i~()  " is equal to ~  X 2,,+1  ,~O  2,,-2i+1  =  z  Example 3  Proof  ..  Show that  [('~/2\ _  X,,-l  +1) , 2  1)k  + x)  other hand, in the equality  =  1)  ,  •  Hence  (2n - ~k - 1)  ,,+1  ,,+1  (2i) 1  C:  . equal to (n+1) n-1 (n+1) 2  IS  2,,+1-2i  2l  (4n + 2). 2n + 1  Firstly, in the equality C1  coefflcient of  (211  =  ~ k~O  =  (11 + 1) Xk,  the  k  21 n(n +1).  On the  37  The Generating Functions  Hence  How many distinct ways are there to exchange n  Example 4  Yuan for 1 and 2 Yuan? Suppose that there are a" distinct ways, then a"  Solution  ~ 1 (where t 1 ,  =  are nonnegative integers) and the generating  t2  function of a" is OD  j(x)  OD  ~a"x"  =  =  n=()  ~ J/=()  ~ 1) x"  ( t  1 +2t 2 =n  =  OD  =  = ~ ~ XII +212 = (~Xll) ( ~ X212 )  1 1 1 l-x"1-x 2 = (1+x)(1-x)2  =  A  (1 -  we get A  +B + C  X)2  +~+~ 1 - x 1 + x·  1. Hence B  =  =  CD  1- A - C  =  1- ~ - ~ 2 4  1  4·  Therefore we have OD  j(x)  =  =~~C 00  11=0  =  1  ~a"x"  20 +1 1  _X)2  + 4(1  1 -x)  + 4(1  =  =  11=0  11=0  1 +x)  )x"+!~x"+!~(-l)"x"  ! ~[2n +3 + ! + + (- 1)"],  (-l)"]x".  7l=()  It follows that a"  =  [271  3  i. e. there are  !  [2n  +3 +  ( - 1)"] distinct ways. Example SCExample 8 in Chapter 1)  How many 3-digit integers  38  Combinatorial Problems in Mathematical Competitions  are there such that the sum of digits of each integer is equal to 11 ? Solution We denote the hundred digit, ten digit and unit digit by the  X I ' X2' X3 XI  respectively, then  +X2 + X3 =  11 C1  :(;; XI  :(;; 9,0  :(;;X2  :(;; 9, 0  :(;;X3  :(;; 9).  CD  Thus the required number of 3-digit integers equals the number of integer solutions of the linear equation CD. But the number S of integer solutions of the linear equation CD equals the coefficient of Xli of the following function: !(x) = (x +X2 =  C1  +X  + ...  + ...  + x~)C1 +X  + X 9 )3 -  C1  + ...  +X  +X~)2  + ...  + X 9 )2  C1 - X III )2 C1 _X)2  the required number of 3-digit integers is 61.  Exercise 3  1 Find the general term a" of the following sequences of numbers using the generating functions: (1) au = 2, al = 5, a,,+2 = 3a,,+1 - 2a,,(n =  0,1, 2, ... );  (2)ao = 4, al = 3, a,,+2 = a,,+ 1 +6a" - 12 (n = 1,2, ... ).  2  Prove that the following identities:  39  The Generating Functions  [ ,, / 2J  (3) ~ ( _ 1) k k- O  (n + 1 ) (2n - 2k ) k  =  n  + 1;  n  (i = j ) ,  Ci  *- j).  For a sequence {I,,}, if there is a positive integer k and an equation that connects I,,+k with its preceding k terms I,,+k-l CP(I,,+k' I,,+k-l' ••• , I,,)  =  , I,,+k-2' ••• , I" :  CD  0,  Then the sequence {I,,} is called a k order recurrence sequence of numbers and the equation Solving I  ,,+k  CD  from the relation X  ll  +k  =  is called the recurrence relation of {I,,}.  CD,  we obtain  cp(X ll +k-1' X n +k-2' ••• ,  x  TI ) .  The equation CZ) is also called the recurrence relation of {I,,}. The firstk terms of {I,,}:  are called the initial values of {I,,}. Obviously, the sequence {I,,} is determined uniquely by the recurrence relation CZ) and the initial values  ®. Suppose that the recurrence sequence {I,,} is determined uniquely by the initial values I,,+k  =  PII,,+k-1  constants and  Pk  ®  + P2 I  and the following recurrence relation: ,,+k-2  + ... + PkI" + q  (PI'  P2'  ••• ,  Pk  are  "* 0),  then the recurrence sequence {I,,}  IS  called the linear recurrence  sequence of numbers (with constant coefficients) of order k. When  Recurrence Sequence of Numbers  41  q - 0, the recurrence sequence {x,,} of numbers called homogeneous,  otherwise it is non-homogeneous.  4. 2  The Methods of Finding Solutions  (1) The method of characteristic roots  Consider the linear  homogeneous recurrence relation (with constant coefficients) of second-order: X,,+2 = PX,,+1 + qx" (71 =  0, 1, 2, ... ; p, q are the constants and q  If the geometric sequence { r"} (r  relation  CD,  we have r"+2  * 0).  * 0) is a solution of the recurrence  = pr,,+1 +qr" ,  i. e.  r  is a root of the following  quadratic equation: r2  The quadratic equation  CD  =  pr  + q.  is called the characteristic equation of the  sequence {x,,} and the roots of the equation (2) are called the characteristic roots of the sequence {x,,}. Conversely, if r is a root of the equation (2), then the geometric sequence {r"} is a solution of  CD.  If the two roots r 1 and r2 of equation (2) are distinct, then {r ;l}  and {r2} are the solutions of {C I r~  +C  2  CD  and for any constants C 1 and C 2 ,  rn also is the solution of CD.  If the initial values x  1  =  a, x 2  =  bare given, the values of C 1 and  C 2 are determined uniquely by the following system of equations:  CD  with the  1p is a double root of equation (2), we get pr +  2q  =  initial values XI = If r  =  + C 2r2  of  Therefore we get the unique solution x" a, X2  =  C 1rll  = b. 0 from  Combinatorial Problems in Mathematical Competitions  42  the following system of equations:  O.  =  Thus nr" - pCn - 1)r,,-l - qCn - 2)r,, - 2 =  nr,, - 2Cr 2 - pr - q) +r,,- 2Cpr + 2q)  =  O.  So {nr" } is a solution of  CD  and for any constants eland C 2' {C 1 r" +  C 2 nr" } is also the solution of CD. Since the values of eland C 2 can be determined uniquely by the initial values XI = a, X2 = b. Therefore, we get the unique solution x" values Xl = a, X2 = b.  =  C 1 r'{  + C 2 nr"  of  CD  with the initial  Example 1 CThe Fibonacci Sequence of numbers)  The rabbits  mature in a month after birth. Each month the female of a mature pair gives birth to a new pair of rabbits with opposite sexes. At first, there is a pair of newly born rabbits with opposite sexes and how many pairs of rabbits are there at the end of the nth month? Solution  Suppose that at the end of the nth month there are a"  pair of mature rabbits and b" pair of newly born rabbits. If at the nth month there are F" pair of rabbits, thenF" = a" +b". Buta" =a,,- l + b,,-l = F,,- l and b" = a,, -l = F,, -2' Thus we have F"  a"  =  + b"  =  F,,- l  + F,, -2.  CD  Obviously FII = 1 CSince we begin with only one pair of newly born rabbits.) and F 1 = 1 CSince at the end of first month, we only have  CD is r2 1 - 15 Th us --2-'  one pair of mature rabbits. ). The characteristic equation of r  .. + 1. Th e c h aractenstic  F  = "  C  roots are rl  1  =  -1 +-2-15 ' r2  (1 +15)" +c 2  Since F o = 1, Fl = 1, we get  2  (1 - 15)" 2  =  =  43  Recurrence Sequence of Numbers  1 -v's 2v's .  Solving the system of equations, we get C 1 Hence F"  =  ),,+1 _ ( 1 -v's )"+1] 2'  _1 [( 1 +v's v's 2  n  =  0, 1, 2, ...  This sequence (2) is called the Fibonacci sequence of  Remark  numbers and its first 10 terms are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...  The problems concerning Fibonacci sequence of numbers often appear in mathematical competitions. How many n-digit numbers with no pair of adjacent  Example 2  1 's are there which consist of 1, 2 and 3?  Assume that the number of required n-digit numbers is  Solution  a". Obviously, a1 = 3, a2 = 3 2  -  1 = 8. We classify the n-digit  numbers satisfying the conditions into two types: the number of n-digit numbers with the leading digit 1 and the second digit 2 or 3 is 2a,,-2 and the number of n-digit numbers with the leading digit 2 or 3 is 2a,,-1. By the addition principle, we get a"  2a,,-1  =  The characteristic equation of roots are r1  =  1 +/3, r2  =  + 2a,,-2 en CD is  r2  =  ~  2r  3).  + 2.  CD The characteristic  1 -/3. Thus  2a . Let ao satis f ya2 = 2a1 +2ao' l.e. a() = a2-2 1 = 1. W·h It a() = 1, a1  =  3, we have  Combinatorial Problems in Mathematical Competitions  44  Solving the above system of equations, we get  CI  2 + 13 213 2 - 13 213  =  C2 Therefore, a n  1M [ C1  =  +13) 2 4  C1  C1  - 13 )2 413  +13) '1+2 - C1 -13 )'1+2].  4'1 3 (2)  The Method of Substitution  In fact, it may be very difficult to find the solution of some recurrence relations . We will illustrate several examples about the method of substitution to obtaining the solution of some recurrence relations. Example3  1.  +  (an  ifal  ,  1, a n  =  =  ;a n- I + n 2 -15 ( n  ~ 2).  Set undetermined constant a, b, c such that  Solution an  Finda n  2  + bn  + c)  =  [an-I  ;  + (a(n  _1)2 +b(n -1)  +c)],  e.  + (- ~a 3  Comparing it with a n  )n 2 +  =  (-  2 3 an-1  -±-a - ~b)n 33  +n  2 -  + ( ~a  - ~b - ~ c ) 333'  15, we get  = - 3, 4 - -1 b - -a 3 3  =  0,  2 2 1 -a - -b - - c = -15. 333  =  12,  =  15.  Thus an + ( - 3n 2 + 12n + 15)  =  ;  [a n- I +( - 3(n _ 1) 2 + 12(n - 1) + 15) ].  Recurrence Sequence of Numbers  Setting b"  =  a" - 3n 2  + 12n + 15,  45  we have  2 b" = 3b "- 1, b 1 = a 1 - 3  + 12 + 15  = 25.  Thus {b,,} is a geometric sequence with the leading term a 1 the common ratio q = a"  Remark  p  2 Hence we have b" = 25 (2)"-1 3' 3 . Therefore 2 ) ,, - 1  =  25 and  =  25 ( 3  ,  + 3n -  - 12n - 15.  For the recurrence relation a"  * 0 is a constant and f C  pa,, - l  =  + fCn),  Cn  *  ~ 2,  is a polynomial of degree k) . If P 1, by applying the method of undetermined coefficient, we can determine n)  the polynomial g Cn) of degree k such that a " +gCn) =p[a,, - l + gCn - 1) ].  Settingb" = a" +g(n), we getb" = pb,,-l' thus  It follows that  + fCn),  If P = 1, i . e. a " = a,, - l  using the method of iteration, we  could obtain to get a"  =  =  + fen) a ,,-2 + fen -1) + fCn)  a,,-l  =a 1 + f(2) + f(3) + "' + fCn)  or n  a" = a1  n  + ~Cak k=2  Solution  Since a" +la,,  - ak-]) =a1  + ~fCk). k =2  =  4(a,, +1 - 1), then a,, +l  4 4 - a,,'  Combinatorial Problems in Mathematical Competitions  46  al/+l  2(a ll - 2) 4 -all '  - 2 = -4- - 2 4 -all  Thus all  Hence  {~2} an  4 -all 2(a ll - 2)  -2  1 -2  1 2'  -----  all  is a arithmetical sequence with the leading term  - 1 and the common difference d  at  ~2  ~, Thus we get  = -  -1) n+1 a ll _2=-1+(n-n ( 2 =--2-=>a ll =2  0  n n + 1,  Therefore  In this example, 2 is the double roots of the equation  Remark x  2  a ll +l  1),  = 4(x =  More generally, for the fractional recurrence equation  aa II + b h . d aa 1 + b h f +d' w erec #0, a -bc #0, al # +d' T e roots 0 call cal  equation x  =  ax ++db are called the fixed points of this sequence {all} If  ex  the sequence {all} has only one fixed point p (i, e, p is a double root of the equationx(cx +d) = ax +b), Then 1 all -  1  P  all-I -  2c  P +a +d'  If the sequence {a II} has two distinct fixed p and q, then a ll +l - p a ll +l -q  a - pc a -qc  =---0  a ll -l - P all-I-q  Example 5  Prove that n  + 21 < a 1 + a 2 + ... + a II < n + 2.  47  Recurrence Sequence of Numbers  Proof  Witha,,+1 =a"C2-a,,+I),wegeta,,+1  =  2a+"l' Solving the a"  , x = x 2x ' two f'Ixe d pomts ' equatlOn + 1 ' we 0 btam XI = 0, 2a" d =-+1 an a,,+1 all  a n +l  X 2  = 1.  W'It h  1 =-+12a" 1 =-+1' a" - 1 a,,+1 - 1 1 . we get =-2 a 71 a n +l  -  all  a,,-l, e, {a,,-l}, , sequence WIt 'hI ea d'mg term-al-l - - IS a geometnc an al  - - , 1. all  and common ratio ; , Hence  S'  mce  2 21 < a 1 < 3' 21 <  1  1  ~  -  <  1  1,  1 1 + 2" <;- <  1  1 + 2,,-1  '  "  we get  ~ +~ + .. , +~ < (1 +~)+ (1 +~)+ .. , + (1 +~)  al  a2  1  a"  n  =  2  1 2,,-1  +2 -  <  n  2  +2  and  ~ +~ + .. , +~ > (1 +~)+ (1 + \)+ .. , + (1 +~)  al  a2  2  a"  =n  2  2  1 11 +1->n +1-- =n +-2' 2" 2  This completes the proof, Example 6 (n  ~1),  Solution  /1  Find a", if a 1 = 1, a ,,+1 = 116 C1 + 4a" + / 1 + 24a" )  + 24a"  For eliminating the radical, natuarally, we set b"  , i, e, a"  =  =  214 Cb;, - D, Substituting this to the original  Combinatorial Problems in Mathematical Competitions  48  recurrence relation, we obtain  I.e. (2b,,+!)2  =  Cb" +3)2, Sinceb" >0, so  CD Thus {b" - 3} is a geometric sequence with the leading term b1  -  and the common ratio q  3  j 1 + 24a 1  =  =  3  -  2  =  Hence  ;.  1 ) ,,-I = 22-" =>b b - 3 = 2 X ( -2 II  11  Therefore  Remark  In the equation  CD,  3 is the root of equation x  3) and it is also called the fixed point of the function f 3),  =  (x) =  (x  +  ; (x  +  ;  Generally, the recurrence relation of degree 1 with the constant  coefficients: b,,+! reduced to  pb"  =  b,,+l  +q  (p,  +-qp-1  q are the constants and p  =  P (b" +-q-), p-l  where - - q - is the root of the equation x  p  -1  Example 7  * 1 ) can be  =  px  + q,  The sequences {a,,}, {b,,} are defined as follows: au =  1} ,  a,,+1  =  1} '\h - J1 -  a; ,  bo = 1, b,,+l = b1 eJb; +1 -1), n = 0,1,2, .... "  49  Recurrence Sequence of Numbers  Prove that the following inequality holds:  for each of n = 0, 1, 2, .... Applying the mathematical induction, we easily get 0  Proof a"  <  >  1, b"  O. Let a" = sin A"  (0 < A" <  ; ,  / 1-  sinA,,+l = /} J 1 - '\11 - sin2A" = /}  So A,,+l = 1 1\"  ~A" (n _ -  1 1\"  0) , then 2,.  cosA" = sin A  ~. Thus  ;?: 0) and Au = arcsin /}  IT => . 4IT ( _21 )" -_ 2,,+2 a" = sin  n ;?:  .  IT  = sin 2,, +2  (  Similarly, letb" = tano",wecanobtainb" =ta n2'~2 Since sin x  <  x  < tan x a"  (0 < x  <  >: 0)  n :;o-  •  (n ;?: O).  < ; ) , we get  ------ 2,, +2 a" < < 2,,IT+2 < b,,----'"  ~ H  <  2"+2b,,.  (3) The Mathematical Induction  The basic ideas to solve the problem about the recurrence relation of {x,,} by applying the mathematical induction are that (1) Use the recurrence relation and the initial values to compute the first several terms:  Xl' X2' ••• , Xk  and explore the general law of  { x,, } .  (2) Guess the expression of the general term of { x,, } or some properties of { x,, }.  0) Prove that the conjecture in (2) is true with the mathematical induction. Example 8  Let  a"  denote the number of the positive integers N,  whose sum of digits is n and digits are 1, 3 or 4. Prove that for any n = 1, 2, 3, .. . , a2" is a perfect square.  (China Mathematical  Combinatorial Problems in Mathematical Competitions  50  Competition in 1991) Proof Among a" positive integers satisfying the conditions, the number of numbers with leading digit 1, 3 or 4 are a,, - I ' a,, -3 or a ,,-4 respectively, then a"  =  a,, - I  + a ,,-3 + a,,-4 en  CD  ~ 5)  Obviously a I = 1, a2 = 1, a 3 = 2, a~ = 4. Combining this with can evaluate the first several terms as follows:  CD ,  we  11  1  2  3  4  5  6  7  8  9  10  11  12  . ..  au  1  1  2  4  6  9  15  25  40  64  104  169  . ..  11  1X2  22  2 X3  Y  3X5  52  5 X8  law  82 8X 13 1Y  From the above table of numbers we guess that the following conclusion holds: Let {I,, } be the Fibonacci sequence, i. e. 1 1 = 1, 12 = 2, 1,,+2 = 1,,+ I + I" en ~ 1). Then the following conclusion holds:  Using the mathematical induction, we prove that for any positive integer n the above conclusion @ is valid. For n = 1 and n = 2, we have  and a~ = 22 = IL as = 6 = 2 X 3 = I d 3'  i. e. for n  =  1 and n  =  2 the formula @ is valid. We suppose that for + 1, using  n = k - 1 and n = k the formula @ is valid, then for n = k  the recurrence relation CD , the inductive hypothesis and the definition of the Fibonacci sequence, we get a2(k+ l)  = = =  + a2k-l + a2k -2 = Iklk +l + Ik -l Ik + 1~ - 1 Idk+l + 1k-1 elk-1 + Ik) = Idk+l + 1k-1 Ik+l Ik+ l Uk + 1 k-1 ) = 1~+1 ,  a2k+l  51  Recurrence Sequence of Numbers  a2(k+l l-l- 1  =  a2(k +ll  =  f~+1  =  1.  e. for  n  = k  square for n  =  Remark  is valid. In fact, from  + f~ + fk-lfk f~ + 1 + fdk+l  + a2k + a2k - 1 = f~+1  + fk (fk + fk - I) = fk+l Cfk+l + fk) = fk+l fk +2 '  + 1 our conjecture (2)  is true. There a 211 =  f;  is a perfect  1, 2, 3, .... This completes proof. In this example, we also prove that  CD,  we can deduce the following recurrence relation:  Using the mathematical induction and the recurrence relation @ , we could prove that the conjecture Q) is true. We leave the detail of the proof to the reader. Example 9 Let the sequences {all}' {b ll } satisfy the following conditions: a ll +l  =  7a ll + 6b ll -3,  =  Sail  CD  and b ll +1  n  2,  =  0, 1, 2, .... Prove that a  II  + 7b ll  - 4,  is a perfect square for n  0, 1,  (China Mathematical Competition in 20(0) Proof  I  With  CD  we get  b ll  =  1 6(a ll +1 -7a ll  + 3).  Substituting Q) to (2) and rearranging we have a ll +2  14a ll +l - all - 6.  =  By direct computation, we get all = 1 = 12 , al = 7all  + 6b o -  3 = 4 = 22 , a2 = 14a 1 - ao - 6 = 49 = 72 ,  a3 = 14a 2 - al -6 = 676 = 262 , a4 = 14a 3 - a2 -6 = 9409 = 972 ,  ••••  52  Combinatorial Problems in Mathematical Competitions  and the sequence of numbers 1, 2, 7, 26, 97, ... satisfies the recurrence relation: do d,,+2  =  1, d I  =  2,  =  4d ,,+1 -d" Cn  =  0,1, 2, ... ).  Hence we guess that the formula a" = d;, is valid, where {d ,,} satisfies the recurrence relation ® . With the mathematical induction, we prove that this conjecture is true. For n =  °and  n = 1, all = 1 = d~, al = 4 =  df. Assume that for  n = k - 1 and n = k , we have that aH = d~-I , ak = d~. Then for n =  k  + 1,  we get a k+1  =  14ak - ak-I - 6  14d~ - d ~ -1 -  =  6  = (4d k -d k_I )2 - 2(d~ + d~-I - 4d k d k - 1 + 3) = d ~ +1 -2(d~ + d~-1 -4d kd k - 1 + 3).  But d~ + d~-I - 4dkdk-l  +3  =  d k C4d k - 1 - dk-2) + d~ - 1 - 4d k d k- 1 +3  = d~-1 -d k-2 C4d k- 1 -d k- 2 ) +3 = d~- I + d~ - 2 -4dk-ldk-2 + 3  =  df  = 22  + d6 -4d 1d u +3  + 12  - 4 X 1X2  +3  = 0.  Thus ak+1 = d ~+I . Therefore for each of n = 0, 1, 2, ... , a" = d;, is a perfect square. Remark The recurrence relation of undetermined coefficients.  ® is also deduced by the method  In fact, setting d ,,+2 = pd ,,+1 + qd" and combining this with d o d 1 = 2, d 2 = 7, d 3 = 26, we get q {P=4, { 2P + =7, 7 P + 2q = 26. ::::;. q = - 1.  Therefored"+2 =4d,,+1 - d"Cn = 0, 1, 2, ... ). Proof 1I  Let x"  =  a" -  ~  (  ~  is the root of the equation x  1,  53  Recurrence Sequence of Numbers  1 2'  14x -x -6 ) ,thenxo = X,,+2  =  Xl  =  27  and from @ we get  l4xn+l - x" (n ):: (J).  Using the method of the characteristic roots, we easily get x"  ~ C7 + 4)3)" + ~ C7 - 4)3)"  =  4  4  ! (2 +)3)2" + ! (2 _)3)2".  =  Thus a" =  Let ; (2 +)3)"  =  ~C7 +4)3)" +~C7 -4)3)" +~ 4 4 2  =  ~(2 +)3)2" + ~(2 _)3)2" + ~  =  [  4 4 2  ~  (2 +)3)" +  A~  =  Example 10  r.  A" + E,,)3 (An' E" are the positive integers), then  ~ (2 -)3)" Therefore a"  ~ (2 -)3)"  =  An - En )3.  is a perfect square.  Set N  =  (2 +)3)211114. Find the first digit at the left of  the decimal point and the first digit at the right of the decimal point of N. Solution  Set  The characteristic equation is  [r - (5 +216)J • [r - (5 -216)J i.e. r2 -lOr  +1 =  =  0,  O. Thus the sequence of numbers {x,,} satisfies the  following recurrence relation: X,,+2  =  10x,,+1 - x" (n ):: D.  Combinatorial Problems in Mathematical Competitions  54  Thus Xl = (5 +2/6) +(5 -2/6) = 10, x, = (5 + 2/6)2 + (5 - 2/6)2 = 98  are two positive integers and Xl < positive integers and X  k-1  <  X k ,  X2.  Suppose that  and with  CD  Xk-1 , Xk  are two  we deduce that for each of  n = 1,2, ... , x" is a positive integer andx,,-l <x". Hence X"  = 10x,,-1 - (10x,,-3 -  X,,--I  -X,,--I)  = 10(x,,-1  -X,,-3) +x,,--I  (moci10)  Especially we obtain Xlli02 -  X2  -  8 (mod10), i. e. the unit digit of  X1II112 is 8. Since 0 < 5 - 2/6 < O. 2, thus 0< (5 - 2/6)10112 < 0. 21002 = 0. 008 33-1 < 0.01 33-1 = 0.00···01 ~  668 zeros  1.  e. X1002 =N+(5-2/6)ll}()2 =N+O.OO···O* * * ... ~  669 zeros  Since the unit digit of  X WII2  is 8, therefore the first digit at the left of  the decimal point of N is 7 and the first digit at the right of the decimal point of N is 9.  Exercise 4 1 Let the sequence ai' a2' ... , a", ... of positive integers satisfy the following conditions: (1) ja"a,,-2 -  ja,,-la,,-2 = 2a,,-1; (2) an = al = 1.  Find a". (China Mathematical Competition in 1993) 2  Determine real number ao such that the sequence {a,,} which is  determined by the recurrence relation an+l =- 3a" + 2" ... ) is increasing.  (n  = 0, 1, 2,  Recurrence Sequence of Numbers  3 a 2 + ...  55  Let the sequence a t . a 2' ., .• a " • ... satisfy at  + a"  =  ;.  at +  n 2a " • find a" (7th Canadian Mathematical Olympiad in  =  1985) .  4  Letao = 0. a 1 = 1. a" = 2a ,,- t + a ,,-2 Cn  ~ 2).  Prove that 2k la" if  and only if 2k In. (Note:  a  I b express that  b  IS  divisible by  a).  (The Problem  Prepared for 29 IMO) th  5  How many numbers of ways are there such that a 2 x n  chessboard can be perfect covered by n 1 and without overlaps?  X  2 rectangles without gaps  6  Suppose a sphere is divided into a " regions by n big circles on this sphere. no three of which are concurrent. Find a" . 7 How many n-digit numbers can be formed by the digits 1. 2. 3. 4 such that the number of the digit 1 is even? 8  Four men A. B. C and D pass a ball to each other satisfying  the following requirement: every man who accepts the ball pass this ball to anyone of other three men at once. Suppose that A begin to pass the ball Cas first time passing ball). In how many distinct ways can the ball return to A after 10 passes of the ball. 9 Prove that for any nonnegative integer n. the number [ ( 1  +  j3 ) 2"+l J is divisible by 2,,+1 .  10  Prove that for any nonnegative integer n. the number  " (2n +1) 2 2: k ~() 2k + 1  11  3k  is not divisible by 35.  There is a sequence { a ,,} satisfying a o  7a ,,+J45a ~- 3 6 EN 2 •n .  Prove that: C1) For each n E N. a " is a positive integer. (2) For each n E N. a"a,,+l - 1 is a perfect square . (China Mathematical Competition in 2005 )  1. a,,+ l  When many situations are set m an investigative problem, we usually discuss each situations individually and find the solution. Summing and synthesizing these conclusions of the situations, we will obtain the solution of the original problem. That is the idea and method of classification. When we solve some problems applying the idea and method of classification, the following rules must be followed: Each situation in the original problem must be contained in some class without omissions. (1)  (2)  Any two classes are disjoint and do not have overlaps.  The classification must follow the same criterion. (4) The key to choose the classifying criterion is that the problem appearing in each situation could be solved more easily than the original problem. (3)  How many 3-digit numbers can be formed from the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 such that the sum of its digits is even and greater than or equal to 10? Example 1  Solution  The 3-digite numbers whose sum of the digits is an even  only have the two following classes: each digit is even or one is even and the other two are odd. When each digit is an even, the number of the 3-digit numbers - Pi = 48.  (1)  is  P~  (2) When one digit is an even and the other two are odds, the  57  Classification and Method of Fractional Steps  number of 3-digit numbers is  But among above the 280 numbers, there are following 42 numbers with the sum of its digits less than 10: 204,240,402,420; 206, 260, 602, 620; 103, 130,301,310; 105, 150,501,510; 107, 170,701,710; 305, 350, 503, 530; 123,132,213,231,312,321; 125, 152,215,251, 512, 521; 134, 143,314,341, 413, 431. Therefore the number of 3-digit numbers satisfying the conditions equals 48  + 280 -  Example 2  42 = 286. Suppose a figure consists of 271  (n ~ 2)  points (no four  points of are coplanar) and there are n 2 + 1 line segments connecting these points. Prove that there exist 71 triangles in this figure. Proof  We shall prove the statement by induction on n. For the  basic case n = 2, suppose the 4 points are A, B, C, D and there are 22  + 1 = 5 line segments connecting these vertices. Thus only (:) - 5 = 1 pair of these points is not connected by a  line segment. Without loss of generality, suppose that there is no line segment connecting the points C and D. In this case, there exist two triangles: 6.ABC and 6.ABD. Thus the basic case is proved.  + + 1)2 +  Assume that the statement is true when n = k ~ 2. When n = k 1, let a space figure G consist of 2k  + 2 points and there are (k  1 line segments connecting these points. Firstly, we prove that there exists at least one triangle. Let the two given points A and B be connected by a line segment and the number of line segments connecting the points A (or B) and 2k other points is a (or b). (1) If a  +b  ~ 2k  + 1,  then there are a point C (C differ from A  and B) which is connected with A and B by the line segments. Thus there exists a triangle ABC.  Combinatorial Problems in Mathematical Competitions  58  (2) If a  + b < 2k,  by deleting the points A and B and all line  segments meeting both A and B, then among residual figure, there are 2k points and at least (k  + 1)2 + 1 -  2k - 1  =  +1  k2  line segments connecting these points. By the induction hypothesis, there exist k triangles. Let LiABC be one of above triangles and n A. , n Born c denote the number of line segments connecting the points A, B or C and other 2k - 1 points respectively.  Case I : If n A + n B + n c  ~  3k - 1, there are at least k triangles  with one side of three sides AB, BC or CA respectively. Adding the triangle ABC, we have at least k  + 1 triangles.  Case II: IfnA +nB +nc <3k -2, i.e.  then among three numbers n A  + n B'  nB  least one is not exceeding [6k 3- 4] generality, assume n A.  + n < 2k B  =  + n c and n c + n A. , 2k -  there is at  2. Without loss of  - 2. After deleting two points A and  B and all line segments meeting both A and B, then among residual figure, there are 2k points and at least (k + 1)2 + 1 - (2k - 2) - 3 =  +1  line segments connecting these points. By the induction hypothesis, there exist k triangles. Adding the triangle ABC, we have  k2  at least k  + 1 triangles.  Hence for n  =  k  + 1,  the conclusion is valid.  This completes the proof. Remark  In this example, we have two classifications and the first  classification and the second classification are independent (the criterions of two classifications are distinct).  In the following  example, our second classification is the subclasses of the first classification. Example 3  Suppose 4 couples are seated on a bench to watch a  movie such that any female is only adjacent to her husband or other female. How many different ways of seating are possible?  59  Classification and Method of Fractional Steps  (The Problem Prepared for Japan Mathematical Olympiad in 1995) Firstly, the number of ways of arranging 4 females is 4!. If there are the males between two females, then the number of Solution  the males is at least 2 (their husbands) . Similarly, if there are females between two males, then there are at least 2 females. If seats of several females are consecutive, then we consider these females as a group. Thus unordered grouping ways of the females have the following 5 classes: 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1. Since the isolated female must sit at two ends of the bench, the grouping way 1 + 1 + 1 + 1 does not satisfy the condition. (1) When the grouping way of females is 2  + 1 + 1,  the grouping  way of males has only one class: 2 + 2. In this case, the mode of seating has on the only one class (The letters F and M express the female and the male respectively) : CD FMMFFMMF The number of way of arranging all males is only 1. (2) When the grouping way of females is 2 + 2, the modes of seating have the 4 following classes: CZ) FFMMMMFF ® M F F M M M F F or F F M M M F F M ® M M F F M M F F or F F M M F F M M ® MFFMMFFM In the four classes above, the numbers of ways of arranging all males are 2!, 1, 1, and 1 respectively. The total ways is 2! + 1 x 2 + 1  x 2 +1  =  7.  (3) When the grouping way of females is 3  +  1, the modes of  seating have the 3 following classes: ® F F F M M M M F or F M M M M F F F (J) M F F F M M M F or F M M M F F F M ® M M F F F M M F or F M M F F F M M In the three classes above, the numbers of ways of arranging all males are 2!, 1, and 1 respectively. The total ways is 2 x (2! + 1 + 1) = 8. (4) When all of females are consecutive, the modes of seating  60  Combinatorial Problems in Mathematical Competitions  have the 3 following classes: ® F F F F M M M M or M M M M F F F F  ®  M F F F F M M M or M M M F F F F M  @MMFFFFMM  In the three classes above, the numbers of ways of arranging all males are 31 , 21, and 21 respectively. The total ways is 31 X 2 + 21 X 2 + 21 = 18. Summarizing what we have described above, we obtain that the total ways of arranging 4 couples is 41 X C1 + 7 + 8 + 18) = 24 X 34=816. Suppose that a group of n (n ~ 6) persons satisfies the following conditions: (1) each person sends his regards to at most n Example 4  [n i 2 ] persons by telephone;  (2) Among any three persons, there  are at least two persons sending their regards to each other by telephone. Prove that it is possible to divide these n persons into two disjoint sets such that any two persons in the same set send their regards to each other by telephone. Solution  We represent a person with a point in the plane, no  three points of which are collinear. If two persons send their regards to each other by telephone, then two corresponding points are connected by a red line segment, otherwise, connected by a blue line segment.  Thus we obtain a figure G satisfying the following  conditions: (1) There are at most  n - [n i 2]  red line segments  meeting every point in G. (2) Among any three points in G, there are at least two points which are connected by a red line segment. Thus original problem is reduced to prove that it is possible to divide the n points in G into two disjoint subsets such that any two points in the same subset are connected by a red line segment. Let S denote the set of n points in G. By the given condition ( 1) , there are at least  Classification and Method of Fractional Steps  n  -1- (n - [n i 2J)  =  [ ;  61  J  blue line segments meeting every point of 5. Suppose that the point A I and  [n 12J points  B  I ,  B  2 ,  ••• ,  B Cn I2]  are connected by the blue line  segments and the point B I and [n12J points A I ' A connected by the blue line segments . Let 51  =  {AI' A 2 ,  ••• ,  2 ,  ••• ,  A Cn/2]  are  A Cn!2]}  and  by the given condition (2), we know 51 in the same subset 5 i (i Case I : When n  =  =  n 52 =  0  and any two points  1, 2) are connected by a red line segment.  2k is even, then the set 5 is divided into two  disjoint subsets 5 I and 5 2 so that any two points in the same subset are connected by a red line segment. Thus the conclusion is valid. Case II : When n = 2k + 1 ~ 6 is odd, then k ~ 3. Since I 51 U 5 2 I = 2k, then there is a point C in 5 which does not belong to 5 1 U 52.  CD  If C and Bl are connected by a blue line segment, denote 5~  =  5 1 U {C } by the given condition (2), we know that any two points in  each of 5/ and 5 2 are connected by a red line segment and 5 5 2' 5'1  n 52  =  =  5 '1 U  0 . Thus the conclusion is valid.  @ If C and Al are connected by a blue line segment, with the  same reason in  CD ,  the conclusion is also valid.  Q) If C and each of A I and B I are connected by the red line  segments, with the given condition (1), there are at least [ ;  J  =  k  ~3  points and the point C are connected by the blue line segments and not all of these points belong to 5 I and not all of these points belong to 52. Without loss of generality, suppose that C and a point A i (2 ~ i ~ k) in 5 1 are connected by a blue line segment and C and the two points B/, B j (2  ~  t < j ~ k) in 5 2 are connected by two blue line segments. We  know at least [ ; ]  =  k points and the point Ai are connected by the  62  Combinatorial Problems in Mathematical Competitions  blue line segments and at least k  ~  1 of these points, except the point  C, belong to 52. But there are only k points B , , B j  .  ~  2 points in 52' except two  So A i and one of two points B , , B} must be connected  by a blue line segment. For convenience, we assume that the point Ai and the point B , is connected by a blue line segment. Thus any two of the three points C, Ai, B , are connected by a blue segment, which contradicts the given condition (2). This completes the proof.  The method of fractional steps is that the original complex and difficult problem is transformed into a group of correlative "small problems". Among these "small problems", the solutions of the posterior problems often depend on the solutions of the anterior problems. When the last problem is solved, we obtain the solution of the original problem . Example 5  Find the smallest positive integer n such that among  any n irrational numbers, there exist 3 irrational numbers such that the sum of any two of them is an irrational number, too. Solution  Obviously, for the 4 following irrational numbers:  ~J2, ~J3,  J2, J3 , any three of them contain two opposite numbers  such that the sum of them equals zero and zero is not an irrational number. Hence the smallest positive number n satisfying the condition is greater than or equal to 5. Next, we will prove that among any 5 irrational numbers, there are at least 3 numbers such that the sum of any two of them is an irrational number . For convenience, we represent 5 irrational numbers with 5 points r, y, z, u, v in the plane (The point and the corresponding irrational number are represented by the same letter) and not three of them are collinear. If the sum of two numbers is a rational number, the two corresponding points are connected by a red line segment, otherwise, by a blue line segment. Thus we obtain a  63  Classification and Method of Fractional Steps  figure G. and the original problem is reduced to prove that there exists a blue triangle in G. Firstly, we prove that there exists a monochromatic triangle in G. If among 4 line segment meeting some point there are at least 3 red (or  blue) line segments, then there must be a monochromatic triangle. Hence, without loss of generality, we could assume that there are exactly 2 red and 2 blue line segments meeting every points in G. And there are 5 red and 5 blue line segments in G . Since there are only two red line segments meeting every point in G, then every point is a vertex of a close broken line. But every close broken line has at least 3 line segments, hence 5 red line segments form a close broken line. Similarly, 5 blue line segments form a close broken line. For convenience, assume y  + z, x  IS  x yzuvx  z  + u,  u  + v,  v  =  2"[(x  + y)  - (y +z)  1  +x  is a red close broken line, thus  a rational number,  x  + y,  are all rational numbers . Hence  + (z  +u) - (u +v)  + (v  + x )]  which contradicts the given condition .  Consequently, there exists a monochromatic triangle. Secondly, we prove that there exists a blue triangle. Otherwise, there exists a red triangle. For convenience, assume that red triangle. Thus x x  =  + y,  y  + z,  z  +x  !':::,.xyz  is a  all are rational numbers, and  ~ [ ex + y) + (z + x)  - (y  + z) ]  is a rational number, which contradicts the given condition. So there exists a blue triangle. Assume that !':::,.xyz is a blue triangle, i. e. there exist three irrational numbers x, y, z such that the sum of any two of them is an irrational number. Summarizing what we have described above, we obtain that the smallest positive integer n is 5. Example 6 Suppose that there are 2,, -1 n-term sequences in which each term is 0 or 1. If for any three these sequences, there exists a positive integer p such that the p th terms of them all are 1. Show that  Combinatorial Problems in Mathematical Competitions  64  there exists an unique positive integer k such that the k th terms of these 2,, - 1 sequences are all 1. (32 nd Moscow Mathematical Olympiad in  1969) Proof  LetS = {X I X =  (XI' X 2 ' " , ' x,,), Xi  = Oor 1, i = 1,  2, ... , n } and So represent the set of 2,, - 1 n-term sequences satisfying  the given conditions. Thus S o is a proper subset of S. Firstly, we discuss the characters of So which are applied to prove the conclusion that we seek. For convenience, we need the following notes: for any X = where  (XI'  X2'  ••• ,  set X = (It,  x,,),  Xl'  ••• ,  y,,),  set  .r;;) ,  X~ I  and for any X =  ={ O, if 1, if  Xi X i  = 1, = 0,  (XI' X2' ••• , x,,)  i = 1,2, ... and Y =  ,n,  (YI , Y 2 ' ••• ,  Thus X and X • YES, if X, YES. With the given condition, for any X, Y, Z E S o, we know X • y. Z -=F (0, 0, '" , 0). We prove that for any XES, only one of the relations X E So andX E So is valid andO = (0,0, ... ,0) E So. (1)  Suppose that for any XES, X and X are paired. Thus the 2" elements of S form 2,, - 1 pairs. If some X and X belong to So, then for anyY E So, X·  X· Y =  (0,0, ... ,0). This contradicts the given  condition. Hence there are at most one of X, X belonging to S o. Note that the number of the distinct pairs (X, X) is 2,, - 1 and the number of sequences in So is also 2,, - 1, so there is exactly one of X, X belonging to So. Next, if (0, 0, ... , 0) E So, then for any X, Y E So we know 0· X • Y = (0, 0, ... , 0). This contradicts the given condition. Thus  ° (2)  =  (0, 0, ... , 0) E So.  Next we prove that if X, Y E S o, then X • YES,). If Z = X • Y E  So , from (1), we obtain Z = Z • Y E So, then X • y. Z  =  (X • X) • (y. Y)  =  (0, 0, ... , 0).  65  Classification and Method of Fractional Steps  This contradicts the given condition. Thus X • YES". (3)  Finally, we prove that let Xl' X 2 ,  sequences in S " and X  X l · X2  =  •••••  Xr  I ,  ••• ,  Xr l be 2,,-1 distinct  then there is just one term  in X which equals 1 and the remaining n - 1 terms in X all equal zero . From (1) and (2), we know XES" and X 7"= (0, 0, ... , 0), i. e. there are at lease one term of X which equals 1. If there are at least two terms of X which equal 1, the two terms of each sequence in S " equal 1 and the remaining n - 2 terms of each sequence in S" all equal 1 or O. Hence the number of the sequences in So does not exceed 2,,-2, which contradicts that there are 2,,-1 distinct sequences in So. Secondly, we come back to the original problem. With (3), we could assume that the k th term of X is equal to 1 and the other terms of X are all equal to zero, i. e. there exists an unique positive integer k such that the k th terms of all sequences in SI1 are all equal to 1 and all the other terms of are not equal to 1. This completes the proof. Remark This problem is equivalent to the following problem. Let I  =  {aI, a2' ... , a,, } be a set with n elements, and the set S "  consist of 2,,-1 distinct subsets of I satisfying the following conditions: the intersection of any three elements (i. e. three subsets of  I)  in So is  nonempty. Prove that the intersections of all elements (i. e. 2,,- 1 distinct subsets of  I)  in So have an unique element. In the above  solution, the operations  X and X • Y  just correspond to the operations  of the complement and intersection of the sets. Hence the readers could use the perations of the complement and intersection of the sets to complete the proof.  Exercise 5  1  Suppose that 4-digit numbers abed satisfy the following  conditions:  (1)  a, b, e, d E {1, 2, 3, 4 }; (2) a 7"=b, b 7"= e, e 7"= d,  d 7"= a; (3) a is the smallest number in a, b, e, d. Then number of  66  Combinatorial Problems in Mathematical Competitions  4-digit numbers abed equals Competition in 2(00) 2  (China Mathematical  The 5-digit numbers with at least three distinct digits are  formed from the digits 1, 2, 3, 4, 5, 6. How many these 5-digit numbers are there such that the digits 1 and 6 are nonadjacent? How many even integers with four different digits between  3  4000 and 7000 are there? (11 5t American Invitational Mathematical Examina tion in 1993) There are 3 line segments whose lengths are 1, 2, 3  4  respectively and the line segment with length 3 is divided into any n ( ?': 2) line segments. Prove that among above n  + 2 line  segments, there  must be 3 line segments which are three sides of a triangle. S  Firstly, we select a subset X from set S = {1, 2, ... , n}. Next  we select another subset Y of S such that X is not a subset of Y and Y is not a subset of X too. How many ways are there to select X and Y orderly? 6  In the rectangular coordinates system in plane, there are 9  integerpointsAi(xi'  Yi) (x"  Yi  EZ, i =1,2, ... ,9), no three of  which are collinear. Prove that there exists a LA,AjAk C1 k  <i <j <  < 9) whose barycenter is an integer point too. 7  There are n people in a committee such that among any 3  people, there is a pair of mutually acquainted people. Find the smallest positive integer n such that there are 4 mutually acquainted people in these n persons? 8  There are 7 given points in a plane such that among any three  points, at least two points are connected by a line segment. Find the smallest number of connected line segments and draw a figure satisfying above requirement. (The Problem Prepared for 30 th IMO in 1989) 9  Suppose that the area of a convex hexagon AJA2A3A4A5A6  equals S. Prove that there is at least a triangle LA iA jAk C1 k  < 7) with area not exceeding ~ S.  <i < j <  The correspondence is not only a basic mathematical concept but also an important method and skill to solve the problems and prove the proposi tions. What is more, it is a bridge between the unfamiliar and familiar problems. By a correspondence, covert relations are of

Combinatorial Problems In Mathematical Competitions Pdf

Source: https://3lib.net/book/1167848/46305d

Posted by: shroyerplasoner.blogspot.com

Share this post