# Problem Solving Maths Group Archives

I ran the Problem Solving Maths Group at the University of Edinburgh for 5 semesters. The main activity of the group are weekly sessions, each having as a topic a less-known, powerful, or in any way interesting mathematical concept or technique. At the beginning of a session, the attendees are given a guidance sheet containing a blend of theory and problems, then they try cooperatively to tackle the problems. You can find below a list of all of the topics from these 5 semesters with pdfs of the worksheets.

- The worksheets are problem-based and usually contain an explained introduction to the topic.
- The problems should be of ranging difficulty.
- I do not have solutions to all of them.
- You are most welcome to use the below resources for your own purposes.
- The vast majority of the materials should be mistake-free. No guarantees though.

## Regular sessions

# Extreme principle [»pdf«]

The Extreme principle is a methodology, a useful problem solving tactics, that focuses on finding a solution with some extreme property among all possible candidates. Very often, this means finding the smallest or largest value. Afterwards, the extreme solution is used to construct a proof while making use of the simplified conditions that it provides.

_{ Authors: Miroslav Stankovic, Marko Puza }

# Pick’s theorem [»pdf«]

Discrete Geometry is a branch of mathematics dealing with combinations and arrangements of geometric objects and discrete properties of such objects. Questions in discrete geometry usually involve countable sets of geometrical objects, such as points, lines, polygons and in general don’t involve the notion of continuity. Today, we will take a look at two different ways to calculate the area of simple polygons. First, we will deduce one of the most significant theorems in the area of Discrete geometry - the Pick’s Theorem. This will be followed by introducing the Shoelace formula and a small discussion about how useful these theorems are.

_{ Authors: Miroslav Stankovic, Marko Puza }

# Convex hull [»pdf«]

Shoelace formula and Convex Hull.

_{ Authors: Marko Puza, Miroslav Stankovic }

# Functional equations [»pdf«]

Functional Equations appear occasionally in mathematical competitions especially if one reaches further stages of those. The bad news about this: Those functional equations are completely different from what one is usually dealing with in University. But the good news is: They are much more fun :-).

_{ Authors: Jonas Wolter }

# Colouring proofs [»pdf«]

In 1961 it was proven that a chessboard can be covered be 2 ∗ 1 dominoes in 12,988,816 (24 ∗ 9012) different ways. Hence it seems to be appropriate if we’re looking at the problem in how many ways one can cover a chessboard with 2 ∗ 1 dominoes where the two opposite corners are missing ;-)

_{ Authors: Jonas Wolter }

# Double counting proofs [»pdf«]

Being able to employ a combinatorial point of view in seemingly non-related problems may often prove very useful - even provide a proof. In the following, we will take a look at a number of identities that can be proved by counting in two different ways. The simple example of usefulness of this technique can be the Handshaking lemma.

_{ Authors: Miroslav Stankovic, Marko Puza }

# Pigeonhole principle [»pdf«]

The Pigeonhole principle (also known as Dirichlet’s principle) states that if n pigeons are put into m holes with m < n, then there must exist a hole containing at least two pigeons. As easy and intuitive as this all may seem, this principle can be actually used to obtain a surprising range of possibly unexpected results.

_{ Authors: Miroslav Stankovic, Marko Puza }

# Invariants [»pdf«]

Invariants (also known as The Invariance Principle) are one of the most profound problem solving techniques. Problems that may be approached by this technique are often easily recognisable with the tricky part being how to find a suitable invariant. Invariant is a property whose value remains constant when the transformations are applied.

_{ Authors: Miroslav Stankovic, Marko Puza }

# Mean inequalities [»pdf«]

Inequality problems are a very broad topic. In this text, we will mostly focus the inequalities between means and how to apply them to solve wide range of inequalities.

_{ Authors: Miroslav Stankovic, Marko Puza }

# Elementary geometry I [»pdf«]

