Combinatorial Extremization

Yuefeng Feng

• Publisher: WSPC
• Year: 2016
• eBook ISBN: 9789814723183
• Topic: Mathematics
• Subtopic: Counting & Numeration
• Index: Mathematics

In China, lots of excellent students who are good at maths takes an active part in various maths contests and the best six senior high school students will be selected to form the IMO National Team to compete in the International Mathematical Olympiad. In the past ten years China's IMO Team has achieved outstanding results — they have won the first place almost every year.

The author is one of the coaches of China's IMO National Team, whose students have won many gold medals many times in IMO.

This book is part of the Mathematical Olympiad Series which discusses several aspects related to maths contests, such as algebra, number theory, combinatorics, graph theory and geometry. The book elaborates on methods of discrete extremization, such as inequality control, repeated extremum, partial adjustment, exploiting symmetry, polishing transform, space estimates, etc.

Request Inspection Copy

In China, lots of excellent students who are good at maths takes an active part in various maths contests and the best six senior high school students will be selected to form the IMO National Team to compete in the International Mathematical Olympiad. In the past ten years China's IMO Team has achieved outstanding results — they have won the first place almost every year.

The author is one of the coaches of China's IMO National Team, whose students have won many gold medals many times in IMO.

This book is part of the Mathematical Olympiad Series which discusses several aspects related to maths contests, such as algebra, number theory, combinatorics, graph theory and geometry. The book elaborates on methods of discrete extremization, such as inequality control, repeated extremum, partial adjustment, exploiting symmetry, polishing transform, space estimates, etc.

Request Inspection Copy

Readership: Senior high school students engaged in math contests, math teachers, undergraduates of math major and math enthusiasts.
Key Features:

• China has performed outstandingly in IMO and the book gathers from the tutoring experience of many excellent teachers
• The author is one of the leading experts in aspects of maths contests in China as the coach of China's IMO National Team
• The Chinese version of the book has been very popular

Chapter 1Inequality Control

One of the most significant characteristics of combinatorial extremization problems is that the constraints or the expressions of the target function are rather complicated. The so-called inequality control method is to enlarge or shrink the constraints or the target function, in such a way that the relation between the assumptions and the goal becomes more apparent. By enlarging or shrinking, the problem will become close to a standard form, where one needs to find the extremum of u = g (x, y) given f(x, y) = 0. In this way, the combinatorial extremization problem is transformed into an analytic extremization problem.

There are usually two ways to use this method. One is to enlarge or shrink the constraints, making clear the subtle or hidden constraints; the other one is to enlarge or shrink the target function, simplifying the complicate expressions of the function.

Example 1. Assume there are m different positive even integers and n different positive odd integers that add up to 1987. Find the maximum of 3 m + 4n. (2nd CMO)

Analysis and Solution. The difficulty of this question lies in the fact that the constraints are complicated. They can be simplified via inequalities, and then be enlarged or shrunk to meet the target function.

Assume that the m given positive even integers are a₁, a₂, . . . , a_m and the n positive odd integers are b₁, b₂, . . . , b_n, then

Notice that the target function is a function of m, n, and in the constraints m, n only act as subscripts. Thus the constraints in a₁, a₂, . . . , a_m and b₁, b₂, . . . , b_n in

should be transformed into constraints in m, n.

Since a₁, a₂, . . . , a_m and b₁, b₂, . . . , b_n are mutually different positive even integers and positive odd integers, we have

Notice that our goal is to prove 3m + 4n ≤ A for some A, which is akin to the form of Cauchy-Schwartz inequality. Thus the right-hand side of equation

should be transformed i...

Table of contents

• Cover Page
• Title
• Copyright
• Contents
• Introduction
• Preface
• Chapter 1 Inequality Control
• Chapter 2 Repeated Extremum
• Chapter 3 Partial Adjustment
• Chapter 4 Exploiting Symmetry
• Chapter 5 Polishing Transform
• Chapter 6 Space Estimates
• Chapter 7 Block Estimates
• Chapter 8 Guesses and Contradiction
• Chapter 9 Global Estimates
• Chapter 10 Parameter Estimates
• Chapter 11 Counting in Two Ways
• Chapter 12 Shrinking the Encirclement
• Chapter 13 Considering Special Cases
• Solutions to Exercises