Inequalities and mathematical induction: RMO sample problems-solutions

Problem:

1. Prove the inequality —- 2^{n}(n!)^{2} \leq (2n)! for all natural numbers greater than or equal to 1.

Proof 1:

First consider the following: 2.6. 10.14 \ldots (4n-2)=\frac{(2n)!}{n!}. Let us prove this claim first and then use it to prove what is asked: Towards, that end, consider

RHS = \frac{(2n)(2n-1)(2n-2)(2n-3)(2n-4)\ldots 4.2.1}{1.2.3.4\ldots (n-1)n}=LHS, cancelling off the common factors in numerator and denominator of RHS. (note this can also be proved by mathematical induction! ūüôā )

In the given inequality:

we need to prove 2^{n}(n!)^{2} \leq (2n)!

consider 2.6.10.14. \ldots (4n-2)=\frac{(2n)!}{n!} where

LHS = (2.1)(2.3) (2.5) (2.7) \ldots 2(n-1), this is an AP with first term 2 and nth term (4n-2) and common difference 4; there are n factors “2”; hence, we 2^{n}1.3.5.7 \ldots (n-1)=\frac{(2n)!}{n!} so we get

2^{n} (n!) 1.3.5.7.\ldots (n-1) = (2n)!; multiplying and dividing RHS of this by 2.4.6.8.\ldots n, we get the desired inequality. Remember the inequality is less than or equal to.

Problem 2:

Establish the Bernoulli inequality: If (1+a) > 0, then (1+a)^{n} \geq 1+na.

Solution 2:

Apply the binomial theorem, which in turn, is proved by mathematical induction ! ūüôā

Problem 3:

For all natural numbers greater than or equal to 1, prove the following by mathematical induction:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{n^{2}} \leq 2-\frac{1}{n}

Proof 3:

Let the given proposition be P(n).

Step 1: Check if P(1) is true. Towards that end:

LHS=\frac{1}{1^{2}}=1 and $latex RHS=2-\frac{1}{1}=2-1=1$ and hence, P(1) is true.

Step 2: Let P(n) be true for some n=k, k \in N. That is, the following is true:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{k^{2}} \leq 2 -\frac{1}{k}

Add \frac{1}{(k+1)^{2}} to both sides of above inequality, we get the following:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{k^{2}} + \frac{1}{(k+1)^{2}} \leq 2-\frac{1}{k}+\frac{1}{(k+1)^{2}}

Now, the RHS in above is 2-\frac{1}{k} +\frac{1}{(k+1)^{2}}=2-\frac{k^{2}+k+1}{k(k+1)^{2}}. We want this to be less than or equal to 2-\frac{1}{k+1}. Now, k \in N, k>1, so what we have to prove is the following:

-\frac{k^{2}+k+1}{k(k+1)^{2}} \leq -\frac{1}{k+1}, that is, we want to prove that

(k+1)(k^{2}+k+1) \geq k(k^{2}+2k+1), that is, we want k^{3}+k^{2}+k+k^{2}+k+1 \geq k^{3}+2k^{2}+k, that is, we want k+1 \geq 0, which is obviously true. QED.

Cheers,

Nalin Pithwa.

RMO Training: more help from Nordic mathematical contest

Problem:

32 competitors participate in a tournament. No two of them are equal and in a one against one match the better always wins. (No tie please). Show that the gold, silver and bronze medal can be found in 39 matches.

Solution:

We begin by determining the gold medallist using classical elimination, where we organize 16 pairs and matches, then 8 matches of the winners, 4 matches of the winners in the second round, then 2-semifinal matches and finally one match making 31 matches altogether.

Now, the second best player must have at some point lost to the best player, and as there were 5 rounds in the elimination, there are 5 candidates for the silver medal. Let C_{i} be the candidate who  lost to the gold medalist in round i. Now, let C_{1} and C_{2} play, the winner play against C_{3}, and so forth. After 4 matches, we know the silver medalist; assume this was C_{k}.

Now, the third best player must have lost against the gold medalist or against C_{k} or both. (If the player had lost to someone else, there would be at least three better players.) Now, C_{k} won k-1 times in the elimination rounds, the 5-k players C_{k+1}\ldots C_{5} and if k is greater than one, one player C_{j} with j<k. So there are either (k-1)+(5-k)=4 or (k-1)+(5-k)+1=5 candidates for the third place. At most 4 matches are again needed to determine the bronze winners.