One of the most beautiful (I might be biased here) topics in problem solving is Euclidean geometry. To solve a geometric problem you often need to have a cunning perspective over the whole problem and employ creativity. In this sheet we will briefly iterate over some well-known theorems and look in more detail into properties of cyclic quadrilaterals.

_{ Authors: Miroslav Stankovic, Marko Puza }

# Elementary geometry II [»pdf«]

After having looked into angle-chasing problem solving approaches in geometry last week, the following pages contain simple tools that will enable us to augment angle-chasing with algebraic tools. More precisely, we will try to reason about angles using lengths and vice versa using Power of a point and Radical lines.

_{ Authors: Miroslav Stankovic, Marko Puza }

# Exploring fractals [»pdf«]

Roughly speaking, fractal can be described as an object that exhibits a repeating pattern that displays at any scale. Should the replication be same at every scale, it is called a self-similar pattern. Let’s confine our attention to these first. The notion of dimension is usually perceived as number of independent directions, or degrees of freedom, of some object. It turns out that consider- ing the effects of dimension on the measure of similar objects gives a simple way of characterizing fractals.

_{ Authors: Marko Puza }

# Fractals and the Chaos game [»pdf«]

We have seen two different possibilities to generate fractals yet. One uses more-or-less descriptions on how a fractal is produced. The other one uses L-systems. Interestingly, there is a third method to generate fractals using a probabilistic algorithm which is known as the Chaos Game. As an example, the follow- ing algorithm produces the Sierpinski Triangle which we have already seen when we were looking at L-systems.

_{ Authors: Jonas Wolter }

# Sets and infinity [»pdf«]

The idea of infinity have always been part of mathematics and philosophy. It has been part of famous Zeno’s paradoxes, infinite lines in geometry, or basis of analysis in the times of Leibnitz and Newton. However, until late 18th century, the infinity was viewed as something indefinite - as a limit, towards which a variable goes.

_{ Authors: Miroslav Stankovic }

# Combinatorics [»pdf«]

Introduction to combinatorics.

_{ Authors: Ivan Lau, Marko Puza }

# Games [»pdf«]

Another topic that appears occasionally in mathematical competitions and which is also a lot of fun is the topic of Games. Games in the mathematical context are always seen as a competition between two players who are allowed to conduct different operations. In this session we will only look at games which don’t contain any randomness in them (such as rolling a die).

_{ Authors: Jonas Wolter }

# Colouring for physicists [»pdf«]

Tiling problems are about covering a space (usually a plane or its part), using specific set of tiles. Tiling problems arise in different areas of mathematics, but are usually considered as problems in Combinatorics or Algebra. In this paper, we will be mostly looking at a finite two-dimensional grid to be covered by square tiles.

_{ Authors: Miroslav Stankovic }

# Barycentric coordinates [»pdf«]

Last week we have used weights to solve some tiling problems by especially using the centroid of different points. Interestingly there is a different very beautiful application of weights in Geometry which is known as the method of Barycentric coordinates. We are all used to working with cartesian coordinates which involve assigning coordinates (mostly 2 or 3) to a point. We all know that this gives abstract geometric problems a very basic setting and a good way to tackle them computationally. The problem that often appears are the difficult coordinates of certain points which make calculations very tedious. Barycentric coordinates really try to overcome this problem by not starting with axis but with vertices as the foundation for the coordinates.

_{ Authors: Jonas Wolter }

# Continued fractions [»pdf«]

We all know fractions from a very early age. We also know that not any real number can be written as a fraction (although you probably got to know this a tad later) - there is the set of irrational numbers for which it is not possible. Today, we will introduce an interesting concept of continued fraction, which somehow extends the concept to all of the real numbers. Not only will every real number have a representation as a continued fraction, these will also provide us with a straightforward way to approximate the irrationals.

_{ Authors: Marko Puza }

# The Farey sequence [»pdf«]

