Introduction to Theoretical Tasks

Written by Bibin Muttappillil and Timon Gehr.

At SOI we sometimes ask you to justify why your algorithm solves a given problem. This usually involves four points:

  1. a description of the idea on how to solve the problem
  2. an explanation why this idea solves the problem correctly for all inputs
  3. an analysis on how fast the proposed algorithm is and how much memory it needs
  4. a rough sketch of a pseudo-code with the important pieces

where the most essential part is the second point.

Like writing algorithms, proving their correctness is not an easy task. There is no step-by-step guide on how to reason correctly as it requires a lot of creativity and thinking. Despite this we try to collect some tips and techniques on how to write theoretical solutions.

We will start with some guidelines on how to write down your solutions. Then we introduce you to some techniques on how to show that a program solves something correctly (second point). And we will look on how to analyze runtime and memory (third point).

Note: These techniques are not only useful for theoretical tasks, but for actual programming. Knowing how to show that something is correct helps debugging a faulty program as you can observe where your explanation and therefore your code breaks. It also helps to save time as you can see faster which algorithms are wrong and don’t waste time implementing a wrong solution.

How to write ‘proofs’

In mathematics there are so-called ‘proofs’, which are formal descriptions of an explanation of why something is correct. We at SOI don’t expect you to write such things, but we expect you to give a good explanation containing all important ideas and steps involved in showing the correctness of your algorithm. It doesn’t need to be formally correct, but we need to see that you thought about all possible cases where your idea could go wrong. In the following we will refer to those explanations as ‘reasonings’.

One essential point for a clean reasoning is structure. With structure it is easier for you to build logical arguments and to see why they are correct or if something is missing (also applies to us as correctors). For that you can define lemmas, constructs and use facts.
The latter is just knowledge you can assume are known at SOI (e.g. something written in the wiki, a well-known mathematical property, …). Be sure that this fact is true and try to include a reference (e.g. wiki, lecture of ours, name of the property, …) if you know it.
Sometimes you may want to use special property which is useful for you reasoning, for example looking only at a continuous subsequence which is strictly increasing (e.g. looking at [2,5,7][2, 5, 7] and [1,2,9][1, 2, 9] in the array A=[9,2,5,7,6,5,1,2,9,8]A = [9, 2, 5, 7, 6, 5, 1, 2, 9, 8]). Then instead of writing the properties over and over again you can define a construct and then reason what properties it has and what consequences follow from this construct. In the example before you could define a ‘rise’ (the name doesn’t matter) as two indices aa and bb such that for every ii, where ai<ba \le i < b, it holds that A[i]<A[i+1]A[i] < A[i+1]. With this definition you don’t have two write ‘continuous subsequence which is strictly increasing’ every time, it is clear what you mean and you can build on top of this definition, for example you can define the length of a rise as len(rise):=ba+1len(rise) := b-a+1 (where :=:= is the symbol for defined as).
The most important thing for the structure are probably lemmas. Usually one property is not enough to reason that something is correct, but you need a few key observations. You can view this small observations and properties as checkpoints in your whole reasoning. We call these checkpoints lemmas. An example of a lemma would be that two rises (from before) don’t overlap. If you have several lemmas it is good to name or number them, so we could name the property from before as ‘Lemma of overlap’ or just ‘Lemma 1’. Don’t forget that you also need to reason why a lemma you used is correct. With lemmas it is easier to see what you already showed, what you can use in your reasoning and what we can give you points for.

We will use these structure elements in the following sections so that you can see how they could be applied.

Here are some rules of thumb if you are not sure if your reasoning is correct:

  • Try to justify everything or say it’s well known (only if it is actually known or really obvious).
  • Try to think of counterexamples and see if your reasoning holds against them (meaning your have an argument against it). Counterexample are the easiest and most powerful tool against wrong reasoning (and also against wrong algorithms).

Notation

