The USSR Olympiad Problem Book
I'm working through the problems in this book in a (vain) attempt to prove I'm as smart as a good Soviet high school student in 1935. The complete title is The USSR Olympiad Problem Book: Selected Problems and Theorems of Elementary Mathematics, first published in English in 1962 and available in a cheap Dover reprint or at archive.org.[1] The problems are unconventional with a pedigree going back to the 1930s and are targeted at advanced high school students — they require little to no advanced machinery, but a great deal of ingenuity to solve in most cases. I wrote up about half of them up to #106 and then skipped ahead in order to have one for each chapter to show below, always trying hard to solve a problem, maybe over days, before peeking at the hint in the back or the solution when severely pressed. The questions take up the first 73 page of the book, the solutions the last 349 pages. Sometimes a problem is just plain out of reach, even after some effort, in other cases unappetizing for some reason — only then is a look at the solution in order.
The prefaces contain some information about how the problems were chosen and emphasize the tradition of competitive mathematical olympiads in the Soviet Union that led to the International Mathematical Olympiads of our day[2] (similar exams in Hungary were also notable). A review of the book in Science in 1962 speaks of the Soviet practice of Mathematical Circles, extracurricular high school clubs where students studied these and similar problems often in collaboration with university mathematicians (university students established such clubs as well). The purpose was to create a hothouse environment for promising young scientists and to identify talent — also, if my experience is any guide, to have fun in trying to conquer these bears. The preface to the English edition states:
[This book] contains 320 problems — a few of them merely recreational and thought-provoking, but most of them seriously engaged with solid and important mathematical theory, albeit the preparational background is assumed to be elementary. The problems are from algebra, arithmetic, trigonometry, and number theory, and all of them emphasize the creative aspects of these subjects. The material coordinates beautifully with the new concepts which are being emphasized in American schools, since the "unconventional" designation attributed to the problems by the original authors means that they stress originality of thought rather than mere manipulative ability and introduce the necessity for finding new methods of attack.
For some problems, solutions can be suggested by examples with low integers. If asked for Fibonacci numbers that are multiples of 10,000, for example, look first for those that are a multiple of 10 (#95), then 100, and so on. Python and WolframAlpha can be helpful — thousands of Fibonacci numbers can be stored in a Python array with a few lines of code or (considering how quickly they grow), Fibonacci numbers mod 10,000. The book has twelve chapters and following are a characteristic problem from each chapter. I recommend trying a problem cold, giving it some time and trying a few strategies.
If not coming, left-click the problem's "hint" link for a pop-up window giving some suggestions. If still a mystery, right-click the "solution" link to show the answer in a separate tab. Note that * means hard, ** very hard.
1. Introductory Problems (1-14).
\(\#14.\)* (a) On which of the two days of the week, Saturday or Sunday, does New Year's Day fall more often?
(b) On which day of the week does the thirtieth of the month fall more often? (hint, solution)
2. Alterations of Digits in Integers (15-26).
\(\#19.\) (a) Find the smallest integer whose first digit is 1 and which has the property that if this digit is transferred to the end of the number the number is tripled.
(b) With what digits is it possible to begin a (nonzero) integer such that the integer will be tripled upon the transfer of the initial digit to the end? Find all such integers. (hint, solution)
3. The Divisibility of Integers (27-71).
\(\#28.\) (a) Prove that \(35 \; | \; (3^{6n} - 2^{6n})\) for every positive integer \(n\).
(b) \(120 \; {\large{|}} \; \left(n^5 - 5n^3 + 4n\right)\) for every integer \(n\).
(c)* \(56,786,730 \; | \; mn(m^{60} - n^{60})\) for all integers \(m, n\). (hint, solution)
4. Some Problems from Arithmetic (72-109).
\(\#95.\)* Let \(\{u_n\}_{n=0}^{\infty} = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, \cdots\) be the Fibonacci numbers (indexing starts at 0, so \(u_0 = 0, \; u_1 = 1, \; u_2 = 1, \cdots\)). Is there a number terminating with four zeroes among the first 100,000,001 Fibonacci numbers? (hint, solution)
5. Equations Having Integer Solutions (110-130).
\(\#117.\) (a) Prove that the only solution in integers of \(x^2 + y^2 + z^2 = 2xyz\) is \(x = y = z = 0\).
(b) Find the integers \(x, y, z, v\) such that \(x^2 + y^2 + z^2 + v^2 = 2xyzv\). (hint, solution)
6. Evaluating Sums and Products (131-159).
\(\#143.\) Which is larger, \(99^n + 100^n\) or \(101^n\) (where \(n\) is a natural number)? (hint, solution)
\(\#145.\) Prove that, for any natural number \(n\), \(2 < \left(1+\frac{1}{n}\right)^n < 3\) (hint).
\(\#149.\)* Prove that if \(m\) > \(n\) (where \(m, \; n\) are natural numbers) (hint):
\begin{align*}
(a) \quad \hspace{20pt} \left(1+\frac{1}{m}\right)^m & > \left(1+\frac{1}{n}\right)^n.\\[0.7em]
(b) \hspace{20pt} \left(1+\frac{1}{m}\right)^{m+1} & < \left(1+\frac{1}{n}\right)^{n+1}, \quad (n \geq 2).
\end{align*}
7. Miscellaneous Problems from Algebra (160-195).
\(\#178.\)* Prove that if \(x_1\) and \(x_2\) are roots of the equation \(x^2 - 6x + 1 = 0\), then \(x_1^n + x_2^n\) is, for any natural number \(n\), an integer not divisible by 5. (hint, solution)
8. The Algebra of Polynomials (196-221).
\(\#198.\) Prove that in the product
\begin{align*}
\left(1 - x + x^2 - x^3 + \cdots - x^{99} + x^{100}\right)\left(1 + x + x^2 + x^3 + \cdots + x^{99} + x^{100}\right),
\end{align*}
after multiplying and collecting terms, there does not appear a term in \(x\) of odd degree. (hint, solution)
9. Complex Numbers (222-239).
\(\#234.\) (a). On a circle which circumscribes an \(n\)-sided (regular) polygon \(A_1A_2 \cdots A_n\), a point \(M\) is taken. Prove that the sum of the squares of the distances from this point to all the vertices of the polygon is a number independent of the position of the point \(M\) on the circle, and that this sum is equal to \(2nR^2\), where \(R\) is the radius of the circle.
(b) Prove that the sum of the squares of the distances from an arbitrary point \(M\), taken in the plane of a regular \(n\)-sided polygon \(A_1A_2 \cdots A_n\) to all the vertices of the polygon, depends only on the distance \(l\) of the point \(M\) from the center \(O\) of the polygon, and is equal to \(n(R^2 + l^2)\), where \(R\) is the radius of the circle circumscribing the regular \(n\)-sided polygon.
(c) Prove that statement (b) remains correct even when point \(M\) does not lie in the plane of the \(n\)-sided polygon \(A_1A_2 \cdots A_n\). (hint, solution)
10. Some Problems of Number Theory (240-254).
\(\#248.\) Prove that, for any prime \(p\), it is possible to find integers \(x\) and \(y\) such that \(x^2 + y^2 + 1\) is divisible by \(p\). (hint, solution)
11. Some Distinctive Inequalities (255-308).
\(\#258.\) Prove that if \(a+b=1\), where \(a\) and \(b\) are positive numbers, then:
\begin{align*}
\left(a+\frac{1}{a}\right)^2 + \left(b+\frac{1}{b}\right)^2 \geq \frac{25}{2}.\\
\end{align*}
(hint, solution)
12. Difference Sequences and Sums (309-320).
\(\#316.\) (a) Prove that the sum \(1^k + 2^k + 3^k + \cdots + n^k\) is a polynomial in \(n\) of degree \(k+1\).
(b) Calculate the coefficients of \(n^{k+1}\) and \(n^k\) of this polynomial. (hint, solution)
Mike Bertrand
June 3, 2024
For Parzival, on his high school graduation.
Congratulations Par!
^ 1. The USSR Olympiad Problem Book: Selected Problems and Theorems of Elementary Mathematics, by D. O. Shklarsky, N. N. Chentzov, and I. M. Yaglom, Dover Publications, Inc. (1993), ISBN 0-486-27709-7. This is a reprint of the first English edition edited by Irving Sussman and published by W. H. Freeman in 1962. The problems were developed over some twenty five years going back to the 1930s and collected into a volume titled Selected Problems and Theorems of Elementary Mathematics in the Soviet Union.
^ 2. The International Mathematical Olympiads are a direct descendant of the olympiad tradition in the Soviet Union and Hungary, which spread to the Soviet bloc after WWII, gradually increasing in scope up to the present day. Many of the problems in this book are in the vein of more modern olympiad problems, especially in the earlier period (IMO problems have gotten harder by the year in order to keep up with the extensive olympiad prep industry). The main difference is that our book has almost no geometry, a staple of the IMO. See International Mathematical Olympiads 1959-1977, by Samuel L. Greitzer, The Mathematical Association of America (1978), for a brief account of the evolution of the IMO in early years, as well as the problems and solutions over this period.