Cheers to Norway mathematicians!

Nalin Pithwa.

Reference: Nordic mathematical contests, 1987-2009.

Amazon India link:

https://www.amazon.in/Nordic-Mathematical-Contest-1987-2009-Todev/dp/1450519830/ref=sr_1_1?s=books&ie=UTF8&qid=1518386661&sr=1-1&keywords=Nordic+mathematical+contest

RMO 2017 Warm-up: Two counting conundrums

Problem 1:

There are n points in a circle, all joined with line segments. Assume that no three (or more) segments intersect in the same point. How many regions inside the circle are formed in this way?

Problem 2:

Do there exist 10,000 10-digit numbers divisible by 7, all of which can be obtained from one another by a re-ordering of their digits?

Solutions will be put up in a couple of days.

Nalin Pithwa.

 

Math concept(s) : simple yet subtle

Most math concepts are intuitive, simple, yet subtle. A similar opinion is expressed by Prof. Michael Spivak in his magnum opus, Differential Geometry (preface). It also reminds me — a famous quote of the ever-quotable Albert Einstein: “everything should be as simple as possible, and not simpler.”

I have an illustrative example of this opinion(s) here:

Consider the principle of mathematical induction:

Most students use the first version of it quite mechanically. But, is it really so? You can think about the following simple intuitive argument which when formalized becomes the principle of mathematical induction:

Theorem: First Principle of Finite Induction:

Let S be a set of positive integers with the following properties:

  1. The integer 1 belongs to S.
  2. Whenever the integer k is in S, the next integer k+1 must also be in S.

Then, S is the set of all positive integers.

The proof of condition 1 is called basis step for the induction. The proof of 2 is called the induction step. The assumptions made in carrying out the induction step are known as induction hypotheses. The induction situation has been likened to an infinite row of dominoes all standing on edge and arranged in such a way that when one falls it knocks down the next in line. If either no domino is pushed over (that is, there is no basis for the induction), or if the spacing is too large (that is, the induction step fails), then the complete line will not fall. 

So, also remember that the validity of the induction step does not necessarily depend on the truth of the statement that one is endeavouring to prove.

More later,

Nalin Pithwa.

Learn hardcore math and programming through games :-) The Game of Nim

Reference: Introductory Combinatorics, fourth edition, Richard A. Brualdi

Example : The Game of Nim:

It is a return to the roots of combinatorics —- which does lie in recreational mathematics and we investigate the ancient game of Nim. (Nim derives from the German word Nimml, meaning Take!) Its solution depends on parity, an important problem-solving concept in combinatorics. We can use parity argument in investigations of perfect covers of chessboards when we show that a board has to have an even number of squares in order that it have a perfect cover with dominoes.

Nim is a game played by two players with heaps of coins (or stones or beans or gems or diamonds !!! ūüôā ūüôā …).. Suppose that there are k \geq 1 heaps of coins that contain, respectively, n_{1}, n_{2}, \ldots, n_{k} coins. The object of the game is to select the last coin. The rules of the game are the following:

i) The players alternate turns (let us call the player who makes the first move I and then call the other player II).

ii) Each player, when it is his or her turn, selects one of the heaps and removes at least one of the coins from the selected heap. (The player may take all of the coins from the selected heap, thereby leaving an empty heap, which is now “out of play.”)

The game ends when all the heaps are empty. The last player to make a move, that is, the player who takes the last coin(s), is the winner. 

The variables in this game are the number k of heaps and the numbers n_{1}, n_{2}, \ldots, n_{k} of coins in the heaps. The combinatorial problem is to determine whether the first or second player wins and how that player should move in order to guarantee a win — a winning strategy.