Before we begin we need to agree on some notation. Let’s say that AA and BB are statements. A statement can be any claim or sentence which is either true or false. For example A=“There are 56 cards in a deck of Tichu”A = \text{“There are 56 cards in a deck of Tichu”} is a true statement, B=“42 is the largest natural number”B = \text{“42 is the largest natural number”} would be a wrong statement and F(n)=“The n-th Fibonacci number is 1”F(n) = \text{“The n-th Fibonacci number is 1”} is true for n=1n = 1 and n=2n = 2 but false for the other numbers. Every statement can also be negated, meaning we can also say the opposite (e.g. notA=“There are not 56 cards in a deck of Tichu”\operatorname{not} A = \text{“There are } \textbf{not } \text{56 cards in a deck of Tichu”}). As you saw we write the negation with the ‘not\operatorname{not}’ word. The key property of the negation is that a true statements becomes false and vice versa:

AA notA\operatorname{not} A
false true
true false

We also need the implication, denoted by \rightarrow. A statement can imply another statement, ABA \rightarrow B. This means that if AA is true, than BB must also be true. For example A=“x is divisible by 4”A = \text{“x is divisible by 4”} and B=“x is even”B = \text{“x is even”}. If AA is true BB must be true, but if AA is false then BB can be true or false. So the implication only goes one way. Note that an implication ABA \rightarrow B is again a statement and therefore it can be again true or false. For example A=“V is the father of L”A = \text{“V is the father of L”} and B=“L is the son of V”B = \text{“L is the son of V”} then it is not necessarily true that ABA \rightarrow B holds (L could be the daughter of V). This table summarizes when ABA \rightarrow B is true:

AA BB ABA \rightarrow B
false false true
false true true
true false false
true true true

Contradiction

Now to the interesting part. An easy yet powerful tool is called proof by contradiction. This is the technique were you assume the opposite of the thing you want to reason about and show that the opposite leads to a contradiction and therefore must be impossible. With this you can conclude that the original statement is true. In other words if we want to say that a statement AA is correct we try to assume notA\operatorname{not} A, then conclude stuff with this assumptions (e.g. notAB0B1\operatorname{not} A \rightarrow B_{0}\rightarrow B_{1}, notAC0\operatorname{not} A \rightarrow C_{0}, …) and find two statements that contradict each other (e.g. B1B_{1} is the same as notC0\operatorname{not} C_{0} but C0C_{0} and notC0\operatorname{not} C_{0} can’t both be true).
A small example to see why it might be easier to argue with the negated statements:
Proof why there are infinite natural numbers:
Let’s try to use proof by contradiction. We assume the opposite that there are finite many natural numbers. Now we can say that there exists a largest natural number (for example by testing every number), let’s call it MM. We also know that M+1M+1 is also a natural number and that M+1M+1 is larger (M+1>MM+1 > M). This contradicts with the definition of MM being the largest, so our assumption of the finiteness of natural numbers must be false. (Note: You don’t need to be so formal as to specify which statement is AA, BB or C0C_{0}, these are just here as helping tools).

Indirect proofs

A similar technique to contradiction are indirect proofs. They work in a similar manner, but you work with a beginning statement. So instead of reasoning why BB is true you want to show that BB is true if AA is true (ABA \rightarrow B). The rest is very similar except our end goal. We assume notB\operatorname{not} B, show some in between steps (notBC0C1\operatorname{not} B \rightarrow C_{0}\rightarrow C_{1}\rightarrow {\dots}) and instead of leading to a contradiction we want to show notA\operatorname{not} A. In summary we say that ABA \rightarrow B is correct by showing notBnotA\operatorname{not} B \rightarrow \operatorname{not} A. The intuition is that if ABA \rightarrow B is true it means that BB has to be true if AA is true. So in case BB is false this means that AA has to be false as well, otherwise this leads to a contradiction. And the last statement can be read as notBnotA\operatorname{not} B \rightarrow \operatorname{not} A.
AA BB ABA \rightarrow B notBnotA\operatorname{not} B \rightarrow \operatorname{not} A
false false true true
false true true true
true false false false
true true true true
A small example, proving that if n2n^{2} is even then nn is also even:
Instead of showing n2 is evenn is evenn^{2}\text{ is even} \rightarrow n \text{ is even} we want to show n is not evenn2 is not evenn \text{ is} \textbf{ not} \text{ even} \rightarrow n^{2}\text{ is} \textbf{ not} \text{ even}.
Well n is not evenn \text{ is} \textbf{ not} \text{ even} implies that n is oddn \text{ is odd} meaning we can write n=2k+1n = 2 \cdot k + 1. Then it holds that n2=4k2+4k+1=2(2k2+2k)+1=2C+1n^{2}= 4 \cdot k^{2}+ 4 \cdot k + 1 = 2 \cdot (2 \cdot k^{2}+ 2 \cdot k) + 1 = 2 \cdot C + 1 (where C=2k2+2kC = 2 \cdot k^{2}+ 2 \cdot k). This again shows that n2n^{2} is odd and therefore not even.
With this we showed that n is not evenn2 is not evenn \text{ is} \textbf{ not} \text{ even} \rightarrow n^{2}\text{ is} \textbf{ not} \text{ even} and therefore also n2 is evenn is evenn^{2}\text{ is even} \rightarrow n \text{ is even}.

