combinatorics

Simple concepts Tough problems

Gonit Sora

Apr 13, 2015 • 6 min read

References:

Mathematical Circles (Russian Experience); Dmitri Fomin, Sergey Genkin, Ilia Itenberg; Translated from Russian by Mark Saul; Volume 7; American Mathematical Society; ISBN 0-8218-0430-8.

Well … please don’t worry !! You are not in the end of the article !! It’s in fact the beginning … I know it’s crazy to start with the references but I just thought of pocketing in some attention !! Now, to be serious, this book is really a fantastic book of amazing mathematical problems. I think every student must try problems from it to sharpen the mathematical skills. The very first chapter stuns you with the amazingly application of simple concepts to tough problems. Consider the following problems from Chapter I of this book :

Can we draw a closed path made of 9 line segments, each of which intersects exactly one of the others?
Can a convex 13-gon be divided into parallelograms (not necessarily equal dimensions)?
Can a $5\times 5$ square checkerboard be covered by $1\times 2$ dominoes?
Given a convex 101-gon which has an axis of symmetry. Show that the axis of symmetry passes through one of the vertices.

Any solution? Well it’s good if you do find the solutions directly. But before attacking the problems, let us feel the simple concept :

If a set of objects can be partitioned into pairs, then there are evenly many of them

Now for the first problem, if such closed path were possible then we could group the lines into pairs of intersecting line segments but this is not possible as there are odd number of lines. The second one is also not posible, since each domino covers two squares and so the dominoes can cover only an even number of squares. For the third problem, suppose that the convex 13-gon were divided into parallelograms. We choose one of the sides and consider a particular parallelogram it belongs to. The opposite side of this parallelogram is also a side of a second parallelogram. This second parallelogram has another side parallel to the side we started with. We continue this chain of parallelograms until we arrive at another side of the 13-gon, which by our approach is parallel to the first side. Since the 13-gon is convex so this side cannot be parallel to any other side. Thus proceeding this way we could find pairs of parallel sides. But this is not possible as there are 13 sides. Note that the division into parallelograms is not possible even if it is a regular 13-gon. In a similar way, partitioning into pairs solves the other two problems too.

We go for some more problems :

The product of 22 integers is equal to 1. Show that their sum cannot be zero.
Pete bought a notebook containing 96 pages, and numbered them from 1 to 192. Victor tore out 25 pages of Pete’s notebook and added the 50 numbers he found on the pages. Could Victor have gotten 1990 as the sum?
Can one form a $latex 6\times 6$ magic square out of the first 36 prime numbers? Magic square means an array (here $6\times 6$ ) of boxes with a unique number in each box such that the sum of the numbers in every row, column or diagonal is the same.
The numbers 1 through 10 are written in a row. Can the signs + and – be placed in between them, so that the value of the resulting expression is zero?
The numbers $1,2,3,\ldots,1984,1985$ are written on a blackboard. We decide to erase from the board any two numbers and include their positive difference in the list. After doing this several times, a single number is left on the board. Could this number be equal to zero?
$1+3+5+\ldots+19=100$ . Which five of the numbers in L.H.S add up to 50?

The main idea in solving the above problems is :

The sum of evenly many odd numbers is even and the sum of oddly many odd numbers is odd

The curious readers may try solving these.

Now let us look at some problems concerning the prime factorization and division algorithm:

Is the product of any five consecutive natural numbers always divisible by 30?
How many zeros are there at the end of the number 100! ? (I mean factorial 100).
For some number $n$ , can the number n! have exactly five zeros at the end?
A number consists of 300 digits, of which 100 are 1’s, 100 are 2’s and 100 are 0’s, arranged in any order. Can this number be a perfect square? (One must try this problem at least… really its interesting!!)
Three prime numbers $p$ , $latex q$ and $latex r$, greater than 3, form an arithmetic progression: $p=p$ , $q=p+d$ and $latex r=p+2d$. Show that $d$ must be divisible by 6.

One more useful concept is the Pigeon Hole Principle. People who have never heard of it will think its just another mathematical joke. Anyway, whether one likes it or not, let me state it below:

If $N+1$ or more pigeons are to be put in $N$ pigeon holes then some pigeon hole must contain two or more pigeons

In a more general form,

If $Nk+1$ or more pigeons are to be put in $N$ pigeon holes then some pigeon hole must contain $k+1$ or more pigeons

A distinguishing feature of pigeon hole principle is that it sometimes allows us to draw quite unexpected conclusions even when we don’t seem to have enough information. The principle is quite trivial to understand but equally non-trivial while applying in problems. Lets have a look at some of the conclusions that can be drawn using pigeon hole principle :

In any group of 13 persons, there exist at least two persons having birthday on the same month.
If a board in the shape of equilateral triangle of side 20 cm is hit with a dart five times, then there exist at least two hits such that the distance between them less than 10cm.
Fifty one points are scattered inside a square of side 1 meter. There exists some set of three of these points can be covered by a square of side 20 cm.
Given any twelve integers, we can always find two integers out of these such that their difference is divisible by 11. (Hint: Use division algorithm)
To generalize the above: Given any $N+1$ integers, we can always find two integers out of these such that their difference is divisible by $N$ .
Given any 8 different natural numbers, not greater than 15, we can find at least three pairs of them having the same positive difference. (The pairs need not be disjoint as sets)
A bag contains balls of two colours. What is the minimum number of balls which must be drawn from the bag, of course without looking, so that two balls are of the same colour?

For the 6th problem, we see that the given 8 different numbers can form 28 different pairs (not ordered), the corresponding difference being any of the numbers from 1 to 14. But the difference 14 is possible only in one case ie 15-1=14. Thus remaining 27 pairs are to be fitted in `holes’ numbered form 1 to 13. And since $27=13\times 2+1$ by the general pigeon hole principle, at least one such positive difference must correspond to 2+1=3 pairs.

There are various other types of challenging problems in the book I have mentioned. Please do read the book Mathematical Circles for more!

Sign up for more like this.