In order to develop some understanding of Nim, we consider some special cases.¬†(This is an important principle to follow in general: Consider small or special cases in order to develop understanding and intuition. Then try to extend your ideas in order to solve the problem in general.)¬†If there is initially only one heap, then player 1 wins by removing all its coins. Now, suppose that there are k=2 heaps, with n_{1}, and n_{2} coins, respectively. Whether or not player I can win depends not on the actual values of n_{1} and n_{2} but on whether or not they are equal. Suppose that n_{1} \neq n_{2}. Player I can remove enough coins from the larger heap in order to leave two heaps of equal size for player II. Now player I, when it is her turn, can mimic player II’s moves. Thus, if player II takes c coins from one of the heaps, then player I takes the same number c of coins from the other heap. Such a strategy guarantees a win for player I. If n_{1}=n_{2}, then player II can win by mimicking player I’s moves. Thus, we have completely solved 2-heap Nim. An example of play in the 2-heap game of Nim with heaps of sizes 8 and 5, respectively, is

8, 5 \stackrel{I}\rightarrow 5,5 \stackrel{II}\rightarrow 5,2 \stackrel{I}\rightarrow 2,2 \stackrel{II}\rightarrow 0,2 \stackrel{I}\rightarrow 0,0

The preceding idea in solving 2-heap Nim, namely, moving in such a way as to leave two equal heaps, can be generalized to any number k of heaps. The insight one needs is provided by the concept of the base 2 numeral of an integer. Recall that each positive integer n can be expressed as a base 2 numeral by repeatedly removing the largest power of 2 which does not exceed the number. For instance, to express the decimal number 57 in base 2, we observe that

2^{6} \leq 57 < 2^{6}, 57-2^{5}=25,

2^{4} \leq 25 < 2^{5}, 25-2^{4}=9,

2^{3} \leq 9 < 2^{4}, 9-2^{3}=1,

2^{0}\leq 1 <2^{1}, 1-2^{0}=0.

Thus, 57=2^{5}+2^{4}+2^{3}+2^{0},

and the base 2 numeral for 57 is 111001.

Each digit in a base 2 numeral is either 0 or 1. The digit in the ith position, the one corresponding to 2^{i}, is called the ith bit (i \geq 0). We can think of each heap of coins as consisting of subheaps¬†of powers of 2, according to its base numeral. Thus, a heap of size 53 consists of subheaps of sizes 2^{5}, 2^{4}, 2^{2}, and 2^{0}. In the case of 2-heap Nim, the total number of subheaps of each size is either 0, 1, or 2. There is exactly one subheap of a particular size if and only if the two subheaps of each size is even if and only if the two heaps have the same size — that is, if and only if, player II can win the Nim game.

Now, consider a general Nim game with heaps of sizes n_{1}, n_{2}, \ldots, n_{k}. Express each of the numbers n_{i} as base 2 numerals:

n_{1}=a_{s}\ldots a_{1}a_{0}

n_{2}=b_{s}\ldots b_{1}b_{0}

\ldots

n_{k}=e_{s}\ldots e_{1}e_{0}

(By including leading 0’s we can assume that all of the heap sizes have base 2 numerals with the same number of digits.) We call a Nim game¬†balanced, provided that the number of subheaps of each size is even. Thus, a Nim game is balanced if and only if:

a_{s}+b_{s}+\ldots + e_{s} is even,

\vdots

a_{i}+b_{i}+\ldots + e_{i} is even,

\vdots

a_{0}+b_{0}+\ldots + e_{0} is even,

A Nim game that is not balanced is called unbalanced. We say that the ith bit is balanced, provided that the sum a_{i}+b_{i}+\ldots + e_{i} is even, and is unbalanced otherwise. Thus, a balanced game is one in which all bits are balanced, while an unbalanced game is one in which there is at least one unbalanced bit.

We then have the following:

Player I can win in unbalanced Nim games, and player II can win in balanced Nim games.

To see this, we generalize the strategies used in 2-pile Nim.¬†Suppose the Nim game is unbalanced. Let the largest unbalanced bit be the jth bit. Then, player I moves in such a way as to leave a balanced game for player II. She does this by selecting a heap whose jth bit is 1 and removing a number of coins from it so that the resulting game is balanced. No matter what player II does, she leaves for player I an unbalanced game again, and player I once again balances it. Continuing like this ensures player I a win. If the game starts out balanced, then player I’s first move unbalances it, and now player II adopts the strategy of balancing the game whenever it is her move.