And how is that useful for SOI?

Two of the most common outputs of our problems are either ‘yes/no’ or the size of an optimal solution.
In the ‘yes/no’ category you usually need to show that something is either possible or impossible for a given input. Be careful in your reasoning as you actually need to reason two things here:
  1. You need to argue why for every possible case you print ‘yes’ and
  2. why for every impossible case you print ‘no.’
And for both there are several ways to tackle the reasoning.
Either you try to reason it directly (possible inputoutput ’yes’\text{possible input} \rightarrow \text{output 'yes'}) or try it indirectly and show that ‘no’ would be a wrong answer (output ’no’impossible input\text{output 'no'} \rightarrow \text{impossible input}) or use contradictions (output ’no’ and possible inputcontradiction\text{output 'no' and possible input} \rightarrow \text{contradiction}). They all reason about the same thing, but the start and ending point are different, giving you several options to choose from. Depending on the situation one might be easier than the others.
The ‘no’ case is analogous, either show directly (impossible inputoutput: ’no’\text{impossible input} \rightarrow \text{output: 'no'}), indirectly (output ’yes’possible input\text{output 'yes'} \rightarrow \text{possible input}) or contradiction (output ’yes’ and impossible inputcontradiction)(\text{output 'yes' and impossible input} \rightarrow \text{contradiction}).
The other category is finding an optimal solution or at least the size of the optimal solutions. Let’s say the problem asks us to find a solution with an ‘x’ as big as possible. Here again we need to reason about two things:
  1. Why is your output is correct (so why there exists a solution with the size of your output) and
  2. why there is no better solution.
The first part is usually easier, you need to show why your algorithm could output a correct construction that fulfills the requirements of the desired output. The second part requires more thinking as you need to show that there can’t exist a better solution (better meaning with a larger ‘x’). Here we mostly use the contradiction method: assume there exists a solution that is greater than the solution found by your algorithm then try to show that this leads directly to a contradiction or show that your algorithm would have found this solution.
The details for both kind of problems are dependent on the specific problem and usually involve other proof techniques for a full reasoning, but it at least shows what you need to do and where to start.

Induction

Often, we want to show that a statement is true for all elements of a certain set, for example the set of natural numbers N={0,1,2,3,}\mathbb{N}=\{0,1,2,3,\ldots\}, or the set of possible inputs to your program. Sometimes, it is possible to argue that the statement is true for all elements by picking an arbitrary unknown representative of the set and arguing for that specific representative.

For example, for an arbitrary natural number nn, we know that n+1n+1 is larger than nn. Therefore, we know that for all natural numbers nn, n+1n+1 is larger than nn.

Unfortunately, for some statements, this kind of argument is not strong enough. The reason is that in order to show something holds true for the natural number nn, we may already want to use that the same thing is true for natural numbers that are smaller than nn.

For example, the sum 0+1+2++n0+1+2+\cdots+n is equal to n(n+1)2\frac{n(n+1)}2. We can easily check that this is true for n=0n=0, in which case both terms are 00. Assume that for some fixed n>0n>0, we already know that 0+1++(n1)0+1+\cdots+(n-1) is (n1)n2\frac{(n-1)n}2. We can then conclude that 0+1++n=(0+1++(n1))+n=(n1)n2+n=n(n+1)20+1+\cdots+n=(0+1+\cdots+(n-1))+n=\frac{(n-1)n}2+n=\frac{n(n+1)}2. We have now shown that equality holds for n=0n=0, and for all n>0n>0, if the equality holds for n1n-1, then it also holds for nn. This means, if we want to show that the equality holds for some specific natural number kk, we can start at n=0n=0, and use our argument kk times until we reach n=kn=k. Therefore, the equality is true for all natural numbers.