Before we dive into exploring these simply looking sequences, let me first include a few paragraphs about their back- ground. As often happens in Mathematics, the history behind the Farey sequences turns out to be really curious. We will begin the story with an 18-th century British magazine called The Ladies’ Diary, also known as the Woman’s Almanack. As opposed to what you may consider to be the Woman’s almanacks nowadays, the Ladies’s Diary contents could be described (as the cover says): “Containing New Improvements in ARTS and SCIENCES, and many entertaining PARTICULARS: Designed for the USE AND DIVERSION OF THE FAIR SEX.”.

_{ Authors: Marko Puza }

# Knot theory [»pdf«]

A mathematical knot is a closed loop in 3-dimensional space, which may be tangled.

_{ Authors: Imogen I. Morris}

# Geometry with complex numbers [»pdf«]

We all know complex numbers appearing as solutions to polynomial equations and might have seen some other applications of them in Calculus and Analysis. Surprisingly we usually visualise Complex Numbers in the 2-dimensional plane but we barely use this geometric interpretation. In today’s session we are going to see how Complex Numbers can be used to solve geometric problems. It appears not as an intuitive approach and the calculations seem sometimes quite tedious but it turns out that complex numbers are a lot less pain than cartesian coordinates and extremely useful if you are not brilliant in introducing the golden point ;-)

_{ Authors: Jonas Wolter }

# The Cauchy-Schwarz inequality [»pdf«]

Named after mathematicians Augustin-Louis Cauchy and Hermann Amandus Schwarz, the Cauchy-Schwarz inequality is a fundamental result in the theory of inequalities and has a wide range of applications and extensions in as diverse fields as number theory, analysis, probability theory, vector algebra, and many others.

_{ Authors: Håvard Damm-Johnsen}

# Lines and circles in combinatorics [»pdf«]

In this session, we will look at two basic geometrical structures, circles and lines and how they interact in the plane. We will count the intersections between n lines and k circles and the number of regions they divide the plane into. Try to search for patterns and justify your findings. No specific theorems are needed, but analytic geometry and combinations may be useful.

_{ Authors: Daniel Eriksson }

# Systems of non-linear equations [»pdf«]

You have most likely solved a couple of linear systems of equations in your life. If solutions exist, their exist efficient methods for finding those. In this session, we will tackle nonlinear system of equations. No general solution methods exist and finding solutions is in general a hopeless business. Here we will look at some tricks to solve specific such systems. As for linear equations, substitution and adding/subtracting/multiplying equations is useful.

_{ Authors: Daniel Eriksson }

## Problem solving challenges

# Tiling with dominoes [»pdf«]

The problem around which the whole of today will revolve is simple to state and hard to solve.

Rather than trying to solve it directly, we encourage you to take it step by step, work in groups and co-operate and simply explore the interesting context of the problem. We do not expect anyone of you to have found the solution at the end of the day, or to have gone through all of the following pages. However, we do want you to produce a group report - a coherent and self-contained document in which you describe your findings, what made or did not make sense, and what you considered curious etc. It can contain known theorems and results, your own observations, proofs, pictures, graphs, computer programs or whatever you find suitable to express yourselves with. The report might become a piece of work that you can be proud of! After the event, we will read your reports and try to give constructive feedback, with a small prize for the best report!

_{ Authors: Marko Puza }

# The power of linearity (of expectation) [»pdf«]

Our modern world is filled with problems of all kinds, ranging in scale, complexity and importance. One of the crucial factors that has contributed to the success of human development overall is our ability to solve or overcome these problems, using our intelligence and strength in numbers. Hence, there will always be a need for individuals who are keen problem solvers - if not for saving the world, perhaps for saving yourself some trouble. But as with all things, becoming a good problem solver requires three things: Practice, practice and practice.

Buffon’s needle, Geoboard shapes, St. Petersburg Paradox

_{ Authors: Marko Puza, Simon Holm, Daniel Eriksson }