For example, consider a 4-pile Nim game with heaps of sizes 7,9, 12 and 15. The base 2 numerals for these heap sizes are, respectively, 0111, 1001, 1100, and 1111. In terms of subheaps of powers of 2 we have:

\begin{array}{ccccc}    \emph{4-pile Nim game} & 2^{3}=8 & 2^{2}=4 & 2^{1}=2 & 2^{0}=1 \\    \emph{heap of size 7}       & 0              & 1                & 1              & 1                \\    \emph{heap of size 9}       & 1               & 0               & 0             & 1                 \\    \emph{heap of size 12}     & 1               & 1                & 0             & 0                 \\    \emph{heap of size 15}     & 1               & 1                & 1              & 1                   \\    \end{array}

This game is unbalanced with the 3rd, 2nd, and 0th bits unbalanced. Player I can remove 11 coins from the pile of size 12, leaving 1 coin. Since the base 2 numeral of 1 is 0001, the game is now balanced. Alternatively, player I can remove 5 coins from the pile of size 9, leaving 4 coins, or player I can remove 13 coins from the pile of size 15, leaving 2 coins.

A quiz:

  1. Consider 3-heap Nim with piles of sizes 1, 2 and 4. Show that this game is unbalanced and determine a first move for player I.
  2. Is 4-pile Nim with heaps of sizes 22, 19, 14, and 11 balanced or unbalanced? Player I’s first move is to remove 6 coins from the heap of size 19. What should player II’s first move be?
  3. Consider 5-pile Nim with heaps of sizes 10, 20, 30, 40, and 50. Is this game balanced? Determine a first move for player I.

Have fun with math games  !

Cheers,

Nalin Pithwa.

Inclusion Exclusion Principle : further RMO Basics

Note:¬†continued from previous blog article of same topic; same reference text (by the way, this is a beautiful introductory classic in Combinatorics, but a “thick, huge” text !!! :-))

https://madhavamathcompetition.com/2017/07/13/the-inclusion-exclusion-principle-again/

Theorem 1.1: (or 6.1.1 of text):

The number of objects of S that have none of the properties P_{1}, P_{2}, P_{3}, \ldots, P_{m} is given by:

|\overline{A_{1}}\bigcap \overline{A_{2}}\bigcap\ldots\bigcap \overline{A_{m}}|=|S|-\sum|A_{i}|+\sum|A_{i}\bigcap A_{j}|-\sum|A_{i}\bigcap A_{j}\bigcap A_{k}|+\ldots+(-1)^{m}|A_{1}\bigcap A_{2}\bigcap \ldots \bigcap A_{m}|

Some remarks on the theorem 1.1 before we present the proof:

If m=0, the statement of the theorem becomes:

|A_{1}^{'}\bigcap A_{2}^{'}\bigcap A_{3}^{'}|=|S|-(|A_{1}|+|A_{2}|+|A_{3}|)+(|A_{1}\bigcap A_{2}|+|A_{1}\bigcap A_{3}|+|A_{2}\bigcap A_{3}|) - |A_{1}\bigcap A_{2} \bigcap A_{3}|

Note that there are 1+3+3+1=8 terms on the RHS. If m=4, then the statement of the theorem becomes:

|A_{1}^{'}\bigcap A_{2}^{'} \bigcap A_{3}^{'} \bigcap A_{4}^{'}|= |S|-(|A_{1}|+|A_{2}|+|A_{3}|+|A_{4}|) +(|A_{1}\bigcap A_{2}|+|A_{1}\bigcap A_{3}|+|A_{1}\bigcap A_{4}|+|A_{2}\bigcap A_{3}|+|A_{2}\bigcap A_{4}|+|A_{3}\bigcap A_{4}|) - (|A_{1}\bigcap A_{2} \bigcap A_{3}|+|A_{1}\bigcap A_{3} \bigcap A_{4}|+|A_{2}\bigcap A_{3}\bigcap A_{4}|)+|A_{1}\bigcap A_{2} \bigcap A_{3} \bigcap A_{4}|

In this case, there are 1+4+6+4+1=16 terms on the right side. In the general case, the number of terms on the right side of the equation/theorem statement is:

{m \choose 0}+{m \choose 1} + {m \choose 2} + {m \choose 3}+ \ldots + {m \choose m}=2^{m}.

Proof of theorem 1.1:

The LHS of the theorem statement (equation) counts the number of objects of S with none of the stated properties. We can establish the validity of the equation by showing that an object with none of the properties P_{1}, P_{2}, \ldots, P_{m} makes a net contribution of 1 to the right side, and an object with at least one of the properties makes a net contribution of 0. First, consider an object x with none of the properties. Its contribution to the right side of the equation is :

1-0+0-0+\ldots + (-1)^{m}0=1,

since it is in S, but in none of the other sets. Now, consider an object y  with exactly n \geq 1 of the properties. The contribution of y to |S| is 1= {n \choose 0}. Its contribution to \sum|A_{i}| is n = {n \choose 1} since it has exactly n of the properties and so is a member of exactly n of the sets A_{1}, A_{2}, \ldots , A_{m}. The contribution of y to \sum|A_{i}\bigcap A_{j}| is n \choose 2 since we may select a pair of the properties y has in n \choose 2 ways, and so y is a member of exactly n \choose 2 of the sets A_{i}\bigcap A_{j}. The contribution of y to the RHS of Equation I is

{n \choose 0} - {n \choose 1} + {n \choose 2} - {n \choose 3} + \ldots +(-1)^{m}{n \choose m}, which equals {n \choose 0} - {n \choose 1} + {n \choose 2} - {n \choose 3} + \ldots +(-1)^{n}{n \choose n}, since n \leq m and {n \choose k}=0, if k>n. Since this last expression equals 0 according to the identity 5.4, the net contribution of y to the RHS of Equation I is 0, if y has at least one of the properties. QED.

PS: By the way, identity 5.4 is as follows:

{n \choose 0}-{n \choose 1}+{n \choose 2}- \ldots + (-1)^{n}{n \choose n}=0, when n \geq 1.

Corollary 6.2:

The number of objects of S which have at least one of the properties P_{1}, P_{2}, \ldots, P_{m} is given by

|A_{1} \bigcup A_{2} \bigcup \ldots A_{m}|= \sum|A_{i}|-\sum|A_{i}\bigcap A_{j}|+ \sum|A_{i}\bigcap A_{j} \bigcap A_{k}|- \ldots +(-1)^{(m+1)}{|A_{1}\bigcap A_{2} \bigcap A_{3} \bigcap \ldots A_{m}|}

…call this relation as 6.2

where the summations are as specified in theorem 6.1.1(that is, theorem 1 of the previous blog mentioned above)

Proof of the above corollary:

The set A_{1} \bigcup A_{2} \bigcup \ldots A_{m} consists of all those objects in S which possess at least one of the properties. Also,

|A_{1} \bigcup A_{2} \bigcup A_{3} \ldots A_{m}|=|S|-|\overline{A_{1}\bigcup A_{2}\bigcup \ldots \bigcup A_{m}}|.

Since, as is readily verified, \overline{|A_{1}\bigcup A_{2} \bigcup \ldots A_{m}|}=\overline{A_{1}}\bigcap \overline{A_{2}}\bigcap \ldots \bigcap \overline{A_{m}}, we have

|A_{1}\bigcup A_{2}\bigcup \ldots \bigcup A_{m}|=|S|-|\overline{A_{1}}\bigcap \overline{A_{2}}\bigcap \overline{A_{3}}\bigcap\ldots \bigcap \overline{A_{m}}|.

Combining this equation with 6.1, we obtain equation or relation 6.2. QED.

Example:

Find the number of integers between 1 and 1000, inclusive, that are not divisible by 5, 6 and 8.

Solution:

Method 1: use some properties of number theory.

Method 2: use some properties of number theory and figure out how to apply the theory given above ! I agree it seems a very simple illustration of this generalized inclusion-exclusion principle, but we learn here to apply this technique with “clarity”…

To solve this problem, we introduce some notation. For a real number r, recall that \lfloor{r}\rfloor stands for the largest integer that does not exceed r. Also, we shall abbreviate the LCM of two integers, a and b or three integers a, b and c by lcm{(a,b)} and lcm{(a,b,c)} respectively. Let P_{1} be the property that an integer is divisible by 5, P_{2} the property that an integer is divisible by 6, and P_{3} the property that an integer is divisible by 8. Let S be the set consisting of the first thousand positive integers. For i=1,2,3, let A_{i} be the set consisting of those integers in S with property P_{i}. We wish to find the number of integers in \overline{A_{1}} \bigcap \overline{A_{2}} \bigcap \overline{A_{3}}.

We first see that |A_{1}|=\lfloor\frac{1000}{5}\rfloor=200; |A_{2}|=\lfloor \frac{1000}{6}\rfloor=166; |A_{3}|=\lfloor\frac{1000}{8}\rfloor=125

Integers in the set A_{1}\bigcap A_{2} are divisible by both 5 and 8. But, an integer is divisible by both 5 and 6 iff it is divisible by lcm{5,6}, which is, 30. Also, lcm{5,8}=40 and lcm{6,8}=24. Hence, we get

|A_{1}\bigcap A_{2}|=\lfloor \frac{1000}{30} \rfloor=33; |A_{1}\bigcap A_{3}|=\lfloor \frac{1000}{40} \rfloor=25; and |A_{2}\bigcap A_{3}|=\lfloor \frac{1000}{24} \rfloor=41

Because lcm{5,6,8}=120, we conclude that |A_{1}\bigcap A_{2} \bigcap A_{3}|=\lfloor \frac{1000}{120} \rfloor=8.

Thus, by the inclusion-exclusion principle, the number of integers between 1 and 1000 that are not divisible by 5, 6 and 8 equals:

|\overline{A_{1}}\bigcap \overline{A_{2}}\bigcap \overline{A_{3}}|=1000-(200+166+125)+(33+25+41)-8=600.

Example: 

How many permutations of the letters M,A,T,H,I,S,F,U, N are there such that none of the words MATH, IS, and FUN occur as consecutive letters ?(Thus, for instance, the permutation MATHISFUN is not allowed nor are the permutations INUMATHSF and ISMATHFUN.)

Solution:

We apply the generalized inclusion-exclusion principle (theorem 1).

Step 1: Identify the set S as the set of all permutations of the 9 letters given.

Step 2: Let P_{1} be the property that a permutation in S contains the word MATH as consecutive letters; let P_{2} be the property that a permutation in S contains the word IS and let P_{3} be the property that a permutation contains the word FUN. For i=1,2,3, let A_{i} be the set of those permutations in S satisfying property P_{i}.

Step 3: To find the number of permutations in \overline{A_{1}}\bigcap \overline{A_{2}}\bigcap \overline{A_{3}}.

Solution:

We have |S|=9!=362880. The permutations in A_{1} can be thought of as permutations of the six symbols: MATH, I, S, F, U and N.

Hence, |A_{1}|=6!=720.

Similarly, the permutations in A_{2} are permutations of the eight symbols: M,A,T,H,IS,F,U,N. So, |A_{2}|=8!=40320; and the permutations in A_{3} are permutations of the seven symbols : M,A,T,H,I,S,FUN so |A_{3}|=7!=5040.

The permutations in A_{1}\bigcap A_{2} are permutations of the five symbols: MATH, IS, F,U,N; the permutations in A_{1}\bigcap A_{3} are permutations of the four symbols: MATH, I, S, FUN; the permutations in A_{2}\bigcap A_{3} are permutations of the six symbols : M,A,T,H,IS,FUN.

Hence, we get the following:

|A_{1}\bigcap A_{2}|=120; |A_{1} \bigcap A_{3}|=4!=24; and |A_{2}\bigcap A_{3}|=6!=720.

Finally, A_{1}\bigcap A_{2} \bigcap A_{3} consists of the permutations of the three symbols MATH, IS, F, U, N; therefore, |A_{1}\bigcap A_{2} \bigcap A_{3}|=3!=6

Substituting into the equation of the theorem 1.1, we get:

|\overline{A_{1}}\bigcap \overline{A_{2}} \bigcap \overline{A_{3}}|=362880-700-40320-5040+120+24+720-6=317658.

(I hope you liked it!):-)

