There is noticeable correlation between sample problems and those in List A, such that the latter are clearly intended for practicing techniques the author discusses in the sample problems.
Problems in List B require more experience and originality. It is obvious that the author went to a considerable length gathering and organizing the problems according to the solution techniques and difficulty. Of the problem books I own, the two books at hand resemble most Arthur Engel's Problem Solving Strategies in structure and probably intention.
In comparison Xu Jiagu's explanations are more frugal, and only few problems come with more than one solution.
The brevity of introductory explanations is made up by the careful selection of List A problems closely related to the samples solved by the author. Consistent with this approach, Xu Jiagu's topics are more narrowly defined, making for more chapters, each better focused.
The books have been in my possession for a week now. While browsing I found only one insignificant typo; of the several problems I have solved, I can honestly claim that for only one problem my solution was better — clearer and based on more fundamental skills — than the one in the book. I see the books used beneficially by olympiad coaches and, individually, by aspiring olympians.
Many problems, especially among the introductory samples, could be used in math circles or as extras in honors classes. Alex Bogomolny is a former associate professor of mathematics at University of Iowa. In an extreme need you can tweet him at CutTheKnotMath. Skip to main content. Search form Search. At the first step, for getting a group of 7 balls with the same color, at least 43 balls are needed to be picked out from the bag at random, since if only 42 balls are picked out, there may be exactly 6 for each color.
Next, after getting the first group, it is sufficient to pick out from the bag another 7 balls for getting 43 balls once again. Then, by the same reason, the second group of 7 homochromatic drawn balls can be obtained. Repeating this process for 6 times, the 7 groups of 7 homochromatic balls are obtained. There are 60 red ones, 60 blue ones, 60 green ones and the remaining 20 consist of yellow and white ones. If marbles are chosen from the bag without looking, what is the smallest number of marbles one must pick in order to ensure that, among the chosen marbles, at least 20 are of the same colour?
Solution When 77 marbles are chosen, there may be 19 red, 19 blue, 19 green and 20 yellow and white. If 78 marbles are chosen at random, the number of yellow and white ones among them is at most Therefore there are at least 58 marbles of red, blue or green colors. Thus, the smallest 3 number of marbles to be picked is In this problem, a color is taken as a pigeonhole, and then a drawn marble is taken as a pigeon.
Any number in A can be written uniquely in the form 2m q, where m is a non-negative integer, and q is an odd number. When all the numbers in A are partitioned according to q into 50 classes, then each number in A must belong to a unique class. Now for any 51 numbers in A, by the Pigeonhole Principle, there must be two of them coming from a same class, and these two numbers must satisfy the requirement: one is multiple of another since they have the same q.
In this problem, a pigeonhole is the set of all numbers in A with same maxi- mum odd factor q, since any two numbers in the pigeonhole have required prop- erty. Lecture Notes on Mathematical Olympiad 33 Example 4. Then there are numbers in each of L1 , L2 , L3 but numbers in L0. For the set L1 , arrange all the numbers in an ascending order, and consider the pairs formed by its numbers 1, 5 , 9, 13 , 17, 21 ,.
By Pigeonhole Principle, if more than numbers in L1 are selected out as part of L, then there must be some two numbers coming from one of the above pairs, so their difference is 4. Thus, any more than numbers in L1 cannot be put in L. However, all numbers on odd numbered places or all numbers on even places can be chosen.
Thus at most numbers can be chosen from L1 as a subset of L, and the same analysis works for each of L2 , L2 and L0 in L0 all the numbers which are odd multiples of 4 can be chosen to put in L. Therefore the maximum number of the elements in L is For applying the pigeonhole principle, the listed pairs take the role of pigeon- holes, and the chosen numbers are the pigeons.
The congruence relation is a method commonly used for classifying integers. This method is also often used for applying pigeonhole principle, as shown in the following examples. Partition the five numbers according to the remainders modulo 3 into three classes: C0 , C1 , and C2.
But from each class take a number, the three numbers must have a sum divisible by 3. Prove that in a set containing n positive integers there must be a subset such that the sum of all numbers in it is divisible by n. Solution Let the n positive integers be a1 , a2 ,. Then all the n values are distinct.
When some of b1 , b2 ,. Otherwise, if all bi are not divisible by n, then their remainders are all not zero, i. By the pigeonhole 2 principle, there must be one such square containing at least 2 points.
The conclusion is proven. If any two of them are connected by a segment, and each segment is colored by one of red color or blue color, prove that there must be at least one triangles formed by three points and segments joining them, such that the three sides are of the same color. Consider the segments joining A. We use a real segment to denote a. A5 segment, as shown in the diagram.
Consider the five segments starting from A0 Each of.. By Pi A least three with the same color. Without loss of A 2. A3 Now consider three sides of the triangle A1 A2 A3. When one side is red, then there is a red triangle, i. Otherwise, the three sides of 4A1 A2 A3 are all blue, then the conclusion is also true. Prove that among the triangles formed by these points, there must be one 1 with area not greater than m2.
Prove that under any coloring there must be a rectangular region with four angles of same color. Prove that at least three of the nine lines pass through a same point. Prove that there must be two numbers in A such that their sum is Prove that one can always select out 5 numbers from them such that their sum is divisible by 5. In their letters only three different topics are discussed.
Each pair of correspondents deals with only one of these topics. Prove that there are at least three people who write to each other about the same topic. The list of members contains names, numbered 1, 2, Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country. In general, for x1 ,. But here we will given some examples only belonging to the first two kinds of problems.
It implies that bxc may be 1, 2,. The highest power of 11 in ! Thus, there are a total of 6 real solutions. Lecture Notes on Mathematical Olympiad 41 Example 5. Find the value of x. Solution Then Find bSc. Prove that the sum of the reciprocals of these numbers is less than 2. Solution Let the given positive integers be a1 , a2 ,. Since any two of them have an L. Fine the range of a. Here b nc de- notes the largest integer less than or equal to n.
Hence, based on the uncertainty of solutions, this kind of equations are also called indefinite equations in countries.
Besides, the Diophantine problem is also called the problem for finding integer solutions of equations.
In this chapter the discussion is confined to linear equations and the systems of linear equations. Theorem I. The equation Otherwise, if x, y is an integer solution of Therefore, below it is always assumed that the Eq. Theorem II. When each of the b numbers a, 2a, 3a,. The conclusion of Theorem II is proven. If x0 , y0 is a special integer solution of the Equation Let x, y be any solution of For solving a system of Diophantine equations or an equation with more than two variables, substitution method can be used for simplifying the equation.
Thus, the equation has exactly two solutions. Solution It is not obvious to find a special solution. Here substitution can be used to simplify the equation. Find the three-digit number abc. Find the minimum positive integer value of a. Thus, the answer is D. When pebbles are moved from A to B , then the number of pebbles in B is double of that in A. However, if some are moved from B to A , then the number of pebbles in A is five times more than that in B. What is the minimum possible number of pebbles in A , and find the number of pebbles in B in that case.
Solution Let x and y be the numbers of pebbles in the piles A and B respectively. Example Find the minimum value of such four digit numbers. A dragonfly has six feet and a spider has 8 feet. Given that a certain group of dragonflies and spiders have in total 46 feet, find the number of dragonflies and the number of spiders. Given that x 1-cent coins, y 2-cent coins, and z 5-coins have a total value of 10 dollars.
Find the possible values of x, y, z. If a four digit number and the sum of its all digits have a sum , find the four digit number. Someone has coins to buy chickens, how many roosters, hens and chicks can a man purchase out of a total cost of coins? Find the values of x, y and z. Find the number of each kind of weights in the pile. After repeating times of such operations, whether the resulting number is divisible by i ? All the methods for factorizations can be used here, including multiplication formulae, factor theorem and observation method, etc.
III For quadratic equations with absolute values, it is needed to convert them to normal equations by substitution or by partitioning the range of x piece- wise to remove the absolute signs. Solution The given equations have parameters, so the discussion on param- eters is necessary. Note: This example indicates that it is not always convenient to use the for- mula for roots to solve an quadratic equation, in particular, if the equation contains parameters.
Solution The problem can be solved by manipulating the left hand side of the equation. Find the values of a and b. Lecture Notes on Mathematical Olympiad 57 Example 8. Substituting Applying Thus, the answer is A. Quadratic equation can be applied to solve geometric problems, as shown in the following examples Example 9.
Prove that the three segments with lengths a, b, c can form a triangle. In problems about quadratic equations, the relation between roots of two qua- dratic equations is discussed often, as shown in the following example. For the equation Determine if the three segments of lengths a, b, c can form a triangle.
If so, what is the type of the triangle? Give your reasons. Fat is going to pick three non-zero real numbers and Mr. Fat wins the game if and only if the resulting equation has two distinct rational solutions. Who has a winning strategy? Find the value of. Lecture 25 Relation between Roots and Coefficients of Quadratic Equations Viete Theorem and Newton Identity are two important results in discussing the relation between roots and coefficients of polynomial equations.
As the funda- mental knowledge about the quadratic equation, in this chapter we only mention Viete theorem and its some applications.
Or, the conclusion can be verified by applying the formula for roots. Conversely, by applying the Viete Theorem, the given information on roots of a quadratic equation with parameters can be used to determine the values or ranges of the parameters.
To construct quadratic equations by using the inverse Viete theorem can be also used to determine the values of some algebraic expressions. The examples below will explain these applications. Prove that the equation has two real roots, where one is greater than a, and the other is less than a. Under the substitution, the problem becomes one to prove one root is positive and the other is negative for y.
Find the solutions to each of the two equations. Let the right hand side of the equation be a con- stant, zero or a power of a prime number in the case of indicial equation , and factorize the left hand side to the form of product of linear factors, then discuss the possible values of the linear factors based on the factorization of the right hand side. II Discriminant Method. When a quadratic equation with integer coeffi- cients has integer solution s , its discriminant must be a perfect square.
This feature will play an important role. When the quadratic equation contains two variables x, y, by the formula for roots, x can be expressed in terms of y, and its discriminant is an expression in y.
Since the discriminant is a perfect square and that y is an integer, y can be found easily in many cases. Besides the use of discriminant, the use of Viete Theorem and transfor- mation or substitution are also useful tools for simplifying and solving quadratic equations. III Congruence, divisibility, and parity analysis, etc. Find the value of n. Solution This question can be solved by factorization method. By checking, 33 satisfies the given equation. Thus, there are a total of 45 required solutions.
Viete Theorem is also used for solving Diophantine equations. Below is an example. Find the values of p and q. From Corresponding to them, the pairs of p, q are 4, , , 4 , 7, 13 , 13, 7.
Thus, the solution for p, q is 13, 7. Many techniques often used in number theory, like congruence, divisibility, parity analysis, etc. Below a few such examples are given.
We show that a, b and c must all be even by taking modulo 4 to both sides of the equation. Thus, a, b, c are all even. Thus, the equation has only zero solution. It is sometimes useful to use substitution to simplify the equation first, below is such an example. Solution 23 is a prime, so that the second equation has less uncertainty, we deal with it first.
Thus the solutions are 2, 21, 1 and 20, 3, 1 , the answer is B. Find the value of a. Find the value of p. Definition 2 When an inequality or a system of inequalities has k unknown variables x1 , x2 ,. Any point x1 , x2 ,. Note that the property IV is exclusive for inequalities, but the properties I to III are similar to the case of equalities.
At the step v , a should be converted to 1 if a is given constant, however, if a a parameter or contains parameters, then the discussion on the possible cases of the parameters is needed. Since the signs of a and c are not determined, c so the signs of a2 c and ac2 are not determined.
The answer is C. Thus, the answer is C. So to each inequality in the system we can find its solution set first, then the common part of these sets is the solution set of the system. Testing Questions A c a b 1. Find the range of x. Find the range of. Find the number of the ordered pairs a, b. Find the range of the constant a. Lecture 28 Quadratic Inequalities and Fractional Inequalities In this chapter the quadratic inequalities and fractional inequalities of single vari- able are discussed.
IV If there are more than one linear factors in the denominator or numerator of the fractional expression g x , then it is needed to discuss the sign of g x by partitioning the range of x into several intervals, where the partition points are given by letting each linear factor be zero.
Thus, the construction of g x to be considered can be simplified much. V In mathematical olympiad competitions, inequalities containing parame- ters often occur. One kind of the common problems is to determine the values or ranges of the parameters based on information contained in the given inequality and other given conditions. Solution By factorization the given inequality can be simplified.
Find the range of the parameter a. Lecture 29 Inequalities with Absolute Values The most important technique for solving inequalities with absolute values is the same as in solving equations with absolute values, i. V When two or more pairs of absolute value signs occur in a same layer of the given inequality, the general method for removing the absolute value signs is partitioning the range of variable into several intervals, so that the values of each expression between a pair of absolute signs has a fixed sign.
For this it is necessary to let each such expression be zero, and take its roots as the partition points. Solution There are two layers of absolute value signs in the given expres- sion.
By taking squares to both sides, the absolute value signs in the outer layer can be removed. When an inequality with absolute values contains parameters, then, similar to the case of without absolute values, the inequality can give some information on the range of the parameters, as shown in the following example.
Determine which of the following listed expressions holds. Find the values of constants a, b, c. Lecture 30 Geometric Inequalities In this chapter we discuss the inequalities that deal with lengths of segments, sizes of angles and sizes of areas of geometric graphs. The following theorems are the basic tools for dealing with geometric inequalities: Theorem I.
Among the paths joining two given points, the segment joining them is the shortest. Theorem IV. For a triangle, a longer side is opposite to a bigger angle, a shorter side is opposite to a smaller angle, and vice versa.
Theorem V. For any triangle, the median to a side is less than half of the sum of other two sides. B C Example 2. Then ABB1 C Connect B1 D. Then 4CDB1 is equilateral. Applying the trian B1 as desired. Since BCF G is a rectangle, Now construct an isosceles triangle BDE by extending Next, we make parallelogram ACF D Connect BM. Without loss of generality we may assume B , C be the symmetric points of B, C in the.
Lecture Notes on Mathematical Olympiad 99 Example 8. Prove that the difference of areas of 1 the two parts is not greater than of area of the 4ABC. P is a point on the hypotenuse, and the feet of the per- pendiculars from P to the other sides are Q and R. Prove that re- 2 gardless of how P is chosen, the largest one of these three areas is at least. Given that R is an inner point of 4ABC.
Lecture Notes on Mathematical Olympiad 4. Among its 3 inscribed squares, which one has the maximum area? We find [M ] first. It is clear that n is odd since it is the product of odd numbers. Since 15, 35, 55 are three numbers in the product, so n is divisible by , hence x is divisible by Thus, the possible values of x are , , , only. Let n be the solution. Lecture Notes on Mathematical Olympiad 9.
Testing Questions B 14 1. Solution 1 First of all we find the remainder of modulo Below we find the minimum value of m recursively. Below by two examples we indicate that 9 is the maximum possible value of n. Thus, the number is By checking, it is certainly a solution. Let the original four digit number be n. Thus, the four digit number is
0コメント