Math concept(s) : simple yet subtle

Posted by nkpithwa

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:

The integer 1 belongs to S.
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.

Famous harmonic series — solutions

Posted by nkpithwa

Solutions to previous blog questions on harmonic series are presented below:

Basic Reference: Popular Problems and Puzzles in Mathematics by Asok Kumar Mallik, IISc Press, Foundation Books; Amazon India link:

https://www.amazon.in/Popular-Problems-Puzzles-Mathematics-Mallik/dp/938299386X/ref=sr_1_2?ie=UTF8&qid=1505622919&sr=8-2&keywords=popular+problems+and+puzzles+in+mathematics

Detailed Reference:

Mallik, A. K. 2007: “Curious consequences of simple sequences,” Resonance, (January), 23-37.

Personal opinion only: Resonance is one of the best Indian magazines/journals for elementary/higher math and physics. It behooves you to subscribe to it. It will help in RMO, INMO and Madhava Mathematics Competition of India.

http://www.ias.ac.in/Journals/Resonance_–_Journal_of_Science_Education/

Solutions:

The thirteenth century French polymath Nicolas-Oresme proved that the harmonic series : $1+ \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots$ does not converge. Prove this result.

Solution 1:

Nicolas Oreme had provided a simple proof as it involves mere grouping of terms, noticing patterns and making comparisons:

$\lim_{n \rightarrow \infty}H_{n}=H_{\infty}=1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \ldots$

$> 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \ldots$

$> 1+ \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \ldots$

Therefore, $H_{\infty}$ diverges as we go on adding one half indefinitely. Here is another way to prove this:

Consider $\lim_{n \rightarrow \infty}H_{n}=H_{\infty}=1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots$

By multiplying and dividing both sides by 2 and then by regrouping the terms, we get:

$H_{\infty}=\frac{2}{2} + \frac{2}{4} + \frac{2}{6} + \frac{2}{8} + \ldots$

$H_{\infty}= \frac{1+1}{2} + \frac{1+1}{4} + \frac{1+1}{6} + \frac{1+1}{8} + \ldots$

$H_{\infty}= (\frac{1}{2} + \frac{1}{2}) + (\frac{1}{4} + \frac{1}{4}) + (\frac{1}{6} + \frac{1}{6}) + (\frac{1}{8} + \frac{1}{8}) + \ldots$

$H_{\infty}<1+ \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \ldots$

leading to a contradiction that $H_{\infty}<H_{\infty} !$ The contradiction arose because only finite numbers remain unaltered when multiplied and divided by 2. So, $H_{\infty}$ is not a finite number, that is, it diverges.

2. Prove that $\frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \ldots$ does not converge.

Solution 2:

$H_{E}=\frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \ldots=\frac{1}{2}(1+\frac{1}{2} + \frac{1}{3} + \frac{1}{4} +\ldots)=\frac{1}{2}H_{n}$ .

Since $H_{\infty}$ diverges, so does $H_{E}$ .

3. Prove that $1+ \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \ldots$ does not converge.

Solution 3:

$H_{O}=\frac{1}{1}+ \frac{1}{3} +\frac{1}{5}+ \frac{1}{7}+ \ldots$ diverges as each term in this series is greater than the corresponding term of $H_{E}$ , which we have just sent to diverge.

Cheers,

Nalin Pithwa.

Famous harmonic series questions

Posted by nkpithwa

Question 1:

The thirteenth century French polymath Nicolas Oresme proved that the harmonic series $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \ldots$ does not converge. Prove this result.

Question 2:

Prove that $\frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \ldots$ does not converge.

Question 3:

Prove that $1 + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \ldots$ does not converge.

Even if you solve these all on your own, you won’t achieve the glory of that French polymath, but you will have “re-discovered” some “elements of truth of analysis” …You can give yourself a pat on the back!

Cheers,

Nalin Pithwa.

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

Posted by nkpithwa

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:

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.
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?
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.

From China with love !

Posted by nkpithwa

A Chinese mathematical olympiad problem and its solution:

Some body had once commented: The Silicon Valley is full of IC’s — Indians and Chinese! .

(My humble opinion: Perhaps, because of the strong emphasis on math in the two countries.)

Solve the inequality: $\log_{2}{(x^{12}+3x^{10}+5x^{8}+3x^{6}+1)}<1+\log_{2}{(x^{4}+1)}$

Solution:

As $1+\log_{2}{(x^{4}+1)}=\log_{2}{(2x^{4}+2)}$ , and $\log_{2}{y}$ is monotonically increasing over $(0,+\infty)$ , the given inequality is equivalent to :

$x^{12}+3x^{10}+5x^{8}+3x^{6}+1<2x^{4}+2$ , that is,

