IMC 2023 training
I am helping organize extracurricular problem-solving sessions for enthusiastic undergraduate and master's students at the School of Mathematics, University of Bristol, focused on competitive math problems. One the aims of the sessions is to select and train a team of students to represent the University of Bristol at the International Mathematics Competition for University Students IMC 2023 which will take place in the summer.
The training sessions will be ran by me, Oleksiy Klurman, Joseph Najnudel and Sam Pattison. The ultimate aim of the sessions is to enhance the students' problem-solving skills and mathematical thinking. We will mainly focus on presenting material and solving competition problems in the fields of Algebra (Linear and Abstract), Analysis (Real and Complex), Number Theory, Geometry and Combinatorics.
Should you have any questions, please contact me at besfort.shala@bristol.ac.uk.
Resources
Textbooks are a good place to start for competitions for university students. A solid understanding of the basic undergraduate material is often helpful and enough to solve the first one or two problems. One good book focused on competitive problems is Putnam and Beyond by Rǎzvan Gelca and Titu Andreescu.
Problems from previous competitions: see Putnam, IMC, IMO, and more generally the Art of Problem Solving forum (which should contain the preceding ones as well as much more).
Journals: see AMM, Mathematics Magazine, Mathematical Reflections (this one tends to have easier problems in the undergraduate section, so it's a good place to start).
Session 1
Session 1: Saturday, November 19th, 10:00-13:00, LG.02, Fry Building. Ran by Besfort Shala.
We started by discussing general tips/goals on problem-solving, including the following main four points: (i) getting comfortable with not being able to solve problems; (ii) reading solutions appropriately -- a line-by-line understanding of the arguments does not suffice, ask why all the time but understand that answering may be difficult; (iii) taking time to think about the big picture, try summarizing solutions in a few sentences; (iv) making sure to spend a reasonable amount of time and effort on writing solutions up, do not stop once you are convinced that you've solved the problem.
Mathematically, the topic of the session was the usage of eigenvalues in solving Linear Algebra problems. We covered diagonalizability, the complex and real spectral theorems and the spectral mapping theorem; see for instance Linear Algebra Done Right by Sheldon Axler, and Putnam and Beyond.
Session 2
Session 2: Saturday, November 26th, 10:00-13:00, LG.02, Fry Building. Ran by Prof. Joseph Najnudel.
We covered the topic of inequalities, combined with inequality problems with additional differential/integral structure. In particular, we discussed Young's, Hölder's (including Cauchy-Schwarz as a special case) and Minkowski's inequalities.
Session 3
Session 3: Saturday, December 3rd, 10:00-13:00, LG.02, Fry Building. Ran by Prof. Oleksiy Klurman.
We discussed Dirichlet's principle (also known as the pigeonhole principle), and its relevance in the approximation of real numbers by rational ones. The session was a long "warm-up", going through problems and applications of the pigeonhole principle.
Problems in Analysis (to be used in future sessions).
Session 4
Session 4: Saturday, December 10th, 10:00-13:00, LG.02, Fry Building. Ran by Besfort Shala.
We started by solving LA4 from Problem Sheet 1 (see Session 1 above), recapping the spectral theorems and discussing the usefulness of finding group structures. A good source for a gentle introduction to group theory is the book A first course in abstract algebra by John B. Fraleigh.
We continued by considering problems in the form of questions, that is, problems which ask to prove or disprove some statement. It is important for such questions to have a strategy to correctly guess what the answer should be -- it is often useful to simply consider and/or construct examples which satisfy at least some of the given conditions in the problem. Furthermore, we discussed how the idea of counting objects up to an arbitrary threshold is useful when then there are infinitely many objects. This allows us to think about only finitely many things at once, and then attain information when allowing the threshold to increase.
We finished by discussing a common misconception that students have in analysis problems, namely that all differentiable functions have integrable derivatives. The mean value theorem often comes to rescue in such situations, due to the theorem being true for functions which are merely differentiable (that is, without necessarily having a continuous, or even integrable derivative). A good source for such interesting phenomena is the book Counterexamples in analysis by Bernard R. Gelbaum and John M. H. Olmsted.
Session 5
Session 5: Saturday, January 28th, 10:00-13:00, G.09, Fry Building. Ran by Besfort Shala.
We solved P1, P2 and P3 from the problem sheet below, in the reverse order. We discussed about constructing non-linear (equivalently, discontinuous) solutions to the functional equation f(x + y) = f(x) + f(y) using the Axiom of Choice, namely its consequence that every vector space has a basis (and thus real numbers viewed as an infinite-dimensional vector space over the rational numbers has a basis in particular). Additionally, we discussed a general strategy using equivalence relations that might be helpful to construct discontinuous solutions to functional equations.
In P2, we saw the problem could be translated into determining the order of 2 modulo 51 (that is, the least positive integer j such that 2^j = 1 mod 51). One possible source for learning more about this topic more generally is the book Elementary number theory by David M. Burton.
In P1, we discussed how the "discrete derivative" (also known as the method of finite differences) helps in reducing the degree of a recurrence relation. Although we did not need to solve the recurrence relation after reducing it to a linear one, it is worthwhile to know how to do this: see the Wikipedia page on linear recurrences with constant coefficients or any standard combinatorics textbook.
Session 6
Session 6: Saturday, February 4th, 10:00-13:00, G.09, Fry Building. Ran by Prof. Joseph Najnudel.
Session 7
Session 7: Saturday, February 11th, 10:00-13:00, G.09, Fry Building. Ran by Prof. Oleksiy Klurman.
Session 8
Session 8: Saturday, February 18th, 10:00-13:00, G.09, Fry Building. Ran by Sam Pattison.
In this session, we covered generating functions and their usage in solving combinatorial problems. An excellent source for (a lot) more on generating functions is the book generatingfunctionology by Herbert S. Wilf.
Session 9
Session 9: Saturday, February 25th, 10:00-13:00, G.09, Fry Building. Ran by Besfort Shala.
We solved P1, P2, and P4 from the problem sheet below. In P1, it was important to first spend some time thinking about how the different components in the problem statement are connected to one-another. After establishing this, we observed the problem could be solved by using standard properties of the trace (namely trace(XY) = trace(YX) and that the trace is the sum of eigenvalues), thinking about eigenvalues and applying the spectral mapping theorem. See the previously suggested resources on linear algebra.
In P2, thinking about why the problem statement is excluding primes was very helpful. Indeed, this led us to rightly guess that primes are extremal in the context of the problem. Afterwards, by considering the prime factorization of n, we showed that a(n)/n is uniformly bounded by a number less than 1, thus showing the series is dominated by a convergent geometric series.
In P4, we used the generating function "recipe" to solve the problem, that is, we used the recurrence relation for a(n) to get a relation (more concretely a differential equation) for the generating function F(x) = Σ a(n)x^n, which we were able to solve using the integrating factor method. It was crucial to justify all formal computations by using that the series defining F converges absolutely and uniformly in a small neighborhood of 0 (we used the ratio test for series from an introductory course to analysis to do this). After solving for F, we observed that it looked difficult (but perhaps not impossible) to Taylor-expand F in a way that allows us to deduce that all the coefficients are integers. However, we were able to use the explicit form of F and the generating function "recipe" in reverse to produce a simpler recurrence relation for a(n), from where the integrality of the a(n) was obvious.
Session 10
Session 10: Saturday, March 4th, 10:00-13:00, G.09, Fry Building. Ran by Joseph Najnudel.
Session 11
Session 11: Saturday, March 11th, 10:00-13:00, G.09, Fry Building. Ran by Oleksiy Klurman.
Session 12
Session 12: Saturday, March 18th, 10:00-13:00, G.09, Fry Building. Ran by Sam Pattison.
Team selection test
TST: Saturday, April 29th, 10:00-14:00, LG.02, Fry Building.