Remarks:

Later on, we consider applications of the inclusion-exclusion principle to some general problems. The following special case of the inclusion-exclusion principle will be useful:

Assume that the size of the set A_{i_{1}}\bigcap A_{i_{2}}\bigcap A_{i_{3}} \bigcap \ldots \bigcap A_{i_{k}} that occurs in the inclusion-exclusion principle depends only on k and not on which k sets are used in the intersection. Thus, there are constants \alpha_{0}, \alpha_{1}, \alpha_{2}, \ldots, \alpha_{n} such that

\alpha_{0}=|S|

\alpha_{1}=|A_{1}|=|A_{2}|=\ldots = |A_{m}|

\alpha_{2}=|A_{1}\bigcap A_{2}|=\ldots = |A_{m-1}\bigcap A_{m}|

\alpha_{3}=|A_{1}\bigcap A_{2} \bigcap A_{3}|=\ldots = |A_{m-2}\bigcap A_{m-1}\bigcap A_{m}|

\vdots

\alpha_{m} = |A_{1}\bigcap A_{2}\bigcap A_{3}\bigcap \ldots \bigcap A_{m}|

In this case, the inclusion-exclusion principle simplifies to 

Slatex |\overline{A_{1}}\bigcap \overline{A_{2}}\bigcap \ldots \bigcap \overline{A_{m}}|=\alpha_{0}-{m \choose 1}\alpha_{1}+{m \choose 2}\alpha_{2}-{m \choose 3}\alpha_{3}+\ldots+(-1)^{k}{m \choose k}\alpha_{k}+\ldots + (-1)^{m}\alpha_{m}$….call this equation III (or equation 6.3 as the book calls it).