More generally, imagine we want to show that the statement P(n)P(n) is true for all natural numbers nn. It then sufficies to show that P(0)P(0) is true and that for all natural numbers n>0n>0, we have P(n1)P(n)P(n-1)\to P(n). This observation is known as the principle of mathematical induction. In our first example, the statement P(n)P(n) was 0+1+2++n=n(n1)20+1+2+\cdots+n=\frac{n(n-1)}2.

(Note that a well-known alternative argument is to note that 2(0+1+2++n)=2\cdot(0+1+2+\cdots+n)= (0+1+2++n)+(n+(n1)++0)=(0+n)+(1+(n1))++(n+0)=(0+1+2+\cdots+n)+(n+(n-1)+\cdots+0)=(0+n)+(1+(n-1))+\cdots+(n+0)= n+n++n=(n+1)nn+n+\cdots+n=(n+1)\cdot n, but what we discuss above is actually a bit simpler.)

Note that the principle of mathematical induction is equivalent to the observation that any non-empty set of natural numbers has a smallest element: If we want to show that the statement P(n)P(n) is true for all natural numbers nn, we can argue by contradiction. Assume to the contrary that there is some natural number nn which is a counterexample, i.e., P(n)P(n) is false. In particular, consider the smallest nn for which P(n)P(n) is false. (This exists because the set of counterexamples has a smallest element.) We then show that P(0)P(0) is true and we conclude that nn must be larger than 00. Then, we show P(n1)P(n)P(n-1)\to P(n) or, equivalently notP(n)notP(n1)\operatorname{not} P(n)\to \operatorname{not} P(n-1). From notP(n)\operatorname{not} P(n) we can then derive notP(n1)\operatorname{not} P(n-1). This is however a contradiction, because nn was the smallest counterexample, but now we found one that is even smaller. Therefore our assumption had to be wrong and P(n)P(n) is true for all natural numbers nn.

A well-known variant is the principle of complete induction. It follows from the principle of mathematical induction using the statement P(n)P(n) that says that some statement Q(n)Q(n) is true for all natural numbers mm that are strictly smaller than nn. To show that Q(n)Q(n) is true for all natural numbers nn using the principle of complete induction, we pick an arbitrary natural number nn, assume that Q(m)Q(m) is true for all m<nm<n and then show that Q(n)Q(n) is true.

The principle of complete induction is particularly helpful for arguing about the correctness of recursive functions. Consider the following algorithm for sorting a list of numbers:

def mergeSort(list):
    if len(list) <= 1:
        return list
    else:
        (firstHalf, secondHalf) = split(list)
        return merge(mergeSort(firstHalf), mergeSort(secondHalf))

Here, the function split splits a list of nn numbers into two halves of length n/2\lfloor n/2\rfloor and n/2\lceil n/2 \rceil (i.e., n/2n/2, once rounded down and once rounded up to the next integer), and the function merge takes two sorted lists and merges them into a single sorted list containing the same numbers. We can use complete induction to show that the function mergeSort correctly sorts the list of numbers.

In particular, we will show that the algorithm sorts lists of length nn for an arbitrary nn. By the principle of complete induction, we can assume that the algorithm correctly sorts lists that contain fewer than nn elements. If nn is 00 or 11, the list is already sorted and therefore the algorithm returns it unchanged. Otherwise, the list is split into two halves that both contain strictly fewer than nn elements. Therefore, the algorithm sorts each half correctly. Finally, the function mergemerge combines the two sorted halves into a single sorted list.

Greedy

See the Greedy script to see how to reason about greedy algorithms.

Last remarks

As with implementing algorithms reasoning about correctness requires a lot of practice. Check out old 2T Task in the Archive and try to solve them. After trying it also read our solutions to see what kind of solution we expect. If you want more theory and exercises on logical reasoning in general you can also check out our sister olympiad the ‘Math Olympiad’, especially their combinatorics section might also be useful in the SOI.

This wiki is still in work if you have any questions, remarks, comments or new tips you want to share, please email us at info@soi.ch such that we can extend this knowledge.