$(\frac{1}{x^{2}})^{3}+2(\frac{1}{x^{2}})>x^{6}+3x^{4}+3x^{2}+1+2x^{2}+2$ , which in turn, equals $((x)^{2}+1)^{3}+2(x^{2}+1)$ .

Define: $g(t)=t^{2}+2t$ . Then, we have: $g(\frac{1}{x^{2}})>g(x^{2}+1)$ . Clearly, $g(t)$ is a monotonically increasing function; then we have

$\frac{1}{x^{2}}>x^{2}+1$

That is to say, $x^{4}+x^{2}-1<0$ .

We obtain $x^{2}<\frac{-1+\sqrt{5}}{2}$ . So the solution set is $(-\sqrt{\frac{-1+\sqrt{5}}{2}}, \sqrt{\frac{-1+\sqrt{5}}{2}})$ .

Do you think you can solve this problem by another method? Please let me know.

— Nalin Pithwa.

The Inclusion-Exclusion Principle again !! RMO basics

Posted by nkpithwa

Some refresher of motivation(s) and simple applications of the inclusion-exclusion principle. Remember that: (1) We owe a lot to the Indians who taught us how to count. — Albert Einstein. (2) Everything that can be counted is countable, but everything that is countable does not count. — Albert Einstein.

We will derive and apply an important counting formula called the inclusion-exclusion principle. Recall that the addition principle gives a simple formula for counting the number of objects in a union of sets, provided that the sets do not overlap (that is, provided that the sets determine a partition). The inclusion-exclusion principle gives a formula for the most general of circumstances in which the sets are free to overlap without restriction. The formula is necessarily complicated, but, as a result is more widely applicable.

1. The Inclusion-Exclusion Principle:

We know of several examples in which it is easier to make an indirect count of the number of objects in a set rather than to count the objects directly. Below are two more examples:

Example:

Count the permutations $\{ i_{1}i_{2}\ldots i_{n}\}$ of $\{ 1,2, \ldots ,n\}$ in which 1 is not in the first position (that is, $i_{1} \neq 1$ ).

We could make a direct count by observing that the permutations with 1 not in the first position can be divided into $(n-1)$ parts according to which of the $(n-1)$ integers k from $\{ 2,3,\ldots, n\}$ is in the first position. A permutation with k in the first position consists of k followed by a permutation of the $(n-1)-$ element set $\{ 1, \ldots, k-1, k+1, \ldots, n\}$ . Hence, there are $(n-1)!$ permutations of $\{ 1,2,3 \ldots, n\}$ with k in the first position. By the addition principle, there are $(n-1)!(n-1)$ permutations of $\{ 1,2, \ldots, n\}$ with 1 not in the first position.

Alternatively, we could make an indirect count by observing that the number of permutations of $\{1, 2, \ldots, n \}$ with 1 in the first position is the same set as the number $(n-1)!$ of permutations of $\{ 2,3,\ldots,n\}$ . Since the total number of permutations of $\{ 1,2,\ldots, n\}$ is n!, the number of permutations of $\{ 1,2,\ldots,n\}$ in which 1 is not in the first position is $n!-(n-1)!=(n-1)!(n-1)$ .

Example:

Count the number of integers between 1 and 600, inclusive, which are not divisible by 6.

We can do this indirectly as follows: The number of integers between 1 and 600 which are divisible by 6 is 600/6 which is equal to 100 since every sixth integer is divisible by 6. Hence, $600-100=500$ of the integers between 1 and 600 are not divisible by 6.

Some further notes:

The rule used to obtain an indirect count in these examples is the following: If A is a subset of a set S, then the number of objects in A equals the number of objects in S minus the number not in A. Recall that