This is because the kth summation that occurs in the inclusion-exclusion principle contains {m \choose k} summands, each equal to \alpha_{k}.

Example:

How many integers between 0 and 99999 (inclusive) have among their digits each of 2,5, and 8?

Solution:

Let S be the set of integers between 0 and 99999. Each integer in S has 5 digits including possible leading zeros. (Thus, we think of the integers in S as the 5-permutations of the multiset in which each digit 0,1,2,3,4,5,6,7,8,9 has repetition number 5 or greater).

Let P_{1} be the property that an integer does not contain the digit 2; let P_{2} be the property that an integer does not contain the digit 5, and let P_{3} be the property that an integer does not contain the digit 8. For i=1,2,3, let A_{i} be the set consisting of those integers in S with property P_{i}.

We wish to count the number of integers in \overline{A_{1}}\bigcap \overline{A_{2}\overline{A_{3}}}.

Using the notation in the preceding example, we have:

\alpha_{0}=10^{5}

\alpha_{1}=9^{5}

\alpha_{2}=8^{6}

\alpha_{3}=7^{5}.

For instance, the number of integers between 0 and 99999 that do not contain the digit 2 and that do not contain the digit 5, the size of |A_{1}\bigcap A_{2}|, equals the number of 5-permutations of the multiset

\{ 5.0, 5.1, 5.3,5.4,5.6, 5.7, 5.8,5.9\},

and this equals 8^{5}. By the corollary, we get the answer as : 10^{5}-3 \times 9^{5}+ 3 \times 8^{5}-7^{5}.

Did you like this? I hope to continue it further by also putting up some exercise problems from Brualdi’s Combinatorics book.¬†

Nalin Pithwa.

Some elegant applications of the Pigeonhole Principle

Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.

In many interesting applications of the pigeonhole principle, the objects to be placed in boxes must be chosen in a clever way. A few such applications will be described here.

Example 1:

During a month with 30 days, a baseball team plays at least one game a day, but no more than 45 games. Show that there must be a period of some number of consecutive days during which the team must play exactly 14 games.

Solution 1:

Let a_{j} be the number of games played on or before the jth day of the month. Then, a_{1}, a_{2}, \ldots, a_{30} is an increasing sequence of distinct positive integers, with 1 \leq a_{j} \leq 45. Moreover, a_{1}+14, a_{2}+14, \ldots, a_{30}+14 is also an increasing sequence of distinct positive integers, with 15 \leq a_{j} + 14 \leq 59.

The 60 positive integers a_{1}, a_{2}, \ldots, a_{30}, a_{1}+14, \ldots, a_{30}+14 are all less than or equal to 59. Hence, by the pigeonhole principle two of these integers are equal. Because the integers a_{j}, j=1, 2, \ldots, 30 are all distinct, there must be indices i and j with a_{i}=a_{j}+14. This means that exactly 14 games were played from day j+1 to i.

