There is a perceived barrier to mathematics: proofs. In this course we will try to convince you that this barrier is more frightening than prohibitive: most proofs are easy to understand if explained correctly, and often they are even fun. We provide an accompanied excursion in the “proof zoo” showing you examples of techniques of different kind applied to different topics.

We use some puzzles as examples, not because they are “practical”, but because discussing them we learn important reasoning and problem solving techniques that are useful. We hope you enjoy playing with the puzzles and inventing/understandings the proofs.

As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

**Who is this class for: **Our intended audience are all people that work or plan to work in IT, starting from motivated high school students. Almost no math background is assumed.

Course 1 of 5 in the Introduction to Discrete Mathematics for Computer Science Specialization

### Syllabus

**WEEK 1**

Why proofs?

What is a proof? Why do we care about proofs? Are the boring long tedious arguments usually known as `mathematical proofs’ really needed outside the tiny circle of useless theoreticians that pray something called `mathematical rigor’? In this course we will try to show that proofs can be simple, elegant, convincing, useful and (don’t laugh) exciting. Later we will try to show different proof techniques and tools, but first of all we should break the barrier and see that yes, one can understand a proof and one can enjoy the proof. We start with simple puzzles where one small remark can disclose “what really happens there” and then the proof becomes almost obvious.

Graded: Tiles, dominos, black and white, even and odd

Graded: Two Congruent Parts

Graded: Pluses, Minuses and Splitting

**WEEK 2**

How to Find an Example?

One example is enough to prove an existential statement, but how to find an example? In many cases the search space is enormous. A computer may help, but some reasoning that narrows the search space, is important both for computer search and for “bare hands” work — how can this be done? What do we need to prove if we claim that our solution is optimal? As usual, we’ll practice solving many interactive puzzles. We’ll show also some computer programs that help us to construct an example.

Graded: Magic Square 3 times 3

Graded: Different People Have Different Coins

Graded: Free accomodation

Graded: Is there…

Graded: Puzzle: N Queens

Graded: Number of Solutions for the 8 Queens Puzzle

Graded: Maximum Number of Two-digit Integers

Graded: Puzzle: Maximum Number of Rooks on a Chessboard

Graded: Puzzle: Maximum Number of Knights on a Chessboard

Graded: Puzzle: Maximum Number of Bishops on a Chessboard

Graded: Puzzle: Subset without x and 2x

**WEEK 3**

Recursion and Induction

We’ll discover two powerful methods of defining objects, proving concepts, and implementing programs — recursion and induction. These two methods are heavily used, in particular, in algorithms — for analysing correctness and running time of algorithms as well as for implementing efficient solutions. You will see that induction is as simple as falling dominos, but allows to prove complex things by decomposing them and moving step by step. You will learn how famous Gauss unexpectedly solved his teacher’s problem intended to keep him busy the whole lesson in just two minutes, and in the end you will be able to prove his formula using induction. You will be able to generalize scary arithmetic exercises and then solve them easily using induction.

Graded: Largest Amount that Cannot Be Paid with 5- and 7-Coins

Graded: Pay Any Large Amount with 5- and 7-Coins

Graded: Puzzle: Hanoi Towers

Graded: Number of Moves to Solve the Hanoi Towers Puzzle

Graded: Puzzle: Two Cells of Opposite Colors

Graded: Puzzle: Connect Points

Graded: Induction

**WEEK 4**

Logic

We have already invoked mathematical logic when we discussed proofs by examples. This week we will turn mathematical logic full on. We will discuss its basic operations and rules. We will see how logic can play a crucial and indispensable role in proofs. We will discuss how to construct a negation to the statement and we will meet the notion of a counterexamples. We will see tricky and seemingly counterintuitive, but yet (an unintentional pun) logical aspects of mathematical logic. We will see one of the oldest approaches to proving statements: Reductio ad Absurdum.

Graded: Always Prime?

Graded: Examples, Counterexamples and Logic

Graded: Puzzle: Balls in Boxes

Graded: Numbers in Boxes

Graded: Numbers on the Chessboard

Graded: Numbers in Boxes

Graded: How to Pick Socks

Graded: Pigeonhole Principle

Graded: Puzzle: An (-1,0,1) Antimagic Square

**WEEK 5**

Invariants

“There are things that never change”. Apart from being just a philosophical statement this phrase turns out to be an important idea that can actually help. In this module we will see how it can help in problem solving. Things that do not change are called invariants in mathematics. They form an important tool of proving with numerous applications, including estimating running time of algorithms. We will get some intuition of what they are, see how they can look like and get some practice in using them.

Graded: Puzzle: Sums of Rows and Columns

Graded: ‘Homework Assignment’ Problem

Graded: ‘Homework Assignment’ Problem 2

Graded: Chess Tournaments

Graded: Debugging Problem

Graded: Merging Bank Accounts

Graded: Puzzle: Arthur’s Books

Graded: Puzzle: Piece on a Chessboard

Graded: Operations on Even and Odd Numbers

Graded: Puzzle: Summing Up Digits

Graded: Switching Signs

Graded: Recolouring Chessboard

**WEEK 6**

Solving a 15-Puzzle

In this module we consider a well known 15-puzzle where one needs to restore order among 15 square pieces in a square box. It turns out that the behavior of this puzzle is determined by mathematics: it is solvable if and only if the corresponding permutation is even. We learn the basic properties of even and odd permutations. The task is to write a program that determines whether a permutation is even or odd. There is also a much more difficult bonus task: to write a program that actually computes a solution (sequence of moves) for a given position assuming that this position is solvable.

Graded: Interactive 15-puzzle

Graded: Transpositions and Permutations

Graded: Neighbor transpositions

Graded: Is a permutation even?

ENROLL IN COURSE