China 2009-2010 PDF
China 2009-2010 PDF
China 2009-2010 PDF
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 Xu Jiagu
Vol. 7 A Second Step to Mathematical Olympiad Problems
by Xu Jiagu
Vol. 9 Mathemaitcal Olympiad in China (2009–2010)
A catalogue record for this book is available from the British Library.
Mathematical Olympiad Series—Vol. 9
October 2011
Introduction
Early days
The International Mathematical Olympiad (IMO), founded in 1959, is one of the most competitive
and highly intellectual activities in the world for high school students.
Even before IMO, there were already many countries which had mathematics competition. They
were mainly the countries in Eastern Europe and in Asia. In addition to the popularization of
mathematics and the convergence in educational systems among different countries, the success of
mathematical competitions at the national level provided a foundation for the setting-up of IMO. The
countries that asserted great influence are Hungary, the former Soviet Union and the United States.
Here is a brief review of the IMO and mathematical competition in China.
In 1894, the Department of Education in Hungary passed a motion and decided to conduct a
mathematical competition for the secondary schools. The well-known scientist, J. von Etövös, was
the Minister of Education at that time. His support in the event had made it a success and thus it
was well publicized. In addition, the success of his son, R. von Etövös, who was also a physicist, in
proving the principle of equivalence of the general theory of relativity by A. Einstein through
experiment, had brought Hungary to the world stage in science. Thereafter, the prize for
mathematics competition in Hungary was named “Etövös prize“. This was the first formally
organized mathematical competition in the world. In what follows, Hungary had indeed produced a
lot of well-known scientists including L. Fejér, G. Szegö, T. Radó, A. Haar and M. Riesz (in real
analysis), D. König (in combinatorics), T. von Kármán (in aerodynamics), and J. C. Harsanyi (in game
theory), who had also won the Nobel Prize for Economics in 1994. They all were the winners of
Hungary mathematical competition. The top scientific genius of Hungary, J. von Neumann, was one
of the leading mathematicians in the 20th century. Neumann was overseas while the competition
took place. Later he did it himself and it took him half an hour to complete. Another mathematician
worth mentioning is the highly productive number theorist P. Erdös. He was a pupil of Fejér and
also a winner of the Wolf Prize. Erdös was very passionate about mathematical competition and
setting competition questions. His contribution to discrete mathematics was unique and greatly
significant. The rapid progress and development of discrete mathematics over the subsequent
decades had indirectly influenced the types of questions set in IMO. An internationally recognized
prize named after Erdös was to honour those who had contributed to the education of mathematical
competition. Professor Qiu Zonghu from China had won the prize in 1993.
In 1934, a famous mathematician B. Delone conducted a mathematical competition for high
school students in Leningrad (now St. Petersburg). In 1935, Moscow also started organizing such
event. Other than being interrupted during the World War II, these events had been carried on until
today. As for the Russian Mathematical Competition (later renamed as the Soviet Mathematical
Competition), it was not started until 1961. Thus, the former Soviet Union and Russia became the
leading powers of Mathematical Olympiad. A lot of grandmasters in mathematics including the
great A. N. Kolmogorov were all very enthusiastic about the mathematical competition. They would
personally involve in setting the questions for the competition. The former Soviet Union even called
it the Mathematical Olympiad, believing that mathematics is the “gymnastics of thinking”. These
points of view gave a great impact on the educational community. The winner of the Fields Medal in
1998, M. Kontsevich, was once the first runner-up of the Russian Mathematical Competition. G.
Kasparov, the international chess grandmaster, was once the second runner-up. Grigori Perelman,
the winner of the Fields Medal in 2006 (but he declined), who solved the Poincarés Conjecture, was
a gold medalist of IMO in 1982.
In the United States of America, due to the active promotion by the renowned mathematician
G.D. Birkhoff and his son, together with G. Pólya, the Putnam mathematics competition was
organized in 1938 for junior undergraduates. Many of the questions were within the scope of high
school students. The top five contestants of the Putnam mathematical competition would be entitled
to the membership of Putnam. Many of these were eventually outstanding mathematicians. There
were the famous R. Feynman (winner of the Nobel Prize for Physics, 1965), K. Wilson (winner of the
Nobel Prize for Physics, 1982), J. Milnor (winner of the Fields Medal, 1962), D. Mumford (winner of
the Fields Medal, 1974), and D. Quillen (winner of the Fields Medal, 1978).
Since 1972, in order to prepare for the IMO, the United States of America Mathematical
Olympiad (USAMO) was organized. The standard of questions posed was very high, parallel to that
of the Winter Camp in China. Prior to this, the United States had organized American High School
Mathematics Examination (AHSME) for the high school students since 1950. This was at the junior
level yet the most popular mathematics competition in America. Originally, it was planned to select
about 100 contestants from AHSME to participate in USAMO. However, due to the discrepancy in
the level of difficulty between the two competitions and other restrictions, from 1983 onwards, an
intermediate level of competition, namely, American Invitational Mathematics Examination (AIME),
was introduced. Henceforth both AHSME and AIME became internationally well-known. A few cities
in China had participated in the competition and the results were encouraging.
The members of the national team who were selected from USAMO would undergo training at
the West Point Military Academy, and would meet the President at the White House together with
their parents. Similarly as in the former Soviet Union, the Mathematical Olympiad education was
widely recognized in America. The book “How to Solve it” written by George Polya along with many
other titles had been translated into many different languages. George Polya provided a whole
series of general heuristics for solving problems of all kinds. His influence in the educational
community in China should not be underestimated.
International Mathematical Olympiad
In 1956, the East European countries and the Soviet Union took the initiative to organize the IMO
formally. The first International Mathematical Olympiad (IMO) was held in Brasov, Romania, in
1959. At the time, there were only seven participating countries, namely, Romania, Bulgaria,
Poland, Hungary, Czechoslovakia, East Germany and the Soviet Union. Subsequently, the United
States of America, United Kingdom, France, Germany and also other countries including those from
Asia joined. Today, the IMO had managed to reach almost all the developed and developing
countries. Except in the year 1980 due to financial difficulties faced by the host country, Mongolia,
there were already 49 Olympiads held and 97 countries participating.
The mathematical topics in the IMO include number theory, polynomials, functional equations,
inequalities, graph theory, complex numbers, combinatorics, geometry and game theory. These
areas had provided guidance for setting questions for the competitions. Other than the first few
Olympiads, each IMO is normally held in mid-July every year and the test paper consists of 6
questions in all. The actual competition lasts for 2 days for a total of 9 hours where participants are
required to complete 3 questions each day. Each question is 7 points which total up to 42 points.
The full score for a team is 252 marks. About half of the participants will be awarded a medal,
where 1/12 will be awarded a gold medal. The numbers of gold, silver and bronze medals awarded
are in the ratio of 1 : 2 : 3 approximately. In the case when a participant provides a better solution
than the official answer, a special award is given.
Each participating country will take turn to host the IMO. The cost is borne by the host country.
China had successfully hosted the 31st IMO in Beijing. The event had made a great impact on the
mathematical community in China. According to the rules and regulations of the IMO, all
participating countries are required to send a delegation consisting of a leader, a deputy leader and
6 contestants. The problems are contributed by the participating countries and are later selected
carefully by the host country for submission to the international jury set up by the host country.
Eventually, only 6 problems will be accepted for use in the competition. The host country does not
provide any question. The short-listed problems are subsequently translated, if necessary, in
English, French, German, Russian and other working languages. After that, the team leaders will
translate the problems into their own languages.
The answer scripts of each participating team will be marked by the team leader and the deputy
leader. The team leader will later present the scripts of their contestants to the coordinators for
assessment. If there is any dispute, the matter will be settled by the jury. The jury is formed by the
various team leaders and an appointed chairman by the host country. The jury is responsible for
deciding the final 6 problems for the competition. Their duties also include finalizing the grading
standard, ensuring the accuracy of the translation of the problems, standardizing replies to written
queries raised by participants during the competition, synchronizing differences in grading between
the team leaders and the coordinators and also deciding on the cut-off points for the medals
depending on the contestants’ results as the difficulties of problems each year are different.
China had participated informally in the 26th IMO in 1985. Only two students were sent.
Starting from 1986, except in 1998 when the IMO was held in Taiwan, China had always sent 6
official contestants to the IMO. Today, the Chinese contestants not only performed outstandingly in
the IMO, but also in the International Physics, Chemistry, Informatics, and Biology Olympiads. So
far, no other countries have overtaken China in the number of gold and silver medals received. This
can be regarded as an indication that China pays great attention to the training of basic skills in
mathematics and science education.
Winners of the IMO
Among all the IMO medalists, there were many of them who eventually became great
mathematicians. They were also awarded the Fields Medal, Wolf Prize and Nevanlinna Prize (a
prominent mathematics prize for computing and informatics). In what follows, we name some of the
winners.
G. Margulis, a silver medalist of IMO in 1959, was awarded the Fields Medal in 1978. L. Lovasz,
who won the Wolf Prize in 1999, was awarded the Special Award in IMO consecutively in 1965 and
1966. V. Drinfeld, a gold medalist of IMO in 1969, was awarded the Fields Medal in 1990. J.-C.
Yoccoz and T. Gowers, who were both awarded the Fields Medal in 1998, were gold medalists in
IMO in 1974 and 1981 respectively. A silver medalist of IMO in 1985, L. Lafforgue, won the Fields
Medal in 2002. A gold medalist of IMO in 1982, Grigori Perelman from Russia, was awarded the
Fields Medal in 2006 for solving the final step of the Poincaré conjecture. In 1986, 1987, and 1988,
Terence Tao won a bronze, silver, and gold medal respectively. He was the youngest participant to
date in the IMO, first competing at the age of ten. He was also awarded the Fields Medal in 2006.
Gold medalist of IMO 1988 and 1989, Ngo Bau Chao, won the Fields Medal in 2010, together with
the bronze medalist of IMO 1988, E. Lindenstrauss.
A silver medalist of IMO in 1977, P. Shor, was awarded the Nevanlinna Prize. A gold medalist of
IMO in 1979, A. Razborov, was awarded the Nevanlinna Prize. Another gold medalist of IMO in
1986, S. Smirnov, was awarded the Clay Research Award. V. Lafforgue, a gold medalist of IMO in
1990, was awarded the European Mathematical Society prize. He is L. Lafforgues younger brother.
Also, a famous mathematician in number theory, N. Elkies, who is also a professor at Harvard
University, was awarded a gold medal of IMO in 1982. Other winners include P. Kronheimer
awarded a silver medal in 1981 and R. Taylor a contestant of IMO in 1980.
Mathematical competition in China
Due to various reasons, mathematical competition in China started relatively late but is progressing
vigorously.
“We are going to have our own mathematical competition too!” said Hua Luogeng. Hua is a
house-hold name in China. The first mathematical competition was held concurrently in Beijing,
Tianjin, Shanghai and Wuhan in 1956. Due to the political situation at the time, this event was
interrupted a few times. Until 1962, when the political environment started to improve, Beijing and
other cities started organizing the competition though not regularly. In the era of Cultural
Revolution, the whole educational system in China was in chaos. The mathematical competition
came to a complete halt. In contrast, the mathematical competition in the former Soviet Union was
still on-going during the war and at a time under the difficult political situation. The competitions in
Moscow were interrupted only 3 times between 1942 and 1944. It was indeed commendable.
In 1978, it was the spring of science. Hua Luogeng conducted the Middle School Mathematical
Competition for 8 provinces in China. The mathematical competition in China was then making a
fresh start and embarked on a road of rapid development. Hua passed away in 1985. In
commemorating him, a competition named Hua Luogeng Gold Cup was set up in 1986 for students
in Grade 6 and 7 and it has a great impact.
The mathematical competitions in China before 1980 can be considered as the initial period.
The problems set were within the scope of middle school textbooks. After 1980, the competitions
were gradually moving towards the senior middle school level. In 1981, the Chinese Mathematical
Society decided to conduct the China Mathematical Competition, a national event for high schools.
In 1981, the United States of America, the host country of IMO, issued an invitation to China to
participate in the event. Only in 1985, China sent two contestants to participate informally in the
IMO. The results were not encouraging. In view of this, another activity called the Winter Camp was
conducted after the China Mathematical Competition. The Winter Camp was later renamed as the
China Mathematical Olympiad or CMO. The winning team would be awarded the Chern Shiing-Shen
Cup. Based on the outcome at the Winter Camp, a selection would be made to form the 6-member
national team for IMO. From 1986 onwards, other than the year when IMO was organized in
Taiwan, China had been sending a 6-member team to IMO. Up to 2011, China had been awarded the
overall team champion for 17 times.
In 1990, China had successfully hosted the 31st IMO. It showed that the standard of
mathematical competition in China has leveled that of other leading countries. First, the fact that
China achieves the highest marks at the 31st IMO for the team is an evidence of the effectiveness of
the pyramid approach in selecting the contestants in China. Secondly, the Chinese mathematicians
had simplified and modified over 100 problems and submitted them to the team leaders of the 35
countries for their perusal. Eventually, 28 problems were recommended. At the end, 5 problems
were chosen (IMO requires 6 problems). This is another evidence to show that China has achieved
the highest quality in setting problems. Thirdly, the answer scripts of the participants were marked
by the various team leaders and assessed by the coordinators who were nominated by the host
countries. China had formed a group 50 mathematicians to serve as coordinators who would ensure
the high accuracy and fairness in marking. The marking process was completed half a day earlier
than it was scheduled. Fourthly, that was the first ever IMO organized in Asia. The outstanding
performance by China had encouraged the other developing countries, especially those in Asia. The
organizing and coordinating work of the IMO by the host country was also reasonably good.
In China, the outstanding performance in mathematical competition is a result of many
contributions from the all quarters of mathematical community. There are the older generation of
mathematicians, middle-aged mathematicians and also the middle and elementary school teachers.
There is one person who deserves a special mention and he is Hua Luogeng. He initiated and
promoted the mathematical competition. He is also the author of the following books: Beyond Yang
huis Triangle, Beyond the pi of Zu Chongzhi, Beyond the Magic Computation of Sun-zi,
Mathematical Induction, and Mathematical Problems of Bee Hive. These were his books derived
from mathematics competitions. When China resumed mathematical competition in 1978, he
participated in setting problems and giving critique to solutions of the problems. Other outstanding
books derived from the Chinese mathematics competitions are: Symmetry by Duan Xuefu, Lattice
and Area by Min Sihe, One Stroke Drawing and Postman Problem by Jiang Boju.
After 1980, the younger mathematicians in China had taken over from the older generation of
mathematicians in running the mathematical competition. They worked and strived hard to bring
the level of mathematical competition in China to a new height. Qiu Zonghu is one such outstanding
representative. From the training of contestants and leading the team 3 times to IMO to the
organizing of the 31th IMO in China, he had contributed prominently and was awarded the P. Erdös
prize.
Preparation for IMO
Currently, the selection process of participants for IMO in China is as follows.
First, the China Mathematical Competition, a national competition for high Schools, is
organized on the second Sunday in October every year. The objectives are: to increase the interest
of students in learning mathematics, to promote the development of co-curricular activities in
mathematics, to help improve the teaching of mathematics in high schools, to discover and cultivate
the talents and also to prepare for the IMO. This happens since 1981. Currently there are about
200,000 participants taking part.
Through the China Mathematical Competition, around 150 of students are selected to take part
in the China Mathematical Olympiad or CMO, that is, the Winter Camp. The CMO lasts for 5 days
and is held in January every year. The types and difficulties of the problems in CMO are very much
similar to the IMO. There are also 3 problems to be completed within 4. 5 hours each day. However,
the score for each problem is 21 marks which add up to 126 marks in total. Starting from 1990, the
Winter Camp instituted the Chern Shiing-Shen Cup for team championship. In 1991, the Winter
Camp was officially renamed as the China Mathematical Olympiad (CMO). It is similar to the
highest national mathematical competition in the former Soviet Union and the United States.
The CMO awards the first, second and third prizes. Among the participants of CMO, about 20 to
30 students are selected to participate in the training for IMO. The training takes place in March
every year. After 6 to 8 tests and another 2 rounds of qualifying examinations, only 6 contestants
are short-listed to form the China IMO national team to take part in the IMO in July.
Besides the China Mathematical Competition (for high schools), the Junior Middle School
Mathematical Competition is also developing well. Starting from 1984, the competition is organized
in April every year by the Popularization Committee of the Chinese Mathematical Society. The
various provinces, cities and autonomous regions would rotate to host the event. Another
mathematical competition for the junior middle schools is also conducted in April every year by the
Middle School Mathematics Education Society of the Chinese Educational Society since 1998 till
now.
The Hua Luogeng Gold Cup, a competition by invitation, had also been successfully conducted
since 1986. The participating students comprise elementary six and junior middle one students. The
format of the competition consists of a preliminary round, semifinals in various provinces, cities and
autonomous regions, then the finals.
Mathematical competition in China provides a platform for students to showcase their talents in
mathematics. It encourages learning of mathematics among students. It helps identify talented
students and to provide them with differentiated learning opportunity. It develops co-curricular
activities in mathematics. Finally, it brings about changes in the teaching of mathematics.
Contents
Preface
Introduction
China Mathematical Competition
2008 (Chongqing)
2009 (Heilongjiang)
China Mathematical Competition (Complementary Test)
2008 (Chongqing)
2009 (Heilongjiang)
China Mathematical Olympiad
2009 (Qionghai, Hainan)
2010 (Chongqing)
China National Team Selection Test
2009 (Wuhan, Hubei)
2010 (Yingtan, Jiangxi)
China Girls’ Mathematical Olympiad
2008 (Zhongshan, Guangdong)
2009 (Xiamen, Fujian)
China Western Mathematical Olympiad
2008 (Guiyang, Guizhou)
2009 (Kunming, Yunnan)
China Southeastern Mathematical Olympiad
2009 (Nanchang, Jiangxi)
2010 (Changhua, Taiwan)
International Mathematical Olympiad
2009 (Bremen, Germany)
2010 (Astana, Kazakhstan)
China Mathematical Competition
2008 (chongqing)
The equality holds if and only if and it is so when x = 1 ∈ (− ∞, 2). This means
that f reaches the minimum value 2 at x = 1.
Answer: C
Let A = [−2, 4), B = {x | x2−ax −4 0}. If B ⊆ A, then the range of real a is ( ).
number of games reaches six. Suppose that the probabilities of A and B winning a game are
and respectively, and each game is independent. Then the expectation Eξ for the match
ending with ξ games is ( ).
Solution I It is easy to see that ξ can only be 2, 4 or 6. We divide the six games into three rounds,
each consisting of two consecutive games. If one of the players wins two games in the first round,
the match ends and the probability is
Otherwise the players tie with each other, earning one point each, and the match enters the second
Then
Answer; B
Solution II Let Ak denote the event that A wins the kth game, while means that B wins the
game. Since Ak and are incompatible, and are independent of the other events, we have
Then
Answer: B
Given three cubes with integer edge lengths, if the sum of their surface areas is 564 cm2, then
the sum of their volumes is ( ).
Solution Denote the edge lengths of the three cubes as a, b and c, respectively. Then we have
Then
It follows that c2 > 31. So 6 c < 10, and this means that c can only be 9, 8, 7 or 6.
If c = 9, then
This means that b 4 and 2b2 30; it follows that b = 4 or 5, so a2 = 5 or 14; in both cases a
has no integer solution.
If c = 7, then
Answer: A
The number of rational solutions to the system of equations
Solution If z = 0, then It follows that
From x + y + z = 0 we have
It is easy to see that y3 − y − 1 has no rational solution, and so y = 1. Then from and we
get x = − 1 and z = 0, contradicting z ≠ 0.
In summary, the system has exactly two solutions:
Answer: B
Suppose that the sides a, b, c of ΔABC, corresponding to the angles A, B, C respectively,
Solution Suppose that the common ratio of a, b, c is q. Then b = aq, c = aq2, We have
So we only need to determine the range of q. As a, b, c are the sides of a triangle, they satisfy a
+ b > c and b + c > a. That is to say,
It follows that
Answer: C
Part II Short-Answer Questions (Questions 7—12, nine marks
each)
Let f(x) = ax + b, with a, b real numbers; f1(x) = f(x), fn+1(x) = f(fn(x)), n = 1,2, …. If f7(x) =
128x + 381, then a + b = _______.
Solution From the definitions we get
As f7(x) = 128x + 381, we have a7 = 128 and 381. Then a = 2, b = 3. The answer is
a + b = 5.
Suppose that the minimum of f(x) = cos 2x − 2a(1 + cos x) is − Then a =________.
Solution We have
For a > 2, f(x) takes the minimum value of 1 − 4a when cos x = 1; for a <− 2, f(x) takes the
It is easy to see that f(x) will never be − for a > 2 or a < −2. So it is only possible that
Since the two ends of the line must be occupied by a bar, respectively, there are ways
to insert the other 2 bars into the 23 spaces between the 24 asterisks such that there is at least 1
asterisk between every two consecutive bars, in which there are 31 ways that at least two schools
have the same number of volunteers. So the number of allocating ways satisfying the conditions is
253 − 31 = 222.
Let Sn denote the sum of the first n terms in a number sequence {an}, satisfying
Then an =_________.
Solution As
we have
Therefore,
This means that g(x) g(x + 6) g(x + 4) g(x + 2) g(x), and it implies that g(x) is a
periodic function with 2 as a period. So
Suppose that a ball with radius 1 moves freely inside a regular tetrahedron with edge length
Then the area of the inner surface of the container, which the ball can never touch,
is_______.
Solution As shown in Fig. 1, consider the situation where the ball is in a corner of the container.
Draw the plane A1B1C1 || ABC, tangent to the ball at point D. Then the ball center O is also the
center of the tetrahedron P-A1B1C1, with PO A1B1C1 and the foot point D being the center of
ΔA1B1C1.
Fig. 1
Since
we have PD = 4OD = 4r, where r is the radius of the ball. It follows that
Suppose that the ball is tangent to the plane PAB at point P1. Then we have
As shown in Fig. 2, it is easy to see that the locus of the ball on the plane PAB is also a regular
triangle, denoted by P1EF. Through P1 draw P1M PA with point M on PA. Then MPP1 = , and
Fig. 2
It follows that P1E = PA − 2PM = , where a = PA. Now, the space on PAB which the ball
will never touch is the shaded part of Fig. 2, and its size is equal to
since r = 1 and under given conditions. Then the total untouched area is
Solution The image of the three intercepting points of f(x) and y = kx is shown in the figure. It is
easy to see that the curve and the line are tangent to each other at point A(α, −sin α), and α ∈
Solution I As
and log2 y is monotonically increasing over (0, +∞), the given inequality is equivalent to
or
It can be rewritten as
That is to say,
and log2 y is monotonically increasing over (0, +∞), the given inequality is equivalent to
or
That is to say,
As is shown in the figure, P is a moving point on the parabola y2 = 2x, points B, C are on the y
axis, and the circle (x − 1)2 + y2 = 1 is internally tangent to ΔPBC. Find the minimum value of
the area of A ΔPBC.
Solution Denote P, B, C by P(x0, y0), B(0, b), C(0, c), and assume that b > c. The equation for the
line PB is
It can be rewritten as
Since the distance between the circle center (1,0) and the line PB is 1, we have
That is to say,
It is easy to see that x0 > 2. Then the last equation can be simplified as
In a similar way,
Therefore,
Then we get
or Then we have
The equality holds when x0 −2 = 2; this means that x0 = 4 and So the minimum of
SΔPBC is 8.
2009 (Heilongjiang)
The Popularization Committee of CMS and the Mathematical Society of Heilongjiang Province were
responsible for the assignment of the competition problems in the first round test and the extra test.
Part I Short-Answer Questions (Questions 1—8, seven marks each)
Suppose that f(x) = and f(n) (x) = Then f(99) (1) = ________.
Solution We have
Therefore, f(99)(1) =
Given the line L: x + y − 9 = 0 and the circle M: 2x2 + 2y2 − 8x − 8y − 1 = 0, point A is on L
and points B, C are on M; BAC = 45° and the line AB is through the center of M. Then the
range of the x coordinate of point A is_________.
Solution Suppose that A (a, 9 − a). Then the distance from the center of M to the line AC is
On the other hand, since the line AC intercepts M, it follows that d the radius of
i.e.
The solution is 3 a 6.
On a coordinate plane there are two regions, M and N: M is confined by and N is
determined by the inequalities t x t + 1, 0 t 1. Then the size of the common area of M
and N is given by f(t) =________.
Solution As shown in the figure, we have
The inequality
holds for every positive integer n. Then the least positive integer of a is_______.
Solution Obviously,
We have
Then
(i) When k < 0, it is easy to see from that x1 + 1 > 0, x2 + 1 < 0, and kx1 > 0. Then the
(iii) We have
Suppose that these random events are independent of each other. Now, a traveler comes
into the station at 8:20. Then the mathematical expectation of his waiting time is_______ (round
to minute).
Solution The distribution table for the waiting times of the traveler is shown below.
Part II Word Problems (14 marks for Question 9, 15 marks each for Questions
10 and 11, 44 marks in total)
Suppose that the line l: y = kx + m (k, m are integers) intercepts an ellipse at two
Let bn = an+1 − βan. Then bn+1 = αbn(n = 1, 2, …). This means that {bn} is a geometric
sequence with the common ratio α. The first term of {bn} is
Then becomes a geometric sequence with the common ratio β, whose first term is
Therefore,
Then
— ,
We finally get
The character equation of {an} is λ2 − pλ + q = 0, which has roots α, β. Then we can write
down the general expression of {an} according to the following different situations:
The equality holds when 4x = 9(13−x) = x + 27. It is so for x = 9. Therefore, the maximum of y
is 11.
China Mathematical Competition (Complementary
Test)
2008 (Chongqing)
(50 marks) As shown in Fig. 1, ABCD is a convex quadrilateral with B + D < 180°, and P is
a moving point on the plane. Let
(1) Prove that P, A, B, C are concyclic when f (P) reaches the minimum.
Fig. 1
(2) Suppose that point E is on the are of the circumscribed circle O of ΔABC, satisfying
Therefore,
This completes the proof that P, A, B, C are concyclic when f(P) reaches the minimum.
(2) Denote ECB = α. Then ECA = 2α. By the sine theorem we have
By simplification,
That is to say,
That is to say
Then
Therefore,
We obtain EAC = 75° and AEC = 45°.
Since ΔADC is an isosceles triangle and we have CD = 1. Furthermore, ΔABC is an
isosceles triangle, so BC = and AB = 2. Then
We have BD = Therefore,
Solution II (1) As shown in Fig. 2, the line BD intercepts the circumscribed circle O of ΔABC at
point P0, which lies on BD because D is outside of O. Through A, C, D draw lines perpendicular to
P0A, P0C, P0D, respectively, and they constitute ΔA1B1C1 by intercepting with each other. It is easy
to see that P0 lies in ΔABC, as well as in ΔA1B1C1. Denoting the three inner angles of ΔACD by x, y,
z, respectively, we have
Fig. 2
Furthermore, from B1C1 P0A and B1A1 P0C, we have B1 = y. In a similar way, we have A1 =
x and C1 = z. It follows that ΔA1B1C1 ΔABC. Now let
That is to say, f(P0) f(M). Since M is an arbitrary point, we know that f(P) reaches the
minimum at P0, and at the same time P0, A, B, C are concyclic. This completes the proof.
(2) From (1) we know that the minimum of f(P) is
In the same way as is shown in the proof of (2) in Solution I, we find that both ΔADC and ΔABC
Furthermore, since ΔA1B1C1 ΔABC, AB1B = AB1C + BB1C = 90°, AB1BD is a rectangle.
Solution III (1) We discuss the problem on the complex plane, and regard points A, B, C as
complex numbers. Then by the triangle inequality we have
That is to say,
Then
The equality in holds only when the complex numbers (A − P)(C − B) and (C − P)(B−A) are in
the same direction. This means that there is a real λ > 0 such that
That is to say,
Therefore,
which means that the angle of rotation from to is equal to that from to It follows
that P, A, B, C are concyclic.
The equality in holds only when B, P, D are collinear and P lies on the segment BD. This
means that f(P) reaches the minimum when P lies on the circumscribed circle of ΔABC and P, A, B, C
are concyclic.
(2) From (1) we know that f(P)min = BD × CA. The following steps are the same as those in the
proof of (2) in Solution I.
(50 marks) Let f(x) be a periodic function with periods T and 1, satisfying 0 < T < 1. Prove that:
(1) If T is a rational number, there exists a prime p such that is also a period of f(x);
(2) If T is irrational, there exists a sequence of irrational numbers {an}, satisfying 1 > an >
an+1 > 0(n = 1, 2, …) and each an is a period of f(x).
Solution (1) T is a rational number, and there exist positive integers m, n such that and
(m, n) = 1. There are two integers a, b such that ma + nb = 1. It follows that
is also a period of f(x). Furthermore, m 2 because 0 < T < 1. Then m = pm′, p being a prime.
It is easy to know by induction that each an is irrational and 0 < an < 1. On the other hand, we
(50 marks) Suppose that ak > 0, k = 1,2, …, 2008. Prove that if and only if > 1, there is a
sequence {xn} satisfying
(1) 0 = x0 < xn < xn+1, n = 1, 2, 3, …;
(2) exists;
(3) xn − xn−1 = n = 1, 2, 3, ….
Solution Proof of necessity: Assume that there exists {xn} satisfying (1)–(3). Notice that the
expression in (3) can be written as
As x0 = 0, we then have
From (2) we are able to define b = Let n → ∞ in the above expression. Then we have
Therefore, > 1.
and there then exists a unique 0 < s0 < 1 such that f(s0) = 0. Now, define xn = n ∈ N. It is
easy to see that {xn} satisfies (1) and
2009 (Heilongjiang)
(50 marks) As shown in the Fig. 1, M, N are the midpoints of arcs respectively, which
are on the circumscribed circle of an acute triangle ΔABC ( A < B). Through point C draw
PC || MN, intercepting the circle Γ at point P. I is the inner center of ΔABC. Extend line PI to
intercept Γ at point T.
Fig. 1
(1) Prove that MP × MT = NP × NT;
(2) For an arbitrary point Q(≠A, T, B) on arc (not containing C), denote the inner centers of
ΔAQC, ΔQCB by I1, I2, respectively. Prove that Q, I1, I2, T are concyclic.
Solution (1) As shown in Fig. 2, join NI, MI. Since PC || MN and P, C, M, N are concyclic, PCMN is
an isosceles trapezoid. Therefore, NP = MC, PM = NC.
Join AM, CI. Then AM intercepts CI at I. We have
Fig. 2
Therefore, MC = MI. In the same way, NC = NI. Then NP = MI, PM = NI.
This means that MPNI is a parallelogram. Therefore, SΔPMT = SΔPNT, for the two triangles
having the same base and height.
On the other hand, TNP + PMT = 180°, as P, N, T, M are concyclic. Then we have
Therefore, MP × MT = NP × NT.
(2) As shown in Fig. 3, we have NCI1 = NCA + ACI1 = NQC + QCI1 = CI1N.
Therefore, NC = NI1. In the same way, MC = MI2.
From MP × MT = NP × NT we get
Fig. 3
From (1) we know that MP = NC, NP = MC. Then
Furthermore,
Let
Therefore,
Let
Then
Therefore, xn < xn−1 < … < x1 =
Furthermore,
Consequently,
There are infinite many positive integers m k such that and l are relatively prime.
Therefore,
If p | k!, there exists integer α 1 such that pα | k! but pα+1 k!. Then pα+1 |l(k!).
We have
Therefore, and Since pα | k!, we get . The proof is completed.
Solution II Let m = k + t × l × (k !)2, where t is any positive integer. The following proof steps
are similar to those in Solution I, and are omitted.
(50 marks) Suppose that a matrix of nonnegative entries,
(O) For any column (k = 1, 2,…, 9) in P, there exists i ∈ {1, 2, 3} such that
Prove that:
(i) For different i (= 1, 2, 3), ui = min{xi1, xi2, xi3} comes from different columns in S;
By ( i ), we know that the first column of S contains a ui, and it must be u1 = x11; the second
column also contains a ui, assuming that it is u2 = x22, and then it must be u3 = x33.
Define M = {1, 2,…, 9} and
Obviously, I = {k ∈ M | x1k > x11, x3k > x32}, and 1, 2, 3 I. Since x18, x38 > 1 x11, x32, we
have 8 ∈ I. Therefore, I ≠ ø. Consequently, ∃ k* ∈ I such that x2k* = max{xzk | k ∈ I}. Of course, k* ≠
1, 2, 3.
We now prove that
We claim that, for any k ∈ M, there exists i ∈ {1, 2, 3} such that xik. Otherwise, we would
have xik > min{xi1, xi2}, i = 1, 3 and x2k > x2k*, contradicting the definition of k*.
Therefore, S′ has property (O).
Secondly, we prove the uniqueness of S′. Assume that ∃ k0 ∈ M such that
Since has property ( O ), we know that, for k* ∈ M, there exists i ∈ {1, 2, 3} such that .
As k* ∈ I, and by , , it must be x2k* = x2k.
On the other hand, S also has property ( O ). Then, in a similar way, we get x2k = x2k*.
Therefore, k* = k. This completes the proof.
Chinese Mathematical
Olympiad
2009 Qionghai, Hainan
First Day
(0800 – 1230; January 9, 2009)
Given an acute triangle PBC, PB ≠ PC. Let points A, D be on sides PB and PC, respectively. Let
M, N be the midpoints of segments BC and AD, respectively. Lines AC and BD intersect at point
O. Draw OE AB at point E and OF CD at point F.
(1) Prove that if A, B, C, D are concyclic, then
(2) Are the four points A, B, C, D always concyclic if EM × FN = EN × FM? Prove your answer.
(Posed by Xiong Bin)
Proof (1) Denote by Q, R the midpoints of OB, OC, respectively. It is easy to see that
and
Because of that A, B, C, D are concyclic, and Q, R are the midpoints of OB, OC, and we have
Then
So
We know that A, B, C, D are not concyclic in this case because PB ≠ PC, so the answer is “false”.
Find all pairs (p, q) of prime numbers such that pq | 5P + 5q. (Posed by Fu Yunhao)
Solution If 2 | pq, we suppose that p = 2 without loss of generality, and then q | 5q + 25. By
Fermats theorem we have q | 5q − 5, so q | 30, where (2, 3) and (2, 5) are solutions [(2, 2) does not
fit].
If 5 | pq, we suppose that p = 5 without loss of generality and then 5q | 5q + 55. By Fermats
theorem we have q | 5q−1 −1,
so q | 313, where (5, 5) and (5, 313) are solutions.
Otherwise, we have pq | 5p−1 + 5q−1, and so
a contradiction of p ≠ 2. So k > l.
But we have k < l by a similar argument – a contradiction. Therefore, all possible pairs of
primes (p, q) are (2, 3), (3, 2), (2, 5), (5, 2), (5, 5), (5, 313) and (313, 5).
Let m, n be integers with 4 < m < n, and A1A2…A2n+1 be a regular 2n + 1 polygon. In addition,
let P = {A1, A2,…, A2n+1}. Find the number of convex m-gons with exactly two acute internal
angles whose vertices are all in P. (Posed by Leng Gangsong)
Solution Notice that if a convex m-gon whose vertex set is contained in P has exactly two acute
angles, they must be at consecutive vertices: for otherwise there would be two disjoint pairs of sides
that take up more than half of the circle each. Now assume that the last vertex, clockwise, of these
four vertices that make up two acute angles is fixed; this reduces the total number of regular m-
gons 2n + 1 times and we will later multiply by this factor.
Suppose that the larger arc that the first and the last of these four vertices make contains k
points, and the other arc contains 2n − 1 − k points. For each k, the vertices of the m- polygon on
the smaller arc may be arranged in ways, and the two vertices on the larger arc may be
arranged in (k − n − 1)2 ways (so that the two angles cut off more than half of the circle).
The total number of polygons given by k is thus (k − n − 1)2 × . Summation over all
k and a change of variable shows that the total number of polygons (divided by a factor of
Second Day
(0800 – 1230; January 10, 2009)
Let n 3 be a given integer, and a1, a2,…, an. be real numbers satisfying .
for 1 k n. So
When n is odd,
When n is even,
So
First of all, there are ways to choose three among n colors, and ways to choose three
vertices to form a triangle, so if the questions condition is fulfilled, all the triangles should have a
different color combination (a 1—1 correspondence). Note that any two segments of the same color
cannot have a common endpoint.
As each color combination is used in exactly one triangle, for each color there should be exactly
triangles which have one side in this color, and so there should be exactly lines of this
color. Therefore, n is odd.
Now we give a construction method for any odd n.
As the orientation of the vertices does not really matter, we may assume that the polygon is a
regular n-polygon. First, color the n sides of the polygon in the n distinct colors. Then, for each side,
color those diagonals that are parallel to this side into the same color.
In this way, for each color, there are n diagonals colored in this color, and notice that each of
these diagonals is of a different length.
Besides, for any two triangles with all vertices in, we shall prove that they should have different
color combinations. Suppose that, on the contrary, they have exactly the same three colors as their
sides. Because of that all the sides with the same line are parallel, and the two triangles must be
similar. For their vertices to be in the same circle, they must be the same, but this is a contradiction
of . This completes the proof.
Given an integer n 3, prove that there exists a set S of n distinct positive integers such that
for any two distinct nonempty subsets A and B of S, the numbers
are two coprime composite integers and denotes the sum of all elements of a finite set X,
and |X| denotes the cardinality of X. (Posed by Yu Hongbing)
Proof Let f (X) be the average of elements of the finite number set X. First of all make n different
primes P1, P2,…, pn which are all bigger than n, and we prove that for any different nonempty
In fact, we can suppose that and without loss of generality. Every element
of B can be divided by P1, so P1 | n! f(B). But A has exactly one element which cannot be divided by
P1, so we find that n! f (A) cannot divided by P1 ( note that P1 > n), and therefore n ! f(A) ≠ n ! f(B),
which follows f(A) ≠ f(B).
Second, let S2 = {n!x:x ∈ S1}. Then f(A) and f(B) are different positive integers when A, B are
different nonempty subsets of S2.
In fact, it is easy to see that there exist two sets A1, B1 which are different nonempty subsets of
S1, and f(A) = n! f(A1), f(B) = n!f(B1) holds. We get f(A) ≠ f(B) from f(A1) ≠ f(B1), and f(A), f(B) are
positive integers from | A |, | B | n and their elements are all positive.
Then, let K be the largest element of S2. We prove that for every two distinct subsets A, B of the
set S3 = {K !x + 1: x ∈ S2}, f(A) and f(B) are coprime integers which are both larger than 1.
In fact, it is easy to see that there exist two sets A1, B1 which are different nonempty subsets of
S1, and f(A) = n!f(A1) + 1, f(B) = K!f(B1) + 1 holds. Obviously, f(A) and f(B) are different integers
which are both larger than 1. If they have common divisors, let p be a prime common divisor of
them without loss of generality. Clearly, we have p | (K ! • | f(A1) − f(B1) |). We get 1 | f(A1) − f(B1)
| ) K by 0 < f(A1), f(B1) K and f(A1) ≠ f(B1), so p K, which follows p | K!f(A1), and then p | 1 −
a contradiction.
Lastly, let L be the largest element of S3. We prove that for every two distinct nonempty subsets
A, B of the set S4 = {L! + x:x ∈ S3}, f(A) and f(B) are two composites which share no common
divisors.
In fact, it is easy to see that there exist two sets A1, B1 which are different nonempty subsets of
S3, and f(A) = L! + f(A1), f(B) = L! + f(B1) holds. Obviously, f(A) and f(B) are different integers
which are both larger than 1. Because of that, L is the largest element of S3, and we have f(A1) | L!
and f(A1) | f(A). We find that f(A) is composite by f(A1) < f(A). For a similar reason, f(B) is composite
too. If they have common divisors, let p be a prime common divisor of them without loss of
generality. It is obvious that p | (L! • | f(A1) − f(B1) |). We get 1 | f(A1) − f(B1) | L by 0 < f(A1),
f(B1) L and f(A1) ≠ f(B1), so p L, which follows p | f(A1) and p | f(B1) — a contradiction of the
fact that f(A1) and f(B1) are coprime. This completes the proof.
2010 (Chongqing)
First Day
(0800 – 1230; January 22, 2010)
As shown below, two circles Γ1, Γ2 intersect at points A, B, one line passing through B
intersects Γ1, Γ2 at points C, D, another line passing through B intersects Γ1, Γ2 at points E, F,
and line CF intersects Γ1, Γ2 at points P, Q, respectively. Let M, N be the middle points of arc
PB and arc QB, respectively. Prove that if CD = EF, then C, F, M, N are concyclic. (Posed by
Xiong Bin)
Proof Draw lines AC, AD, AE, AF, DF. From ADB = AFB, ACB = AEF and the assumption CD
= EF; one obtains ΔACD ΔAEF. So we have AD = AF, ADC = AFE and ADF = AFD. Then
ABC = AFD = ADF = ABF; AB is the bisector of CBF. Draw lines CM, FN. Since M is the
middle point of arc PB, CM is the bisector of DCF, and FN is the bisector of CFB. Then BA, CM,
FN have a common intersection, say, at I. In the circles Γ1 and Γ2, one has CI × IM = AI × IB, AI ×
IB = NI × IF, according to the theorem of power with respect to circles. So NI × IF = CI × IM, and
C, F, M, N are concyclic.
Given an integer k 3 and a sequence {an} that satisfies ak = 2k and for each n > k,
Prove that an − an−1 is a prime for infinitely many n. (Posed by Zhu Huawei)
Proof Suppose that al = 2l k. Let p be the least prime divisor of k − 1. Then
and thus
Then al+p−1 −al+p−2 = (2l + 2p − 2) − (2l + p − 2) p is a prime number, al+p−1 = 2(l + p − 1). From
the discussion above, we know that there are infinitely many l k, such that al = 2l and al+p−1
−al+p−2 = p is the least prime divisor of l − 1.
Let a, b, c be complex numbers such that | az2 + bz + c | 1 for all complex numbers z with | z
| 1. Find the maximum of |bc|. (Posed by Li Weigu)
Solution Write f(z) = az2 + bz + c. We first prove that
Assume that f(z) = a(z − a)(z − β). For any z, | z | <1, if α = β, one of the two intersection points
of the line through α and the origin with the unit circle is closer to α than z is; if α ≠ β, the line
through z and perpendicular to the line through α, β intersects the unit circles at two points, one of
which is closer to α, β than z is, respectively. So holds.
For any complex number z, | z | = 1, it is obvious that
So | ab |max = | be |max. Write a′z2 + b′z + c′ = eiα f (eiβz). One can choose real numbers α, β
such that a′, b′ are positive real numbers, so one can assume that a, b 0 without loss of generality
Without loss of generality we can assume Im c γ 0 (otherwise take a map, θ → − θ). For any
An example of is
Second Day
(0800 – 1230; January 23, 2010)
Given two integers m, n greater than 1, and integers a1 < a2 < … < am, prove that there exists
then prove that there must exist at least one good team if a1 + a2 + … + an n2 + 2n + 1.
Assume that there is no good team. Then each ai ∈ {n + 1, n + 2, n + 3}, otherwise there is a
good team of one point at any Ai with ai n + 4. Suppose that the number of n + 1, n + 2 and n + 3
‘s among a1, a2,…, an, are x, y, z respectively. We will show that x z. Since n2 + 2n + 1 > n(n + 2),
z 1. If z = 1, then x 1, otherwise all ai n + 2 and G = {A1, A2, …, An} is a good team. If z 2,
the z points with n + 3 cards divide the circle into z arcs (no two of these z points are adjacent).
Since there is no good team by assumption, there is at least one point on each arc with n + 1 cards.
So x z, and the total number of cards at A1, A2,…, An is
which is a contradiction. Thus, we have proven that when the number of cards at O is less than n +
1, there exists a good team. We use operation (1) on each point of a good team; the number of cards
at O is increased while the number of cards at each A1, A2, …, An is still no less than n + 1. We can
reiterate until there are at least n + 1 cards at O.
Let a1, a2, a3, b1, b2, b3 be pairwise distinct positive integers such that
holds for all positive integers n. Prove that there exists a positive integer k such that bi = kai
for all i = 1, 2, 3. (Posed by Chen Yonggao)
Proof Suppose that r is any positive integer. Since there are infinitely many primes, there is a
prime p, such that
Eliminate n from , :
From , we have
and thus
Because 0 < < 1 (1 i t + 1), take the limit r → + ∞, and we have 0 1, a contradiction.
So xt+1 = yt+1, and then = 1, 2,…. By induction the lemma holds
for all positive integer s.
Now return to the proof of the problem. Since a1, a2, a3, b1, b2, b3 are distinct,
or
1, 2, 3. From 2b1 + b2 = and the assumption of the problem (with n = 1), 2a1 + a2 |
First Day
(0800 – 1230; March 31, 2009)
Let D be a point on side BC of triangle ABC such that CAD = CBA. A circle with center O
passes through B, D, and meets segments AB, AD at E, F, respectively. Lines BF and DE meet
at point G. M is the midpoint of AG. Prove that CM AO. (Posed by Xiong Bin)
Proof As shown in Fig. 1, extend EF and meet BC at point P, and join and extend GP, which meets
AD at K and the extension of AC at L.
Fig. 1
As shown in Fig. 2, let Q be a point on AP such that PQF = AEF = ADB.
It is easy to see that A, E, F, Q and F, D, P, Q are concyclic respectively. Denote by r the radius
of O. By the power of a point theorem,
Fig. 2
Similarly,
By , , we have AP2 − AG2 = PO2 − GO2, which implies that PG AO. As shown in Fig. 3,
applying Menelaus’ theorem for ΔPFD and line AEB, we have
yields
Fig. 3
Since B, D, F, E are concyclic, we have DBA = EFA. Since CAD = CBA, we have CAF =
EFA, which implies that AC || EP. Thus,
then
Indeed, by assumption, 2iai i(ai+1 + ai−1) holds for i = 1, 2,…, n − 1. For any given positive
integer 1 l n − 1, summing the above inequality over i = 1, 2,…, l, we have (l + 1)al lal+1, i.e.
In what follows J we show that for any i, j, k ∈ {1, 2,…, n}, if i > j, then
Indeed, the above inequality is equivalent to 2ik2 (j + k) > 2jk2 (i + k), i.e. (i − j)k3 > 0, which is
clearly true.
Now, we are going to show inequality . We shall start by estimating the lower bound of aiaj for
1 i < j n.
Since
Since p is a prime number, there are at most s solutions to the above equation, thanks to
Lagranges theorem. Thus, there are at most s nis with ni+1 − ni, = s, i.e. holds.
and hence
Proof of lemma. Let v be the smallest integer not less than , i.e. v satisfies
hence
and thus
(Here we have used a well-known result: the function (a t b) attains its maximum
at t = a or b.)
By and , we see that uv and (u + 1)v are two distinct integers in the interval I = [ab, (a + 1)
then it follows from the above equality that is a square of a rational number.
If S is empty, then mn is a square of an integer. Since a + b > 2 , we have ab + a + b + 1 >
ab + 2 + 1, i. e. > + 1, which means that there is at least an integer in
the interval [ , . As a result there is a perfect square in the interval [ab, (a + 1)
(b + 1)). Suppose that r2 ∈ [ab, (a + 1) (b + 1)) (r ∈ Z), and let S′ = {r2}. Then is a square of a
rational number.
Let m be an integer greater than 1, and let n be an odd number with 3 n < 2m. Numbers ai, j
(i, j ∈ N, 1 i m, 1 j n) satisfy:
(1) For every 1 j n, a1,j, …, am, j is a permutation of 1, 2,…, m;
(2) | ai, j − ai, j+1 | 1 for every 1 i m, 1 j n − 1.
Thus,
Case 2: None of , and is m, and by the condition (1) there exists 1 i1 m, i1 ≠ i0,
such that = m. It easily follows from the conditions (1) and (2) that = m − 1, = m. It
follows again from the condition (2) that
Thus,
Combining the above two case, we have M (2l + 1) m − l2. On the other hand, consider
We shall show that this table of numbers satisfies the required conditions in the problem.
For any 1 i m, 1 j n − 1, if m | 2i + j, then
if m | 2i + j, then
The condition (2) is verified.
We next show that the condition (1) is also fulfilled. In fact, it suffices to show that for any
integers 1 j n and 1 k m, there exists an integer 1 i m such that ai, j = k.
If j ≡ k (mod 2), since 1 j n, 1 k m and n < 2m, we have − 2m <k − j <m, and
therefore −m <m, and note that is an integer. Thus, at least one of and + m
is in the set {1, 2,…, m}; taking this number to be i will do the job.
If j k (mod 2), again since 1 j n, 1 k m and n < 2m, we have
and therefore
Prove that in an arithmetic progression consisting of 40 distinct positive integers, at least one
of the numbers cannot be written as 2k + 3l, where k, l are nonnegative integers. (Posed by
Chen Yonggao)
Proof Suppose on the contrary that there exist 40 distinct positive integers in arithmetic
progression such that each term can be written as 2k + 3l, and denote this sequence by a, a + d, a +
2d,…, a + 39d, where a, d are positive integers. Let
In what follows, we first show that at most one of a + 26d, a + 27d,…, a + 39d cannot be
written as 2m + 3l or 2k + 3n (k, l are nonnegative integers).
Suppose that a + hd cannot be written as 2m + 3l or 2k + 3n, for some 26 h 39. Then, by
assumption, a + hd = 2b + 3c for some nonnegative integers b, c. By the definition of m and n, it is
clear that b m, c n. Since a + hd cannot be written as 2m + 3l or 2k + 3n, we have b m − 1, c
n − 1.
If b m − 2, then
a contradiction.
If c n − 2, then
also a contradiction.
It follows that b = m − 1, c = n − 1, which implies that at most one of a + 26d, a + 27d,…, a +
39d cannot be written as 2m + 3l or 2k + 3n.
In these 14 numbers, at least 13 numbers can be written as 2m + 3l or 2k + 3n. By the
pigeonhole principle, at least 7 numbers can be written in the same form. We shall discuss two
cases.
Case 1: There are 7 numbers in the form of 2m + 3l, denoted by
where l1 < l2 < … < l7. Thus, are the 7 terms of an arithmetic progression with 14
terms and the common difference d. However,
a contradiction.
Case 2: There are 7 numbers in the form of 2k + 3n, denoted by
where k1 < k2 < … < k7. Thus are the 7 terms of an arithmetic progression with 14
terms and the common difference d. However,
a contradiction.
It follows from the above arguments that our assumption at the very beginning is false, which
completes the proof.
2010 (Yingtan, Jiangxi)
First Day
(0800 – 1230; March 27, 2010)
For acute triangle ABC with AB > AC, let M be the midpoint of side BC and P a point inside
ΔAMC such that MAB = PAC. Let O, O1 and O2 be the circumcenters of ΔABC, ΔABP and
ΔACP respectively. Prove that line AO bisects segment O1O2. (Posed by Xiong Bin)
Proof I As shown in Fig. 1, draw the circumcircles of ΔABC, ΔABP and ΔACP, respectively. Let the
extension of AP meet O at D, join BD, and draw the line tangent to O at A, intersecting O1 and
O2 at E and F respectively.
It is clear that ΔAMC
ΔABD, hence
we have .
Consequently,
Fig. 1
and, similarly,
It follows that
Draw the perpendicular lines O1 E′ AE with foot E′, and O2F′ AF with foot F′. Since E′, F′ are
the midpoints of AE, AF respectively, it follows from that A is the midpoint of E′F′.
In the right-angled trapezoid O1 E′ F′ O2, AO is the extension of the median, and hence it bisects
the segment O1O2.
Proof II As shown in Fig. 2, draw segments AO1, OO1, AO2 OO2. Denote by Q the intersection of
AO and O1O2. Then
Fig. 2
where .
Since OO1Q = BAP = CAM, and OO2Q = CAP = BAM, it follows that
and thus
Note that M is the midpoint of BC, and therefore O1Q = QO2, i.e. line AO bisects segment O1O2.
Let A = {a1, a2, …, a2010} and B = {b1, b2,…, b2010} be two sets of complex numbers, such
that the equality
holds for every n = 1, 2,…, 2010. Prove that A = B. (Posed by Leng Gangsong)
Proof Let Sk = and . We first show by induction that Sk = k for k = 1, 2,…, 2010.
Setting n = 1 in the given equality, we have 2009S1 = 2009 1, and hence S1 = 1. Assume that
Sj = j for j = 1, 2,…, k − 1, where 2 k 2010; we are going to show that Sk = k.
By the binomial expansion theorem, we have
Similarly, we have
Since
that 2010 is not a power of 2, i.e. 2010 −2k−1 ≠ 0 ). This completes the inductive proof that Sk = k
for all k = 1, 2,…, 2010.
Set
The right hand sides of equations and are equal, and so are their left hand sides, i.e. A =
B.
Let n1, n2, …, n26 be pairwise distinct positive integers, satisfying:
(1) In the decimal representation of each ni, each digit belongs to the set {1, 2 };
(2) For any i, j, nj cannot be obtained from ni by adding some digits on the right.
Find the least possible value of , where S (m) denotes the sum of all digits of m in
decimal representation. (Posed by Fu Yunhao)
Solution Given two positive integers a, b in decimal representationt we say a contains b if a can
be obtained from b by adding some digits on the right. We first prove a lemma.
Lemma Let n1 n2, …, nr be pairwise distinct positive integers with digit 1 or 2. If none contains
another then the number of nis with S(ni) t is at most Ft, where t is an arbitrary positive integer
and Ft is a Fibonacci number satisfying F1 = 1, F2 = 2, Fn+2 = Fn+1 + Fn (n 1).
Proof of lemma. We induct on t. It is clear for t = 1, 2 (when t = 2, 1 and 11 cannot both
appear). Suppose that the lemma is true for all positive integers less than t (t 3); we shall prove
that it is also true for t. Suppose that without loss of generality S(n1), S (n2),…, S(nl) are all the
numbers with the sum of digits t, where n1, n2,…, ni start with 1 and nj+1, nj+2,…, nl start with 2.
If one of n1, n2,…, nj is 1, then j = 1 Ft−1, otherwise by deleting the first digit of n1, n2,… nj we
obtain j positive integers with none containing another and the sum of digits t − 1, and thus we
again have j Ft−1 by the inductive hypothesis. Analogously, we have l − j Ft−2, and therefore l
Ft−1 + Ft−2 = Ft, i.e. the lemma is also true for t. The proof of the lemma is completed.
Going back to the original problem, we consider a more general question. Replacing 26 by m,
denote the least possible value of by f(m). Fix m 3, and let n1, n2, …, nm be a set of
numbers satisfying the conditions in the problem which attains the minimum f(m). Without loss of
generality, assume that = S(n1) and n1 is maximum among all these numbers attaining
the maximum digital sum. Since m 3, n1 contains at least two digits.
If the last digit of n1 is 1, replace n1 by , which is not one of n2, n3,…, nm, otherwise n1
would contain some ni. Notice that , n2,…, nm again. satisfy the conditions in the problem, for
if ni contains for some i 2, then S(ni) > S(n1) and ni > n1, a contradiction. Now
does not contain any of n3, …, nm, otherwise n1 would contain that number. If one of n2, …, nm
Adding 1 or 2 yields n2, n1, and we must have n3 = 100 • . Now S(n3) = S(n1) and n3 > n1, a
contradiction to the choice of n1. So , n3, …, nm satisfy the conditions in the problem, and
therefore the sum of their digits is at least f(m − 1). Thus,
Let u be such that Fu−1 < m Fu. By the lemma, there are at most Fu−1 of S(n1), S(n2),…,
S(nm) less than or equal to u − 1, so S(n1) u, and
These are pairwise distinct numbers consisting of digits 1 and 2, with total digital sum 7 × 8 + 7 ×
5 + 8 × 5 + 6 × 8 = 179. And there is none containing another. In fact, if x contains y, since their
digital sum is either 6, 7 or 8, and a number with digital sum 8 ends up with 2, it follows that x has
exactly one more digit than y. However, deleting the last digit of d1, d2,…, d5 and e1, e2,…, e5 yields
b1, b2,…, b5, and deleting the last digit of c1, c2,…, c8 yields a1, a2,…, a8, none of which is in this set
of 26 numbers.
(1)
(2) If one colors arbitrarily some vertices into red, there exists a red vertex ν, such that f(ν) is
not greater than the number of vertices adjacent to ν that are not colored into red.
Let m(G) be the number of good maps f. Show that if each vertex of V is adjacent to a least one
other vertex, then n m(G) n!. (Posed by Qu Zhenhua)
Proof Given an ordering τ = (ν1, ν2, …, νn) on the vertices in V, we associate a map fτ: V → Z as
follows: fτ(ν) is equal to the number of vertices in V that are ordered preceding ν. We claim that fτ is
good.
Each edge is counted exactly once in , for an edge e ∈ E with vertices u, ν ∈ V such that
u is ordered before ν τ; then e is counted once in fτ(ν). Thus,
For any nonempty subset A ⊆ V of all red vertices, choose ν ∈ A with the most preceding
ordenings in τ. Then by definition, fτ(ν) is not greater than the number of vertices adjacent to ν that
are not colored into red. We have verified that fτ is good.
Conversely, given any good map f:V → Z, we claim that f = fτ for some ordering τ of V.
First, let the red vertice set A = V. By the condition (2) in the problem, there exists ν ∈ A such
that f (ν) 0, and denote one of such vertices by ν1. Assuming that we have already chosen ν1,…,
νk from V, if k < n, set the red vertice set A = V − {ν1,…, νk}. By the condition (2) in the problem,
there exists ν ∈ A such that f(ν) is less than or equal to the number of vertices in ν1, …, νk that are
adjacent to ν. Denote one of such vertices by νk+1. Continuing in this way, we order the vertices by
τ = (ν1, ν2, …, νn). By the construction we have f(ν) fτ(ν) for any ν ∈ V. By the condition (1) in the
problem, we have
we have p, i.e. + p.
On the other hand, + p is even and greater than E, so it does not appear before , and
therefore + p, which is even − a contradiction.
Step 2: We prove that all even numbers are in this sequence.
Suppose on the contrary that 2k is not in this sequence and is the smallest such even number.
Let { } be the subsequence of {an} consisting of all even numbers. By step 1, it is an infinite
sequence. Since ( , 2k) > 1 and 2k {an}, we have 2k by definition.
However, is infinite — a contradiction. Thus, {an} contains all even numbers.
Step 3: We prove that {an} contains all odd numbers greater than 1.
Suppose on the contrary that 2k +1is an odd integer greater than 1which is not in {an}, and is
the smallest such number. By step 2, there is an infinite subsequence of {an} consisting of
even numbers that are multiples of 2k + 1. Arguing analogously as in step 2, we have 2k +
1, i = 1, 2, …, a contradiction.
We have shown that {an} contains all positive integers except 1.
Given integer n 2 and real numbers x1, x2,…, xn, in the interval [0, 1], prove that there exist
real numbers a0, a1,…, an satisfying simultaneously the following conditions:
(1) a0 + an = 0;
(2) |ai | 1, for every i = 0, 1,…, n;
(3) |ai − ai−1 | = xi, for every i = 1, 2,…, n. (Posed by Zhu Huawei)
Proof For any a ∈ [0, 1), define a sequence generated by a as follows: a0 = a for 1 i n,
ai, = ai−1 − xi if ai−1 0, and ai = ai−1 + xi if ai−1 < 0.
Set f(a) = an. It is easy to show by induction that | ai | 1 for every 0 i n.
If there exists a ∈ [0, 1) such that f(a) = −a, consider the sequence generated by a, a0 = a, a1,…,
an = f(a) = −a. Clearly, this sequence satisfies the conditions (1) and (3). By the recursive relation, it
also satisfies the condition (2). Thus, it suffices to show that there exists a ∈ [0, 1) such that f(a) =
−a.
For any a ∈ [0, 1), we say that a is a breaking point if at least one term in its generating
sequence is 0. Since every breaking point is of the form , where ti = − 1, 0, 1, there are
finitely many breaking points.
Clearly, 0 is a breaking point; label all breaking points in increasing order by 0 = b1 < b2 < … <
bm < 1.
We first prove that for 1 < k < m − 1, f(a) = f(bk) + (a − bk) for every a ∈ [bk, bk+1).
Consider bk, bk+1 and their generating sequences. Assume that q0 = bk, q1, q2, …, qn is the
generating sequence of bk, and r0 = bk+1, r1, r2, …, rn is the generating sequence of bk+1. Suppose
that r1 is the first term of equal to 0. Construct a sequence as follows:
It is clear that the sequence satisfies s0 = bk+1; and for 1 i n, si = si−1 − xi if si−1 >
0, and si = si−1 + xi if si−1 0.
We prove by induction that qisi 0 and si − qi = bk+1 − bk. The conclusion is obviously true for
i = 0. Assume that it holds for i − 1. Then qi−1 si−1 0 and si−1 −qi−1 = bk+1 − bk > 0, which
implies that qi−1 0, si−1 > 0, or qi−1 < 0, si−1 0. In the former case, qi = qi−1 − xi, si = si−1 − xi,
and thus si − qi = si−1 −qi−1 = b++1 − bk. Similarly, in the latter case, we have si − qi = b++1 − bk.
If qisi < 0, then qi < 0 < si. Set b′ = bk+1 − si = bk + (− qi) ∈ (bk, bk+1), and consider the generating
sequence of b′, u0 = b′, u1,…, un. It is easy to show by induction that sj − uj = s0 −u0 = si for any 0
j i (qj−1 and sj−1 both add or subtract xj for j < i; uj lies between qj−1 and qj−1, so the recursive
relation is the same). Then ui = si − si = 0, i.e. b′ is a breaking point − a contradiction to bk, bk+1
being two consecutive breaking points. Therefore, qisi 0. By induction we have verified that qisi 0
and si −qi = bk+1 − bk for all 0 i n.
Since f(bk) = qn, f(bk+1) = rn =− sn, we have f(bk) + f(bk+1) = bk − bk+1. It follows from the
above argument that, for any bk < b′ < bk+1, the generating sequence of b′ has the same recursive
relation as and , and hence
Let . Then
Olympiad
2008 (Zhongshan, Guangdong)
(1) Can one divide the set {1, 2,…, 96} into 32 subsets, each containing three elements, and
the sums of the three elements in each subset are all equal?
(2) Can one divide the set {1, 2,…, 99} into 33 subsets, each containing three elements, and
the sums of the three elements in each subset are all equal? (Posed by Liu Shixiong)
Solution (1) No. As
and 32 48 × 97.
(2) Yes. The sum of the three elements in each set is
We can divide 1, 2, 3,…, 66 into 33 pairs, such that the sums of these pairs form an arithmetic
sequence:
For n odd, take these triples as A1, A2,…, An; then they satisfy the required condition. So n can
be any odd number.
The real polynomial φ(x) = ax3 + bx2 + cx + d has three positive roots, and φ(0) < 0. Prove
that
Because x1, x2, x3 are all greater than 0, (x1 − x2) 0. That is to say,
Let , as
we have . So
and we reach a contradiction. Hence, min {λ, μ} φ, which implies that amin φ.
On the other hand, for any a ∈ (1, φ), we take any t ∈ such that .
Inside the square ABCD we can choose a point P so that S1 = b, , S4 = 1 −b. Then
we have
joining the midpoints of opposite sides of PQRS, we find the maximum value of . (Posed by
Xiong Bin)
Now draw lines P1E, S1E, and denote by M, N the midpoints of DP, DS. Then
and
and also
Suppose that the convex quadrilateral ABCD satisfies AB = BC, AD = DC. E is a point on AB,
and F on AD, such that B, E, F, D are concyclic. Draw ΔDPE directly similar to ΔADC, and
ΔBQF directly similar to ΔABC. Prove that A, P, Q are collinear. (Posed by Ye Zhonghao)
Proof Denote by O the center of the circle that passes through B, E, F, D. Draw lines OB, OF, BD.
Fig. 1
In ΔBDF, O is the circumcenter, so BOF = 2 BDA; And ΔABD ΔCBD, so CDA = 2 BDA.
Hence, BOF = CDA = EPD, which implies that the isosceles triangles
Fig. 2
To this end, we draw ΔBAA′ ΔBQF ΔABC (see Fig. 3). Then BAA′ = ABC, which implies
that A′A || BC. As ABCD is not a rhombus, AD is not parallel to BC, which implies that A′, A′, D are
not collinear, i.e. A is not on the locus. Hence, Q is on the line AP only when B, E, F, D are concyclic.
And when ABCD is a rhombus (see Fig. 4), for any E and F the corresponding points P and Q are
always on the diagonal AC.
Fig. 3
Fig. 4
Suppose that the sequence of positive numbers x1, x2,…, xn,… satisfies (8x2 − 7x1) = 8 and
Find positive real number a such that when x1 > a one has x1 > x2 > … > xn,>…, and when 0
< x1 < a one does not have such monotonicity. (Posed by Li Shenghong)
Solution By , we have
i. e.
Fig. 1
Fig. 2
The same argument shows that each of these three columns is composed of two letters in an
alternative way, and a fortiori so is every column.
Now we calculate the total number of different harmonic chessboards. If the leftmost column is
composed of two letters (eg. C and M), we see immediately that all the odd-numbered columns are
composed of these two letters, while the even numbered columns are composed of the other two
letters. The letter in the top square of each column can be either of the two letters that compose
this column; we check easily that it is a harmonic chessboard. Therefore, we have different
ways to choose the two letters of the first column, and 22008 ways to determine the letter in the top
square of each column. Hence, we get 6 × 22008 configurations to make each column composed of
two letters in an alternative way. We have also 6 × 22008 configurations to make each line composed
of two letters in an alternative way.
Then we need to subtract from the sum the configurations that are counted twice, i. e. the
configurations that are alternative on each line and each column. Obviously, any such configuration
is in one-to-one correspondence to the 2 × 2 square at the upper-left corner, which gives 4! = 24
different ways. Hence, we get the above result.
For positive integer n, let . Prove that there are infinitely many
odd numbers and even numbers in the sequence f1 f2,…. ([x] represents the biggest integer
that does not exceed x.) (Posed by Zuming Feng)
Proof We use the dyadic representations of and :
First, we prove that there are infinitely many even numbers by contradiction. Suppose that
there are only finitely many even numbers in the sequence. Then there exists a positive integer N,
and for every positive integer n > N, fn must be odd. We consider n1 = N + 1, n2 = N + 2,…. We
observe that in dyadic representation
apparently gn and fn have the same parity. Hence, for n > N, gn is even. We observe also that in
dyadic representation
and this would imply the rationality of , which is impossible. Hence, there are
infinitely many odd numbers in the sequence.
2009 (Xiamen, Fujian)
First Day
(0800 – 1200; August 13, 2009)
Show that there are only finitely many triples (a, b, c) of positive integers satisfying the
equation abc = 2009(a + b + c). (Posed by Ieng Tak Leong)
Solution There are at most six permutations for any three numbers x, y, z. It suffices to show that
there are only finitely many triples (a, b, c), with a b c, of positive integers satisfying the
equation abc = 2009(a + b + c). It follows that abc 2009 × (3a) or bc 2009 × 3 = 6027. Clearly,
there are finitely many pairs (b, c) of positive integers satisfying the equation b c 6027 and for
each fixed pair of integers (b, c) there is at most one positive integer a satisfying the equation abc =
2009(a + b + c) (because it is a linear equation in a).
A right triangle ABC, with BAC = 90°, is inscribed in the circle Γ. The point E lies in the
interior of the arc (not containing A), with EA > EC. The point F lies on the ray EC with
EAC = CAF. The segment BF meets Γ again at D (other than B). Let O denote the
circumcenter of the triangle DEF. Prove that the points A, C, O are collinear. (Posed by Bian
Hongping)
Solution Let M and N be the feet of the perpendiculars from O to the lines DF and DE,
respectively. Because O is the circumcenter of the triangle DEF, the triangles EOD and ODF are
both isosceles with EO = DO = FO. It follows that
Because = 90°, the quadrilateral OMDN is concyclic, from which it follows that
NDM + NOM = 180° or BDN = NOM. Because ABED is concyclic, we have BAE = BDE.
Combining the above equations together, one has
from which it follows that AEOF is concyclic. Let ω denote the circumcircle of AEOF. Because O lies
on the perpendicular bisector of the segment EF, O is the midpoint of the arc (on ω), implying
that AO bisects EAF and A, C, O are collinear.
Let n be a given positive integer. In the coordinate plane, consider the set of the points
and we have
Indeed, for every positive integer n, we are going to prove that for 1 m n and
we have
We assume the result is true for m = k < n, and we consider m = k + 1. By cyclic symmetry, we
may assume that either
or
From here, we can prove the inequality by direct expansions on both sides. Instead, we proceed
in a slightly different way. By very simple expansions, we can see that
because the right-hand side has positive extra summands 2AB, 2A2B, 2AB2. Applying twice [ (first
with (A, B) = (a, b) and then with (A, B) = (ab + a + b, c)]yields .
The circle Γ1, with radius r, is internally tangent to the circle Γ2 at S. The chord AB of Γ2 is
tangent to Γ2 at C. Let M be the midpoint of the arc (not containing S), and let N be the
foot of the perpendicular from M to the line AB. Prove that AC × CB = 2r × MN. (Posed by Ye
Zhonghao)
Solution It is well known that S, C, M are collinear. Indeed, consider the dilation centered at S that
sends Γ1 to Γ2. Then the line AB is sent to the line l parallel to AB and tangent to Γ2, i. e. the line
tangent to Γ2 at M (the midpoint of ). Thus, this dilation sends C (the points of tangency of line
the AB and Γ1) to M (the points of tangency of the line l and Γ2), from which it follows that S, C, M
are collinear.
By the power-of-point theorem, we have AC × CB = SC × CM. It suffices to show that
Set MCN = α. Then SCA = α. By the extended sine law, we have = sin α. In the right
triangle MNC, we also have sin α = Combining the last two equations, we obtain .
(We can also derive by observing that the triangles MNC and CDS are similar.)
On a 10 × 10 chessboard, some 4n unit square fields are chosen to form a region R. This
region R can be tiled by n 2 × 2 squares. If R can also be tiled by a combination of n pieces of
the following types of shapes (with rotations allowed).
Second, we show that n must be even. We mark the (infinite) chessboard with × in the pattern
indicated in the right-hand-side figure. It is easy to see that each 2 × 2 covers exactly an even
number of crosses (either two or four crosses) and each duck covers exactly an odd number of
crosses (either one or three crosses). It follows that we must have an even number of ducks in R, i.e.
n is even.
Third, we show that n 2. If n = 2, then R can be tiled by two 2 × 2 squares. It is clear that
these two squares much share a common edge. Hence, we can have only two possibilities:
It is not difficult to see that is not possible to tile either of the above configurations by a
combinations of two ducks.
For positive integer n, an = . Compute the maximum value and the minimum
value of α1, α2, …, α 2009. (For real number x, [x] denotes the greatest integer less than or
equal to x.) (Posed by Wang Zhixiong)
Solution Let b0 = 0, b1 = 1, bn = 4bn—2 + bn—1 (n 2). Then
it follows that
The 8th China Western Mathematical Olympiad was held from October 30 to November 4,2008 in
Guiyang, Guizhou, China. The event was hosted by Guizhou Mathematical Society and HS affiliated
to Guizhou Normal University.
The competition committee comprised Zhu Huawei, Wu Jianping, Chen Yonggao, Li Shenghong,
Liu Shixiong, Feng Zhigang, Tang Lihua, Bian Hongping and Shi Xiaokang.
First Day
(0800 – 1200; November 1, 2008)
A sequence of real numbers {an} is defined by a0 ≠ 0, 1, a1 = l — a0, an+1 = 1 — an (1 — an), n
= 1, 2, …. Prove that for any positive integer n, we have
(Posed by Li Shenghong)
Proof From the given condition, we have
By mathematical induction, when n = 1 the proposition holds. Assuming that it holds for n = k,
then when n = k + 1 we have
(2)
(Posed by Bian Hongping)
Hence, is composite.
Given an integer m 2, and two real numbers a, b with a > 0 and b ≠ 0, the sequence {xn} is
such that x1 = b and Xn+1 = + b, n = 1, 2, …. Prove that:
(1) When b < 0 and m is even, the sequence {xn} is bounded if and only if abm—1 —2;
(2) When b < 0 and m is odd, or when b > 0, the sequence {xn} is bounded if and only if
It is obvious that the difference of any two consecutive terms of the sequence {xn} is increasing,
and hence it is not bounded.
When abm—1 — 2, mathematical induction is used to prove that each term of the sequence
{xn} falls on the interval [b, —b].
The first term b falls on the interval [b, —b]. Suppose that the term xn. satisfies the condition b
Thus, the sequence {xn} is bounded if and only if abm—1 > —2.
(2) When b > 0, each term of the sequence {xn.} is positive. So, we first prove that {xn} is
bounded if and only if the equation axm + b = x has positive real roots.
Suppose that axm + b = x has no positive real roots. In such a case, the minimum value of the
function p(x) = axm + b — x on the interval (0, + ∞) is greater than zero. Let t be the minimum
value. It follows that for any two consecutive terms of the sequence xn and xn+1, we have
. Thus, each succeeding term of the sequence {xn} is greater than the
preceding term by at least t. Hence, it is not bounded.
If the equation axm + b = x has positive real roots, let x0 be one of the positive real roots. Then,
by using mathematical induction, we prove that each term of the sequence {xn} is less than x0.
Firstly, the first term b is less than x0. Suppose that xn < x0 for a particular n. By virtue of the fact
that axm + b is increasing on the interval [0, + ∞), it can be established that
on the interval (0, + ∞) is not greater than 1, whereas the minimum value of
can be determined by mean inequality, i.e.
When b < 0, and m is odd, let yn = — b > , showing that the sequence
{xn} is bounded if and only if the sequence {yn} is bounded. Thus, by using the above reasoning, it
can be proven that (2) holds.
Second Day
(0800 – 1200; November 2, 2008)
Four frogs are positioned at four points on a straight line such that the distance between any
two neighboring points is one unit of length. Suppose that every frog can jump to its
corresponding point of reflection, by taking any one of the other three frogs as the reference
point. Prove that there is no case where the distances between any two neighboring points,
where the frogs stay, we all equal to 2008 unit of length. (Posed by Liu Shixiong)
Proof Without loss of generality, we may think of the initial positioning of the four frogs as being
on the real number line at points 1, 2, 3, and 4. Further, it can be established that the frogs at odd
number positions remain at odd number positions after each jump, and likewise for frogs at even
number positions. Thus, no matter after how many jumps, there are two frogs remaining at odd
number positions while the other two frogs remain at even number positions. Therefore, in order
that the distances between any two neighboring frogs are all equal to 2008, all the frogs need to
stay at points which are either all odd or all even, which is contrary to the actual situation. Hence,
the proposition is proven.
Given x, y, z ∈ (0, 1) satisfying
Therefore, i.e.
and thus . Following this, we have , and equality holds when .
and then .
Furthermore, using the fact that the sum of any two sides of a triangle is longer than the third
side, we have, for any 1 i n,
i.e.
The 91th China Western Mathematical Olympiad was held from October 26 to November 1,2009 in
Kunming, Yunnan, China. The event was hosted by Yunnan Mathematical Society and HS affiliated
to Yunnan Normal University.
The competition committee comprised Xiong Bin, Wu Jianping, Chen Yonggao, Li Shenghong,
leng Tak Leong, Liu Shixiong, Feng Zhigang, Li Jianping, Bian Hongping and Li Qiusheng.
First Day
(0800 – 1200; October 29, 2009)
Let M be a subset of R obtained by deleting finitely many real numbers from R. Prove that for
any given positive number n, there exists a polynomial f(x) of degree n such that all its
coefficients and its n real roots are in M. (Posed by Feng Zhigang)
Proof Let T = {| x | ∈ R | x M}, which is a finite set by definition, and a = max T. Choose any real
number k > max {| a |, 1}; then — k T and hence —k ∈ M.
For any positive integer n, define f(x) = k (x + k)n. Then it follows from k > 1 that deg f(x) = n,
and the coefficient of xmin f(x) is given by
Hence, all the coefficients of f(x) are not in T, and thus are in M. As the roots of f(x) are all –k with
multiplicity n, they are in M. It follows that the polynomial f(x) = k(x + k)n satisfies the condition.
Let n 3 be any given integer. Determine the smallest positive integer k, for which there
exists a set A of k real numbers and n real numbers x1, x2, …, xn, which are distinct from each
other such that
For (2), we have xn. = x2, which is possible. For (1), it follows that
Hence,
and the point M lies on the circumcircle of ΔABC. Join the segments PB, PC, PE and PF. It follows
from AE = AF that
With and , one has . From PBF = PCE, one has ΔPBF ΔPCE, and hence
PFB = PEC, and therefore PFA = PFA. Consequently P, A, E and F are concyclic.
Prove that for any given positive integer k, there exist infinitely many positive integers n, such
that the numbers are all composite. (Posed by Chen Yonggao)
Proof For any given positive integer k, choose positive integer m sufficiently large such that 2m +
3m — k > 1. Consider the following k integers:
all of which are larger than 1. From each of these integers, pick a prime factor: p1, p2, …, pk, and let
where t is an arbitrary positive integer. For any fixed integer i (1 i k), one has 2nt ≡ 2m (mod
pi). In fact, if pi = 2, then the result is obvious. Assuming that pi ≠ 2, it follows from Fermats little
theorem that
are all composite. As t is arbitrarily chosen, there are infinitely many such positive integers
satisfying the conditions above.
Second Day
(0800 – 1200; October 30, 2009)
Let {xn} be a sequence such that x1 ∈ {5, 7}, and xn+1 ∈ , for n = 1, 2, ….
Determine all the possible cases of the last two digits of x2009. (Posed by Ieng Tak Leong)
Solution Let n = 2009. Then we have the following three cases:
(1) If , then xn ≡ 7 (mod 100).
Since both 5 and 7 are oddt xk (1 k n) all are odd. 1 (mod 4), i.e.
for some positive integer k.
If k, m 0, it follows from mathematical induction that
and hence
Prove that ΔAMN ΔABC if and only if the line AD passes through the circumcenter of ΔABC.
(Posed by Li Qiusheng)
Proof Join the segments XY and DX. It follows from the given conditions that B, P, D, X are
concyclic, and C, Y, Q, D are concyclic. Then
And it follows from AMX = ANY = 90° that ΔAMC ΔANY, so MAX = NAY and
which is equivalent to the fact that the line AD passes through the circumcenter of ΔABC.
Hence, ΔAMN ΔABC if and only if AD passes through the circumcenter of ΔABC.
There are n (n > 12) students participating in a mathematics contest. The examination paper
consists of 15 fill-in-the-blank questions. For each question, the score of a correct answer is
1point, and no point will be awarded if the answer is wrong or left blank. After analyzing all the
possible cases of score distributions of these n students, one finds out that if the sum of total
scores of any 12 students is not less than 36 points, then there are at least 3 students among
these n students who answer at least 3 identical questions correctly. Determine the smallest
possible value of n. (Posed by Liu Shixiong)
Solution The smallest n is 911. We divide the proof into two parts:
(1) We first prove that n = 911 satisfies the conditions. If each student answers at least 3
questions correctly, then for any student there are ways for him to have exactly 3
correct answers. If there are 911 students participating in the contest, it follows from the
pigeonhole principle that there are at least 3 students having 3 identical correct answers.
If there is a student X whose score is not more than 2, then the number of remaining students
with a score not more than 3 cannot exceed 10; otherwise t pick any 11 of these students together
with X, and the sum of their total scores is less than 36 points. Then there are more than 911 — 11
= 900 students in the rest t such that each of them has a score less than 4. Since = 4, and 4 ×
900 > 455 × 2, there are at least 3 students answering 3 identical questions correctly.
(2) There are 910 students participating in the contest. Divide them into 455 =
groups, and there are exactly 2 students in each group. In each group, both students have the
identical answers with only 3 correct answers indexed by the group label.
Let a1, a2, …, an (n 3) be real numbers satisfying a1 + a2 + … + an = 0, and
Determine the smallest λ (n), such that for any k ∈ {1, 2, …, n}, one has
(Posed by Li Shenghong)
follows: and
that λ (n) .
Next, suppose that {ak} is a sequence satisfying the two conditions stated in the questions. We
will prove that the following inequalities hold:
and hence
Similarly, for any fixed k, where k {1, n}, and for any J ∈ {1, 2, …, k}, we have
Therefore, we have
First Day
(0800 – 1200; July 28, 2007}
Find the integer solutions of the function x2 — 2xy + 126y2 = 2009. (Posed by Zhang
Pengcheng)
Solution Suppose that the integers x, y satisfy
Second, if AC = AD, let O be the center of the circle (B, C, D, E are on the circle). Then O is on
the perpendicular bisector (AH) of CD. Let F is the symmetric point of B by the line AH. Then F is on
the circle O. AB ≠ EA, so DE ≠ DF, and thus E, F are not the same points. Now one can see that
ΔAFD ΔABC, with AB = DE, BC = EA, and one can get ΔAED ΔCBA, and so ΔAED ΔDFA,
which indicates AED = DFA, and therefore A, E, F, D is concyclic. This means that A is on the
circle O, and A, B, C, D are concyclic.
so
We can get
On the other hand, the following example shows that n can be 24.
Consider a circle whose perimeter is 12, and the 12 red points are on the circle with equal
distance. The number of chords with red endpoint is . If the length of the minor arc to a
chord is k, then say “the chord belongs to k.” So we have only six kinds of chords, and the number
of chords belonging to 1, 2, …, 5 is 12, and that belonging to 6 is 6
If three chords belonging to a, b, c (a b c) can be the sides of a triangle, then a + b = c or a
+ b + c = 12. So the triangles (a, b, c) ∈ {(1, 1, 2), (2, 2, 4), (3, 3, 6), (2, 5, 5), (1, 2, 3), (1, 3, 4), (1,
4, 5), (1, 5, 6), (2, 3, 5), (2, 4, 6), (3, 4, 5), (4, 4, 4)}.
Now we give an example:
The number of (1, 2, 3) triangles is 6, whose vertices are
The number of (4, 4, 4) triangles is 3, whose vertices are {1, 5, 9}, {2, 6, 10}, {3, 7, 11}.
The number of (2, 4, 6) triangles is 3, whose vertices are {4, 6, 12}, {8, 10, 4}, {12, 2, 8}.
So the minimum n is 24.
Second Day
(0800 – 1200; July 29, 2009}
The set of the permutation X = (x1, x2, …, x9) of 1, 2, …, 9 is A. X ∈ A, and let f(X) = x1 + 2x2
+ 3x3 + … + 9x9, M = {f(X) | X ∈ A}. Find the value of |M|. (Posed by Xiong Bin)
Solution We prove for n 4. If the permutations Xn = (x1, x2, …, xn.) of 1, 2, …, n consist of a set
For n = 4, by arranging inequality, one can see the smallest number of M is f({4, 3, 2, 1}) = 20,
and the biggest number is f({1, 2, 3, 4}) = 300 Because
we have, .
Suppose that the statement is true for n — 1 (n 5). In the case of n, for a permutation Xn—1 =
(x1, x2, …, xn—1) of 1, 2, …, n – 1, let xn = n; then we get a permutation (x1, x2, …, xn—1, n) of 1, 2,
…, n, and so
According to the supposition, the value of can be every integer number in the interval
According to the supposition, the value of can be every integer number in the interval
Fig. 2
Let the points M, N be the intersections
of the line OI and the circle O; then
i.e. R2 — d2 = 2Rr.
Now draw the tangents DE, DF from D to the circle I. The points E, F are on the circle O. Then
DI is the bisector of EDF. It is enough to prove that EF is tangent to the circle I.
Let P be the intersections of the line DI and the circle O. Then P is the midpoint of the arc EF,
and
and so
As I is on the bisector of EDF, we can see that I is the incenter of DEF [because PEI = PIE =
(180° —
Cauchys inequality
and
when we have .
Second, prove that f 0; when x = 1, y = z = 0, we have f = 0.
In fact, one can see that
So fmin = 0 and .
On a piece of 8 × 8 graph paper, at least how many grids should be taken off, and we cannot
cut out a “T” which has five grids as shown in Fig. 1? (Posed by Sun Wen-Hsien)
Fig. 1
Fig. 2
Fig. 3
Fig. 4
See Fig. 3: cut the 8 × 8 graph paper into five areas. We need to take off two grids from the
center areas, otherwise we can get a “T” with five grids in the area. Because the two grids with “×”
are not equivalent, one is in the corner, and the other is in the center — only one grid is taken off,
and we can get a “T” with five grids, as shown in Fig. 4.
For the four corner areas, we prove that at least three grids should be taken off in every area to
ensure that we cannot get a “T” with five grids in the area.
Fig. 5
For example, in the upper right corner, the “T” below as shown in Fig. 5 should be taken off one
grid, and the grids over the “T” should be taken off the “×” grid. From the “T” below having five
cases, we can check that if only two grids are taken off, we can get a “T” with five grids, which is
shown as follows:
First Day
(0080 – 1200; August 17, 2010)
Let a, b, c ∈ {0, 1, 2, …, 9}. The quadratic equation ax2 + bx + c = 0 has a rational root. Prove
that the three digit number is not a prime number.
Solution If = p is a prime number, and the roots of the equation f (x) = ax2 + bx + c = 0 are
rational numbers, then b2 — 4ac is a square number, x1, x2 are negative, and f(x) = a(x — x1)(x —
x2).
So p = f(10) = a(10—x1)(10 — x2), and we get 4ap = (20a — 2ax1)(20a — 2ax2).
Since x1, 2 , we see that 20a — 2ax1, 20a — 2ax2 are integers. Now p | 20a
— 2ax1 or p | 20a — 2ax2, and we can suppose that p | 20a — 2ax1; then p 20a — 2ax1, and 4a >
20a — 2axz, which is a contradiction to x2 being negative.
For any set A = {a1, a2, …, am}, let P(A) = a1a2 … am. In addition, let and let A1, A2,
For n ∈ {1, 2, …, 2010}, we have n2010 ≡ 1(mod 2011) (by Fermats little theorem), and 2010! ≡
—1(mod 2011) (by Wilsons theorem), so
This means that f(x) ≡ 0(mod 2011) have 2010 roots, but the degree of f(x) is 2009. Using
Langranges theorem, we can see that the coefficients can all be divided by 2011.
The incircle of the triangle ABC touches BC at D and AB at F, and intersects the line AD again
and thus
Let a and b be positive integers such that 1 < a < b < 100. If there exists a positive integer k
such that ab | (ak + bk), we say that the pair (a, b) is good. Determine the number of good
pairs.
Solution One can see that when k = 1, if a 2, then ab > a + b; and if a = 1, then b |(b + 1). So k
> 2.
Now, suppose that (a, b) = d, a = sd, b = td, then (s, t) = 1, with t > 1. By std2 | dk. (sk. + tk), it
follows that st | dk—2 (sk + tk), as (st, sk. + tk) = 1, we have st |dk—2, and the prime divisors of st are
the divisor of d.
If s or t has a prime divisor p bigger than 11, then p | d, and so p2 | a or p2 | b, but p2 > 100; this
is a contradiction. Thus, the prime divisor belongs to {2, 3, 5, 7}.
Let T be the set of the prime divisors of st. Then T ≠ {3, 7}, otherwise one of a or b is bigger
than (or equal to) 7 × 3 × 7 > 100, as similarly, T ≠ {5, 7}. So T is one of the following sets:
(1) When T = {3, 5}, we have d = 15, and s = 3, t = 5, and only one good pair (a, b) = (45, 75);
(2) When T = {2, 7}, we have d = 14, and (s, t) = (2, 7) or (4, 7), and only two good pairs, (a, b)
= (28, 98) or (56, 98);
(3) When T = {2, 5}, we have d = 10 or 20, and the coincide (s, t) = (1, 10), (2, 5), (4, 5), (5, 8)
or (2, 5), (4, 5). There are six good pairs (a, b);
(4) When T = {2, 3}, we have d = 6, 12, 18, 24, 30, and the coincide (s, t) = (1, 6), (1, 12), (2,
3), (2, 9), (3, 4), (3, 8), (3, 16), (4, 9), (8, 9), (9, 16) or (1, 6), (2, 3), (3, 4), (3, 8) or (2, 3), (3, 4)
or (2, 3), (3, 4) or (2, 3). There are 19 good pairs (a, b);
(5) When T = {7}, we have (s, t) = (1, 7), d = 7 or 14. There are two good pairs (a, b);
(6) When T = {5}, we have (s, t) = (1, 5), d = 5, 10, 15 or 20. There are four good pairs (a, b);
(7) When T = {3}, we have (s, t) = (1, 3), (1, 9) or (1, 27), and the coincide d ∈ {3, 6, …, 33},
{3, 6, 9} or {3}. There are 15 good pairs (a, b);
(8) When T = {2}, we have (s, t) = (1, 2), (1, 4), (1, 8), (1, 16) or (1, 32), and the coincide d ∈
{2, 4, …, 50}, {2, 4, …, 24}, {2, 4, …, 12}, {2, 4, 6} or {2}. There are 47 good pairs (a, b).
So we have 1 + 2 + 6 + 19 + 2 + 4 + 15 + 47 = 96 good pairs (a, b) satisfied.
Second Day
(0080 — 1200; August 18, 2010)
ABC is a triangle with a right angle at C. M1 and M2 are two arbitrary points inside ABC, and
M is the midpoint of M1 M2. The extensions of BM1, BM and BM2 intersect AC at N1, N and N2
respectively.
Prove that
Solution Let H1, H2, H be the projection from M1, M2, M to the line BC. Then
Now suppose that BC = 1, BH1 = x, BH2 = y. Then
which is equivalent to .
This is obviously true.
Let N* be the set of positive integers. Define a1 = 2, and for n = 1, 2, …,
Prove that .
Solution Since
.
This means that when n = 1, the conclusion is right.
Suppose that for n k — 1 (k 2), the conclusions are right, for n = k, from
Prove that .
Solution Let
Since
whose k term is
i.e. the sum of the elements from the k row of the graph, k = 1, 2, …, n, we find that
If every chord belongs to only one triangle, then the maximum . But if there 9
triangles such that every 2 of them have no common side, then there are 27 vertices of this triangle,
and there is a point belonging to 4 triangles (suppose that it is A8), whose opposite sides are chords
with endpoints of A1, A2, …, A7, and so there is a point Ak that is the endpoint of two triangles, and
the two triangles have a common side A8 Ak, so r 8.
On the other hand, the following example shows that r can be 8: from the picture, the triangle
(1, 2, 8), (1, 3, 3 6), (1, 4, 7), (2, 3, 4), (2, 5, 7), (3, 5, 8), (4, 5, 6), (6, 7, 8) is satisfied. So the
maximum of r is 8.
First Day
(0900 — 1330; July 15, 2010}
Let n be a positive integer and let a1, a2, …, ak (k 2) be distinct integers in the set {1, …, n}
such that n divides ai (ai+1 — 1) for i = 1, …, k—1. Prove that n does not divide ak (a1 — 1).
(Posed by Australia)
Proof We first prove by induction that for any integer 2 i k, n | a1 (ai — 1).
If i = 2, we have n | a1 (a2 —1) by assumption. Suppose that n | a1 (ai — 1) for some 2 i k —
1; then
i.e. n | a1 (ai+1 —1). By the method of induction, n | a1 (ai—1) holds for every integer 2 i k. In
particular, we have n | a1(ak — 1).
Since a1 (ak —1) — ak (a1 — 1) = ak—a1 is not divisible by n (because a1 and ak are distinct
elements in {1, …, n}), we conclude that ak (a1 — 1) is not divisible by n.
Let ABC be a triangle with circumcenter O. The points P and Q are interior points of the sides
CA and AB, respectively. Let K, L and M be the midpoints of the segments BP, CQ and PQ,
respectively, and let Γ be the circle passing through K, L and M. Suppose that the line PQ is
tangent to the circle Γ. Prove that OP = 0 Q. (Posed by Russia)
Proof Clearly, the line PQ touches the circle Γ at the point M. By the theorem of the tangent chord
angle, we have QMK = MLK. Since the points K, M are the midpoints of the segments BP and PQ
respectively, KM || BQ, we get QMK = AQP. Thus, MLK = AQP, and similarly MKL = APQ.
As a result, we see that ΔMKL and APQ are similar, and thus
Since the points K, L and M are the midpoints of the segments BP, CQ and PQ respectively, we
have
i.e.
or, equivalently,
As k is arbitrary, we must have d2—d1 = 0, i.e. d2 = d1, denoted by d for both d1 and d2. Let b
.
Since sk+1 > sk, we get sk+1 = Sk + 1, i. e. {sn.} is an arithmetic progression, which is what we
want. In what follows, we assume that d > 1.
We shall prove that Sk+1 — Sk = C for any positive integer k. Supposing on the contrary that it
is not true, we discuss two cases.
Case 1: There exists a positive integer k such that Sk+1 — Sk < c. Since Sk+1 — si = c0 are
positive integers, we may assume that si+1 — si = c0 attains the minimum value for some i; then
we have
(here we have used the minimality of c0). Marking a comparison with , we have c0 > c, a
contradiction.
Case 2: There exists a positive integer k such that sk+1 — Sk > c. Since sk+1 — sk., are integerst
and for any k,
we may assume that sj+l — sj = c1 attains the maximum value for some j; then
we have
(here we have used the maximality of c1). Marking a Comparison with , we have c1 c, a
contradiction.
We have verified that sk+1 — sk = c for any positive integer k, i.e. {sn} is an arithmetic
progression.
Second Day
(0900 — 1330; July 16, 2010}
Let ABC be a triangle with AB = AC. The angle bisectors of CAB and ABC meet the sides
BC and CA at D and E respectively. Let K be the incenter of the triangle ADC. Suppose that
BEK = 45°. Find all possible values of CAB. (Posed by Belgium)
Solution Since AD and BE are the angle bisectors of CAB and ABC, their intersection point
is the incenter I. Join CI; then CI is the angle bisector of ACB. Since K is the incenter of ΔADC, K
lies on the segment CI.
Let BAC = α, since AB = AC, AD BC, we have
So we have
On the other hand, since K is the incenter of ΔADC, DK bisects IDK. It follows from the
property of the angle bisector that
Thus,
or 1 equivalently,
or
and therefore
When α = 90°,
Since IEC = DCK, ΔICE and ΔDCK are similar, which implies that
It follows that ΔIDC and ΔEKC are similar, so EKC = IDC = 90°, and hence
Combining the above arguments, we conclude that all possible values of CAB are 60° and 90°.
Determine all functions f from the set of positive integers to the set of positive integers such
that, for all positive integers a and b, there exists a nondegenerate triangle with sides of
lengths a, f(b) and f(b + f(a) – 1). (A triangle is nondegenerate if its vertices are not collinear.)
(Posed by France)
Solution The only f with the required property is f(n) = n for all n ∈ N*.
By assumption and discreteness of integers, we see that for any positive integers a, b,
Let . For any integer n > M, denote by n0 the unique positive integer
satisfying
Then
a contradiction. As a result, we have f(t) for any t ∈ N*. Then t = f(f(t)) f(t) t, and all
inequalities become equalities, i.e. f(n) = n for any n ∈ N*.
It is not hard to check that f(n) = n for all n ∈ N* satisfies the required property, thus
completing our conclusion that the only solution to the problem is f(n) = n for all n ∈ N*.
Let a1, a2, …, an be distinct positive integers and let M be a set of n — 1 positive integers not
containing s = a1 + a2 + … + an. A grasshopper is to jump along the real axis, starting at the
point 0 and making n jumps to the right with lengths a1, a1, a2, …, an in some order. Prove that
the order can be chosen in such a way that the grasshopper never lands on any point in M.
(Posed by Russia)
Proof We proceed by induction on n. When n = 1, M is empty, and the result is obvious.
When n = 2, M does not contain at least one of a1, a2, and the grasshopper can first jump the
number that is not in M, then the other number.
Let m 3 and assume that the result is true for any n < m, n ∈ N*. We shall prove that the
result also holds for n = m. Suppose on the contrary that there exist m distinct positive integers a1,
a2, …, am and a set M of m — 1 numbers, such that the grasshopper cannot finish the jumping as
required in the problem.
Suppose that the grasshopper can jump at most k steps to the right with lengths of distinct
numbers in a1, a2, …, am, such that the landing points are never in M. Since M contains only m − 1
numbers, the grasshopper can always take its first step. If the grasshopper can jump m — 1 steps, it
can also jump the last step since M does not contain a1 + a2 + … + an, and therefore 1 k m —
2.
We choose such k steps with a minimum total length (if there is a tie, just choose any one that
attains the minimum), denote the lengths of these k steps by b1, b2, …, bk, and let but, bk+1, bk+2 …,
bm be the remaining numbers in a1, a2, …, am in increasing order. Clearly,
Then bk+1 ∈ A. For any bi ∈ A, if we remove bi from b1, b2, …, bk+1, the sum of the remaining k
numbers is not in M, and since
and k < m, by the inductive hypothesis there exists an ordering c1, c2, …, ck of these remaining
numbers, such that
are not in M. Thus, c1, c2, …, ck is also a possible length of k jumps, and by the choice of b1, b2, …,
bk we have
belongs to M (otherwise, since k < m — 2, bm is different from b1, b2, …, bk+1, and the grasshopper
can take k + 1 jumps). For 1 i t — 1, the numbers
are pairwise distinct and greater than b1 + b2 + … + bk + bm, and hence there are at least t — 1
numbers of M greater than b1 + b2 + … + bk + bm. Summing up, M contains at least
First Day
(0900 — 1330; July 7, 2010}
Determine all functions f : R→R such that the equality
holds for all x, y ∈ R. (Here [z] denotes the greatest integer less than or equal to z.) (Posed by
France)
Solution The answer is f(x) = C (a constant function), where C = 0 or 1 C < 2.
Setting x = 0 in , we have
for all z ∈ R.
It is easy to check that f(x) = C (a constant function) with C = 0 or 1 C < 2 satisfies the
required property of the problem.
Let I be the incenter of the triangle ABC and let Γ be its circumcircle. Let the line AI intersect
Γ again at D. Let E be a point on the are and F a point on the side BC such that
Finally, let G be the midpoint of the segment IF. Prove that the lines DG and EI intersect on Γ.
(Posed by Hongkong)
Proof Let Ia be the center of the described circle of the triangle ABC with respect to the side BC.
Then D is the midpoint of the segment IIa, DC || Ia F and GDA = FIaA.
To prove that the intersection point P of the lines DG and EI lies on Γ, i.e. A, E, D, P are
concyclic, is equivalent to proving that GDA = IEA, or similarly FIaA = IEA.
By the assumption BAF = CAE, we have ΔABF ΔAEC, and hence
Since
and D is not divisible by p. Set n = pD — g(k); then n + g (k) = pD, and thus
i.e. p | k — l.
If p | g(k) — g(l) but p2 does not divide g(k) — g(l), choose an integer D as above and set n = p3
D — g(k). Then g(k) + n = p3 D is divisible by p3, but not by p4, and
is divisible by p, but not by p2. As with the above argument, we have p | g(n) + k and p | g(n) + l,
and therefore
If q = —1, then g(n) 0 for n (1) + 1, a contradiction. Therefore, we must have q = 1 and
for any n ∈ N, where g(1) — 1 0. Set g(1) — 1 = C (a constant). Then g (n) = n + C, where C is a
nonnegative integer.
Second Day
(0900 — 1330; July 8, 2010)
Let P be a point inside the triangle ABC. The lines AP, BP and CP intersect the circumcircle Γ
of the triangle ABC again at the points K, L and M respectively. The tangent to Γ at C intersects
the line AB at S. Suppose that SC = SP. Prove that MK = ML. (Posed by Poland)
ProofWithout loss of generality, we assume that CA > CB. Then S lies on the extension of AB.
Suppose that the line SP intersects the circumcircle of the triangle ABC at E, F, as in the figure. By
assumption and the power of a point theorem, we have
to mean that there is a finite sequence of operations on the boxes Bi, Bi+1, …, Bi+k initially
containing bi, bi+1, …, bi+k coins respectively that results in containing
Lemmo 1 For every positive integer a, 1re have (a, 0, 0) → (0, 2a, 0).
Proof of lemma 1: We prove by induction on k a that (a, 0, 0)→(a—k, 2k, 0).
Since (a, 0, 0)→(a — 1, 2, 0)→(a — 1, 21, 0), the assertion is true for k = 1. Suppose that the
assertion is true for some k < a; then
and thus
The assertion is also true for k + 1 ( a). By the method of induction. Lemma 1 is proven.
Lemma 2 For every positive integer a, we have (a, 0, 0, 0)→(0, Pa, 0, 0), where
and the assertion is true for k = 1. Suppose that the assertion is true for some k < a; then
and therefore
i.e. the assertion is also true for k + 1 a. By the method of induction, we have proven Lemma 2.
We have
and
and thus the number of coins in the box B4 is greater than A. Therefore, by performing operations of
type 2, we have
Then we get
Let a1, a2, a3, … be a sequence of positive real numbers. Suppose that for some positive
integer s, we have
for all n > s. Prove that there exist positive integers l and N, with l s and such that an = a1 +
an—l for all n N. (Posed by Iran)
Proof By assumption, for each n > s, an. can be written as,
Suppose that is the last step in obtaining . Then i1 + i2 > s, and is reformulated as
On the other hand, if the indices i1, …, ik satisfy , we set sj = i1 + … + ij. By , we have
If bk = 0 for every k = 1, 2, …, s, then for every positive integer n, bn. = 0, and hence an = nm
for every n, and the conclusion follows.
Then there are at most nonzero terms in otherwise x < , and hence there are
only finitely many such representations for x.
Thus, for every t = 1, 2, …, l, the sequence
is increasing, and takes only finitely many values, and hence it is constant eventually, i.e. there is N
such that {bn} is periodic for n > N with period l; in other words,
i.e.