Example 2:

Show that among any n+1 positive integers not exceeding 2n there must be an integer that divides one of the other integers.

Solution 2:

Write each of the n+1 integers a_{1}, a_{2}, \ldots, a_{n+1} as a power of 2 times an odd integer. In other words, let a_{j} = 2^{k_{j}}q_{j} for j=1, 2, 3 \ldots n+1, where k_{j} is a nonnegative integer and q_{j} is odd. The integers q_{1}, q_{2}, \ldots, q_{n+1} are all odd positive integers less than 2n. Because there are only n odd positive integers less than 2n, it follows from the pigeonhole principle that two of the integers q_{1}, q_{2}, \ldots, q_{n+1} must be equal. Therefore, there are integers i and j such that q_{i} = q_{j}. Let q be the common value of q_{i} and q_{j}. Then, a_{i}=2^{k_{i}}q and a_{j}=2^{k_{j}}q. It follows that if k_{i}<k_{j} then a_{i} divides a_{j}. QED.

A clever application of the pigeonhole principle shows the existence of an increasing or a decreasing subsequence of a certain length in a sequence of distinct integers. Some definitions will be reviewed before this application is presented. Suppose that a_{1}, a_{2}, a_{3}, \ldots, a_{n} is a sequence of real numbers. A subsequence of this sequence is a sequence of the form a_{1_{1}}, a_{i_{2}}, \ldots, a_{i_{n}}, where 1 \leq i_{1} < i_{2} < ldots < i_{n} \leq N. Hence, a subsequence is a sequence obtained from the original sequence by including some of the original sequence in their original order, and perhaps, not including other terms. A sequence is called strictly increasing if each term is larger than the one that precedes it, and it is called strictly decreasing if each term is smaller than the one that precedes it.

Theorem:

Every sequence of n^{2}+1 distinct real numbers contains a subsequence of length n+1 that is either strictly increasing or strictly decreasing.

An example is presented below (before the proof) of the above:

Example:

The sequence 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 contains 10 terms. Note that 10=3^{2}+1. There are four increasing subsequence of length four, namely, 1, 4, 6, 12; 1, 4, 6, 7; 1, 4, 6, 10; 1, 4, 5, 7. There is also a decreasing subsequence of length four, namely, 11, 9, 6, 5.

The proof of the theorem is presented below:

Let a_{1}, a_{2}, \ldots, a_{n^{2}}+1 be a sequence of n^{2}+1 distinct real numbers. Associate an ordered pair with each term of the sequence, namely, associate (a_{k},d_{k}) to the term a_{k}, where i_{k} is the length of the longest increasing subsequence starting at a_{k}, and d_{k} is the length of the longest decreasing subsequence starting at a_{k}.

Suppose that there are no increasing or decreasing subsequences of length n+1. Then, i_{k} and d_{k} are both positive integers less than or equal to n, for k=1, 2, \ldots, n^{2}+1. Hence, by the product rule there are n^{2} possible ordered pairs for (i_{k},d_{k}). By the pigeonhole principle, two of these n^{2}+1 ordered pairs are equal. In other words, there exist terms a_{s} and a_{t}, with s<t such that i_{s}=i_{t} and d_{s}=d_{t}. We will show that this  is impossible. Because the terms of the sequence are distinct, either a_{s}>a_{t} or a_{s}<a_{t}. If a_{s}<a_{t}, then, because i_{s}=i_{t}, an increasing subsequence of length i_{t}+1, can be built starting at a_{s}, by taking a_{s} followed by an increasing subsequence of length i_{t} beginning at a_{t}. This is a contradiction. Similarly, if a_{s}>a_{t}, the same reasoning shows that d_{s} must be greater than d_{t}, which is a contradiction. QED.

Quiz based on generalized pigeonhole principle:

Assume that in a group of six people, each pair of individuals consists of two friends or two enemies. Show that there are either three mutual friends or three mutual enemies in the group.

Note: This little quiz is a motivation for Ramsey theory. This theory deals with the distribution of of subsets of elements of sets.

More later,

Nalin Pithwa