$A^{'}=S-A= \{ x: x \in S, x \notin A\}$

is the complement of A in S: that is, the set consisting of those objects in S which are not in A. The rule can then be written as

$|A| = |S| - |A^{'}|$ , or equivalently, $|A^{'}|=|S|-|A|$ . This formula is the simplest instance of the inclusion-exclusion principle.

We shall formulate the inclusion-exclusion principle in a manner in which it is convenient to apply. As a first generalization of the preceding rule, let S be a finite set of objects, and let $P_{1}$ and $P_{2}$ be two “properties” that each object in S may or may not possess. We wish to count the number of objects in S that have neither property $P_{1}$ nor property $P_{2}$ . We can do this by first including all objects of S in our count, then excluding all objects that have property $P_{1}$ and excluding all objects which have property $P_{2}$ , and then, noting that we have excluded objects having both properties $P_{1}$ and $P_{2}$ twice, readmitting all such objects once. We can write this symbolically as follows: Let $A_{1}$ be the subset of objects of S that have property $P_{1}$ , and let $A_{2}$ be the subset of objects of S that have property $P_{2}$ . Then, $A_{1}^{'}$ consists of those objects of S not having property $P_{1}$ and let $A_{2}^{'}$ consists of those objects of S not having property $P_{2}$ . The objects of the set $A_{1}^{'}\bigcap A_{2}^{'}$ are those having neither property $P_{1}$ nor property $P_{2}$ . We then have $|A_{1}^{'} \bigcap A_{2}^{'}|=|S|-|A_{1}|-|A_{2}|+|A_{1}\bigcap A_{2}|$ .

Since the left side of the preceding equation counts the number of objects of S that have neither property $P_{1}$ nor property $P_{2}$ , we can establish the validity of this equation by showing that an object with neither of the two properties $P_{1}$ and $P_{2}$ makes a net contribution of 1 to the right side, and every other object makes a net contribution of zero. If x is an object with neither of the properties $P_{1}$ and $P_{2}$ , it counted among the objects of S, not counted among the objects of $A_{1}$ or of $A_{2}$ , and not counted among the objects of $A_{1}\bigcap A_{2}$ . Hence, its net contribution to the right side of the equation is $1-0-0+0=1$ .

If x has only the property $P_{1}$ , it contributes $1-1-0+0=0$ to the right side, while it has only the property $P_{2}$ , it contributes $1-0-1+0=0$ to the right side. Finally, if x has both properties $P_{1}$ and $P_{2}$ , it contributes $1-1-1+1=0$ to the right side of the equation. Thus, the right side of the equation also counts the number of objects of S with neither property $P_{1}$ nor property $P_{2}$ .

More generally, let $P_{1}$ , $P_{2}$ , $P_{3}$ , $\ldots$ , $P_{m}$ be m properties referring to the objects in S, and let

$A_{i}=\{ x: x \in S, \hspace{0.1 in} x \hspace{0.1 in} has \hspace{0.1 in} property \hspace{0.1 in} P_{i}\}$ , and $\{ i= 1,2,\ldots,m\}$

be the subset of objects of S that have property S (and possibly other properties). Then, $A_{i}\bigcap A_{j}$ is the subset of objects that have both properties $P_{1}$ and $P_{2}$ (and, possibly others), $A_{i}\bigcap A_{j}\bigcap A_{k}$ is the subset of objects which have properties $P_{i}$ , $P_{j}$ , $P_{k}$ and so on. The subset of objects having none of the properties is $A_{1}^{'}\bigcap A_{2}^{'} \bigcap \ldots \bigcap A_{m}^{'}$ . The inclusion exclusion principle shows how to count the number of objects in this set by counting objects according to the properties they do have. Thus, in this sense, it “inverts” the counting process.

Theorem 1.1:

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

$|A_{1}^{'}\bigcap A_{2}^{'} \bigcap A_{3}^{'}\bigcap \ldots 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 A_{3}\ldots \bigcap A_{m}|$ ,

where the first sum is over all 1-combinations $\{ i\}$ of $\{ 1,2,3, \ldots, m \}$ , the second sum is over all 2-combinations $\{ i,j\}$ of $\{ 1,2,\ldots, m\}$ , the third sum is over all 3-combinations $\{i,j,k\}$ of $\{ 1,2,\ldots, m\}$ , and so on.

Reference:

Introductory Combinatorics (Fourth Edition), Richard A. Brualdi:

For example, available at Amazon India:

http://www.amazon.in/Introductory-Combinatorics-4e-Brualdi/dp/8131718824/ref=sr_1_1?s=books&ie=UTF8&qid=1500279459&sr=1-1&keywords=introductory+combinatorics.

Also, for example, available at Flipkart:

https://www.flipkart.com/introductory-combinatorics-4th/p/itme3fz6nykgzdyw?pid=9788131718827&srno=s_1_1&otracker=search&lid=LSTBOK978813171882786XN5F&qH=75550818a6d8f118T

To be continued further,

Nalin Pithwa.

Some problems from Estonian Mathematical Olympiad: 2000

Posted by nkpithwa

Problem 1: How many positive integers less than 20002001 and not containing digits other than 0 and 2 are there?

Solution 1: The set of integers under consideration consists of all integers with up to 7 digits containing only digits 0 and 2, all 8 digit integers of the form 20000***, and the integer 20002000. There are $2^{k-1}$ integers with exactly k digits 0 and 2, and $2^{3}$ integers of the form 20000***. So, the required number of integers is $(2^{0}+2^{1}+2^{2}+ \ldots + 2^{6})+8+1=(2^{7}-1)+9=136$

Problem 2: Find the last two digits of the number: $1! + 2! + 3! +4! + \ldots +2000!$

Solution 2: This is a classic type of question: the product $1.2 \ldots 10$ has 2, 5, and 10 as factors, therefore being divisible by 100. Hence, the last two digits of n! are zeros for any $n \geq 10$ and it suffices to find the last two digits of $1!+2! + 3! + \ldots + 9!$ . The last two digits of the summands are 01, 02, 06, 24, 20, 20, 10, 20 and 80, yielding 13 as the answer.