# Practice questions based on combinatorics for RMO Training and IITJEE Mathematics

Question 1:

Prove that if n is an even integer, then

$\frac{1}{(1!)(n-1)!} + \frac{1}{3! (n-3)!} + \frac{1}{5! (n-5)!} + \ldots + \frac{1}{(n-1)! 1!} = \frac{2^{n-1}}{n!}$

Question 2:

If ${n \choose 0}$, ${n \choose 1}$, ${n \choose 2}$, ….${n \choose n}$ are the coefficients in the expansion of $(1+x)^{n}$, when n is a positive integer, prove that

(a) ${n \choose 0} - {n \choose 1} + {n \choose 2} - {n \choose 3} + \ldots + (-1)^{r}{n \choose r} = (-1)^{r}\frac{(n-1)!}{r! (n-r-1)!}$

(b) ${n \choose 0} - 2{n \choose 1} + 3{n \choose 2} - 4{n \choose 3} + \ldots + (-1)^{n}(n+1){n \choose n}=0$

(c) ${n \choose 0}^{2} - {n \choose 1}^{2} + {n \choose 2}^{2} - {n \choose 3}^{2} + \ldots + (-1)^{n}{n \choose n}^{2}=0$, or $(-1)^{\frac{n}{2}}{n \choose {n/2}}$, according as n is odd or even.

Question 3:

If $s_{n}$ denotes the sum of the first n natural numbers, prove that

(a) $(1-x)^{-3}=s_{1}+s_{2}x+s_{3}x^{2}+\ldots + s_{n}x^{n-1}+\ldots$

(b) $2(s_{1}s_{2m} + s_{2}s_{2n-1} + \ldots + s_{n}s_{n+1}) = \frac{2n+4}{5! (2n-1)!}$

Question 4:

If $q_{n}=\frac{1.3.5.7...(2n-1)}{2.4.6.8...2n}$, prove that

(a) $q_{2n+1}+q_{1}q_{2n}+ q_{2}q_{2n-1} + \ldots + q_{n-1}q_{n+2} + q_{n}q_{n+1}= \frac{1}{2}$

(b) $2(q_{2n}-q_{1}q_{2m-1}+q_{2}q_{2m-2}+\ldots + (-1)^{m}q_{m-1}q_{m+1}) = q_{n} + (-1)^{n-1}{q_{n}}^{2}$.

Question 5:

Find the sum of the products, two at a time, of the coefficients in the expansion of $(1+x)^{n}$, where n is a positive integer.

Question 6:

If $(7+4\sqrt{3})^{n} = p + \beta$, where n and p are positive integers, and $\beta$, a proper fraction, show that $(1-\beta)(p+\beta)=1$.

Question 7:

If ${n \choose 0}$, ${n \choose 1}$, ${n \choose 2}$, …,, ${n \choose n}$ are the coefficients in the expansion of $(1+x)^{n}$, where n is a positive integer, show that

${n \choose 1} - \frac{{n \choose 2}}{2} + \frac{{n \choose 3}}{3} - \ldots + \frac{(-1)^{n-1}{n \choose n}}{n} = 1 + \frac{1}{2} + \frac {1}{3} + \frac{1}{4} + \ldots + \frac{1}{n}$.

That’s all for today, folks!

Nalin Pithwa.

# Combinatorics for RMO : some basics and examples: homogeneous products of r dimensions

Question:

Find the number of homogeneous products of r dimensions that can be formed out of the n letters a, b, c ….and their powers.

Solution:

By division, or by the binomial theorem, we have:

$\frac{1}{1-ax} = 1 + ax + a^{2}x^{2} + a^{3}x^{3} + \ldots$

$\frac{1}{1-bx} = 1+ bx + b^{2}x^{2} + a^{3}x^{3} + \ldots$

$\frac{1}{1-cx} = 1 + cx + c^{2}x^{2} + c^{3}x^{3} + \ldots$

Hence, by multiplication,

$\frac{1}{1-ax} \times \frac{1}{1-bx} \times \frac{1}{1-cx} \times \ldots$

$= (1+ax + a^{2}x^{2}+a^{3}x^{3}+ \ldots)(1+bx + b^{2}x^{2} + b^{3}x^{3}+ \ldots)(1+cx + c^{2}x^{2} + c^{3}x^{3}+ \ldots)\ldots$

$= 1 + x(a + b + c + \ldots) +x^{2}(a^{2}+ab+ac+b^{2}+bc + c^{2} + \ldots) + \ldots$

$= 1 + S_{1}x + S_{2}x^{2} + S_{3}x^{3} + \ldots$ suppose;

where $S_{1}$, $S_{2}$, $S_{3}$, $\ldots$ are the sums of the homogeneous products of one, two, three, … dimensions that can be formed of a, b, c, …and their powers.

To obtain the number of these products, put a, b, c, …each equal to 1; each term in $S_{1}$, $S_{2}$, $S_{3}$, …now becomes 1, and the values of $S_{1}$, $S_{2}$, $S_{3}$, …so obtained give the number of the homogeneous products of one, two, three, ….dimensions.

Also,

$\frac{1}{1-ax} \times \frac{1}{1-bx} \times \frac{1}{1-cx} \ldots$

becomes $\frac{1}{(1-x)^{n}}$, or $(1-x)^{-n}$

Hence, $S_{r} =$ the coefficient of $x^{r}$ in the expansion of $(1-x)^{-n}$

$= \frac{n(n+1)(n+2)(n+3)\ldots (n+r-1)}{r!}= \frac{(n+r-1)!}{r!(n-1)!}$

Question:

Find the number of terms in the expansion of any multinomial when the index is a positive integer.

In the expansion of $(a_{1}+ a_{2} + a_{3} + \ldots + a_{r})^{n}$

every term is of n dimensions; therefore, the number of terms is the same as the number of homogeneous products of n dimensions that can be formed out of the r quantities $a_{1}$, $a_{2}$, $a_{3}$, …$a_{r}$, and their powers; and therefore by the preceding question and solution, this is equal to

$\frac{(r+n-1)!}{n! (r-1)!}$

A theorem in combinatorics:

From the previous discussion in this blog article, we can deduce a theorem relating to the number of combinations of n things.

Consider n letters a, b, c, d, ….; then, if we were to write down all the homogeneous products of r dimensions, which can be formed of these letters and their powers, every such product would represent one of the combinations, r at a time, of the n letters, when any one of the letters might occur once, twice, thrice, …up to r times.

Therefore, the number of combinations of n things r at a time when repetitions are allowed is equal to the number of homogeneous products of r dimensions which can be formed out of n letters, and therefore equal to $\frac{(n+r-1)!}{r!(n-1)!}$, or ${{n+r-1} \choose r}$.

That is, the number of combinations of n things r at a time when repetitions are allowed is equal to the number of combinations of $n+r-1$ things r at a time when repetitions are NOT allowed.

Example 1:

Find the coefficient of $x^{r}$ in the expansion of $\frac{(1-2x)^{2}}{(1+x)^{3}}$

Solution 1:

The expression $= (1-4x+4x^{2})(1+p_{1}x+p_{2}x^{2}+ \ldots + p_{r}x^{r}+ \ldots)$, suppose.

The coefficients of $x^{r}$ will be obtained by multiplying $p_{r}$, $p_{r-1}$, $p_{r-2}$ by 1, -4, and 4 respectively, and adding the results; hence,

the required coefficient is $p_{r} - 4p_{r-1}+4p_{r-2}$

But, with a little work, we can show that $p_{r} = (-1)^{r}\frac{(r+1)(r+2)}{2}$.

Hence, the required coefficient is

$= (-1)^{r}\frac{(r+1)(r+2)}{2} - 4(-1)^{r-1}\frac{r(r+1)}{2} + 4 (-1)^{r-2}\frac{r(r-1)}{2}$

$= \frac{(-1)^{r}}{2}\times ((r+1)(r+2) + 4r(r+1) + 4r(r-1))$

$= \frac{(-1)^{r}}{2}(9r^{2}+3r+2)$

Example 2:

Find the value of the series

$2 + \frac{5}{(2!).3} + \frac{5.7}{3^{2}.(3!)} + \frac{5.7.9}{3^{3}.(4!)} + \ldots$

Solution 2:

The expression is equal to

$2 + \frac{3.5}{2!}\times \frac{1}{3^{2}} + \frac{3.5.7}{3!}\times \frac{1}{3^{3}} + \frac{3.5.7.9}{4!}\times \frac{1}{3^{4}} + \ldots$

$= 2 + \frac{\frac{3}{2}.\frac{5}{2}}{2!} \times \frac{2^{2}}{3^{2}} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}}{3!} \times \frac{2^{3}}{3^{3}} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}.\frac{9}{2}}{4!} \times \frac{2^{4}}{3^{4}} + \ldots$

$= 1 + \frac{\frac{3}{2}}{1} \times \frac{2}{3} + \frac{\frac{3}{2}.\frac{5}{2}}{2!} \times (\frac{2}{3})^{2} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}}{3!} \times (\frac{2}{3})^{3} + \frac{\frac{3}{2}.\frac{5}{2}.\frac{7}{2}.\frac{9}{2}}{4!} \times (\frac{2}{3})^{4} + \ldots$

$= (1-\frac{2}{3})^{\frac{-3}{2}} = (\frac{1}{3})^{-\frac{3}{2}} = 3^{\frac{3}{2}} = 3 \sqrt{3}$.

Example 3:

If n is any positive integer, show that the integral part of $(3+\sqrt{7})^{n}$ is an odd number.

Solution 3:

Suppose I to denote the integral and f the fractional part of $(3+\sqrt{7})^{n}$.

Then, $I + f = 3^{n} + {n \choose 1}3^{n-1}\sqrt{7} + {n \choose 2}3^{n-2}.7 + {n \choose 3}3^{n-3}.(\sqrt{7})^{3}+ \ldots$…call this relation 1.

Now, $3 - \sqrt{7}$ is positive and less than 1, therefore $(3-\sqrt{7})^{n}$ is a proper fraction; denote it by $f^{'}$;

Hence, $f^{'} = 3^{n} - {n \choose 1}.3^{n-1}.\sqrt{7} + {n \choose 2}.3^{n-2}.7 - {n \choose 3}.3^{n-3}.(\sqrt{7})^{3}+ \ldots$…call this as relation 2.

Add together relations 1 and 2; the irrational terms disappear, and we have

$I + f + f^{'} = 2(3^{n} + {n \choose 2}.3^{n-2}.7+ \ldots ) = an even integer$

But, since f and $f^{'}$ are proper fractions their sum must be 1;

Hence, I is an odd integer.

Nalin Pithwa.

# Some Basics for RMO Number Theory: Congruences

I. The congruence notation:

It often happens that for the purposes of a particular calculation, two numbers which differ by a multiple of some fixed number are equivalent, in the sense that they produce the same result. For example, the value of $(-1)^{n}$ depends only on whether n is odd or even, so that two values of n which differ by a multiple of 2 give the same result. Or again, if we are concerned only with the last digit of a number, then for that purpose two numbers which differ by a multiple of 10 are effectively the same.

The congruence notation, introduced by Gauss, serves to express in a convenient form the fact that the two integers a and b differ by a multiple of a fixed natural number m. We say that a is congruent to b with respect to the modulus m, or in symbols,

$a \equiv b {\pmod m}$

The meaning of this, then, is simply that $a-b$ is divisible by m. The notation facilitates calculations in which numbers differing by a multiple of m are effectively the same, by stressing the analogy between congruence and equality. Congruence, in fact, means “equality except for the addition of some multiple of m”.

A few examples of valid congruences are :

$63 \equiv 0 {\pmod 3}$; $7 \equiv -1 {\pmod 8}$; $5^{2} \equiv -1 {\pmod {13}}$

A congruence to the modulus 1 is always valid, whatever the two numbers may be, since every number is a multiple of 1. Two numbers are congruent with respect to the modulus 2 if they are of the same parity, that is, both even or both odd.

Two congruences can be added, subtracted or multiplied together, in just the same way as two equations, provided all the congruences have the same modulus. If

$a \equiv \alpha {\pmod m}$ and $b \equiv \beta {\pmod m}$

then:

$a + b \equiv {\alpha + \beta} {\pmod m}$

$a - b \equiv {\alpha - \beta}{\pmod m}$

$ab \equiv {\alpha\beta} {\pmod m}$

The first two of these statements are immediate: for example, $(a+b) - (\alpha + \beta)$ is a multiple of m because $a- \alpha$ and $b - \beta$ are both multiples of m. The third is not quite so immediate because $ab - \alpha \beta = (a-\alpha)b$, and $a - \alpha$ is a multiple of m. Next, $ab \equiv \alpha \beta$, for a similar reason. Hence, $ab \equiv {\alpha \beta} {\pmod m}$.

A congruence can always be multiplied throughout by any integer; if $a \equiv {\alpha} {\pmod m}$ the10n $ka \equiv {k\alpha} {\pmod m}$. Indeed this is a special case of the third result above, where $b$ and $\beta$ are both k. But, it is not always legitimate to cancel a factor from a congruence. For example, $42 \equiv 12 {\pmod 10}$, but it is not permissible to cancel the factor 6 from the numbers 42 and 12, since this would give the false result $7 \equiv 2 {\pmod 10}$. The reason is obvious: the first congruence states that $42-12$ is a multiple of 10, but this does not imply that $\frac{1}{6}(42-12)$ is a multiple of 10. The cancellation of a factor from a congruence is legitimate if the factor is relatively prime to the modulus. For, let the given congruence be $ax \equiv ay {\pmod m}$, where is the factor to be cancelled, and we suppose that a is relatively prime to m. The congruence states that $a(x-y)$ is divisible by m, and hence, $(x-y)$ is divisible by m.

An illustration of the use of congruences is provided by the well-known rules for the divisibility of a number by 3 or 9 or 11. The usual representation of a number n by digits in the scale of 10 is really a representation of n in the form

$n = a + 10b + 100c + \ldots$

where a, b, c, … are the digits of the number, read from right to left, so that a is the number of units, b the number of tens, and so on. Since $10 \equiv 1 {\pmod 9}$, we have also $10^{2} \equiv 1 {\pmod 9}$, and $10^3 \equiv 1 {\pmod 9}$, and so on. Hence, it follows from the above representation of n that

$n \equiv {a+b+c+\ldots} {\pmod 9}$

In other words, any number n differs from the sum of its digits by a multiple of 9, and in particular n is divisible by 9 if and only if the sum of its digits is divisible by 9. The same applies with 3 in place of 9 throughout.

The rule for 11 is based on the fact that $10 \equiv -1 {\pmod 11}$ so that $10^2 \equiv {+1} {\pmod 11}$, and so on. Hence,

$n \equiv {a-b+c- \ldots} {\pmod 11}$

It follows that n is divisible by 11 if and only if $a-b+c-\ldots$ is divisible by 11. For example, to test the divisibility of 958 by 11 we form 1-8+5-9, or -11. Since this is divisible by 11, so is 9581.

Ref: The Higher Arithmetic by H. Davenport, Eighth Edition, Cambridge University Press.

Cheers,

Nalin Pithwa.

# Solution: Intel Pentium P5 floating point unit error (1994): RMO problem !!!

Finally, the much awaited solution is here:

(I re-state the problem from a previous blog, almost a month old):

Two number theorists bored in a chemistry lab, played a game with a large flask containing 2 litres of a colourful chemical solution and an ultra-accurate pipette. The game was that they would take turns to recall a prime number p such that $(p+2)$ is also a prime number. Then, the first number theorist would pipette out $1/p$ litres of chemical and the second $\frac{1}{p+2}$ litres. How many times do they have to play this game to empty the flask completely?

Solution:

It is easy to play this game initially even for ordinary people : one could guess p to be 3 because 5 is a prime number, then 5 and 7, 11 and 13, 17 and 19, 29 and 31, and so on. These are called twin primes. Number theorists need to be there to recall large twin primes. The emptied amount of liquid in litres is given by the twin prime harmonic series $H_{P}^{TP}$:

$H_{P}^{TP} = (\frac{1}{3} + \frac{1}{5}) + (\frac{1}{5} + \frac{1}{7}) + (\frac{1}{11} + \frac{1}{13}) + (\frac{1}{17}+\frac{1}{19}) + \ldots$

This series is known to converge to 1.902160583104…which is known as Brun’s constant, named after Viggo Brun, who proved it in 1919. It is a curious result because it is not known if infinitely many twin primes exist, refer for example,

http://www.math.sjsu.edu/~goldston/twinprimes.pdf

even though it is known that infinitely many primes exist (a result proved by Euclid in 300 BC!) and the harmonic series diverges (a result proved by Euler in the eighteenth century). Had the series $H_{P}^{TP}$ diverged, then one could say that infinite twin primes exist. But, as the series converges (must converge with finitely many twin primes or may converge even with infinitely many twin primes), the question of infinitude of twin primes is still an open one. (there is a recent famous result of Prof. Yitang Zhang also regarding this). Anyway, the point is that the two number theorists would not be able to empty 2 litres even if they play the game for infinitely long period. So, they are not bored and can keep themselves busy in the chemistry lab forever.

Another curious fact about Brun’s constant is that its computation in a computer revealed a floating point division arithmetic error in Intel’s Pentium P5 Floating Point Unit in 1994. This bug was discovered by Thomas Nicely while evaluating the reciprocals of twin primes 824633702441 and 824633702443. Consequently, Intel incurred USD 475 million to fix this bug. For a while in 1995, number theory and Brun’s constant took the centre stage in popular media.

For curious minds, there also exist prime triplets, prime quadruples etc. If four number theorists play the game, they will not be able to empty even 1 litre because the harmonic series of prime quadruples is estimated to be around 0.8705883800.

Reference:

Popular Problems and Puzzles in Mathematics, Asok Kumar Mallik, IISc Press, Foundation Books:

https://www.amazon.in/Popular-Problems-Puzzles-Mathematics-Mallik/dp/938299386X/ref=sr_1_1?s=books&ie=UTF8&qid=1530628680&sr=1-1&keywords=popular+problems+and+puzzles+in+mathematics

# Solution to a “nice analysis question for RMO practice”

The question from a previous blog is re-written here for your convenience.

Question:

How farthest from the edge of a table can a deck of playing cards be stably overhung if the cards are stacked on top of one another? And, how many of them will be overhanging completely away from the edge of the table?

Solution:

The figure below shows how two and three cards can be stacked so that the mass of cards is equal on either side of the vertical line passing through the corner of table’s edge in order to just balance them under gravity:

the set of first two cards are arranged as follows (the horizontal lines represents the cards):

$xxxxxxxxxxxxxxxx\line(5,0){170}$

$\line(5,0){150}xxxxxxxxxxxxxxxxxxx$

the set of three cards are arranged as follows:

$xxxxxxxxxxxxxxxxxxxxxx\line(5,0){150}$

$xxxxxxxxxxxxx\line(5,0){150}$

$\line(5,0){150}xxxxxxxxxxxxxxxxxxxxxx$

We can see that the length of the overhand is a harmonic series of even numbers multiplied by the length of one card, L.

Overhand distance is $(\frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \ldots + \frac{1}{52 \times 2})L$ for 52 cards.

It may be noted that the series if continued to infinity leads to $H_{\infty}^{E}$.

That is, $H_{\infty}^{E}=\frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \ldots$

This series is known to diverge as proved below:

First consider, $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$, which is, greater than

$1+ \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}+ \ldots$, which is greater than $1+ \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \ldots$. Hence, $H_{\infty}$ diverges as we go on adding 1/2 indefinitely.

Now, let $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_{\infty}$

Since $H_{\infty}$ diverges, $H_{E}$also diverges.

Hence, the “overhang series” also diverges.

This means that the cards can be stacked indefinitely and the overhang distance can reach infinity. However, this will happen very slowly as shown in the table below:

$\begin{array}{cc} n^{E} & H_{n}^{E}\\ 2 & 0.5 \\ 10 & 1.46 \\ 100 & 2.59 \\ 1000 & 3.74 \\ 10000 & 4.89 \\ 100000 & 6.05 \end{array}$

Computing the number of cards that completely overhang off the table needs information about the overhang distance for different number of cards. As shown below in the figure, four cards are required to have one card completely away from the edge of the table. This is because $(\frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8}=1.0417 >1)$.

(the set of four cards are arranged as follows:)

$xxxxxxxxxxxxxxxxxxxxxxxxxxxx\line(5,0){150}$

$xxxxxxxxxxxxxxxx\line(5,0){150}$

$xxxxxxxxxx\line(5,0){150}$

$xxxxx\line(5,0){150}$

We can see that the length of the overhang is a harmonic series of even numbers multiplied by the length of one card, L:

Overhang distance = $(\frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \ldots + \frac{1}{52 \times 2})L$ for 52 cards

It may be noted that the series if continued to infinity, leads to $H_{\infty}^{E}$

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

This series is known to diverge. This means that the cards can be stacked indefinitely and the overhang can reach infinity. However, this will happen very slowly as shown in the table below:

$\begin{array}{cc} n^{E} & H_{\infty}^{E} \\ 2 & 0.5 \\ 10 & 1.46 \\ 100 & 2.59 \\ 1000 & 3.74 \\ 10000 & 4.89 \\ 100000 & 6.05 \end{array}$

Computing the number of cards that completely overhang off the table needs information about the overhang distance for different numbers of cards. As shown in the above schematic figures of cards with overhangs, four cards are required to have one card completely away from the edge of the table. This is because

$(\frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8})=1.0417>1$

For the second card to overhang completely, leaving the first card (and hence one half) that is already completely overhung, it is now necessary that

$(\frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \ldots + \frac{1}{2n})>1$, or

$(\frac{1}{2} + \frac{1}{4} + \frac{1}{6} + \frac{1}{8} + \ldots + \frac{1}{2n} )>1+ \frac{1}{2}$

where n needs to be found out. By generating some more data, we can find the value of n to be 11.

For third overhanging card, we need

$(\frac{1}{6} + \frac{1}{8} + \ldots + \frac{1}{2n})>1$ or

$(\frac{1}{2} + \frac{1}{4} + \frac{1}{6}+\frac{1}{8}+ \ldots + \frac{1}{2n})>1+\frac{1}{2} + \frac{1}{4}$

Thus, for m completely overhanging cards, we find n such that $H_{2n}^{E} > 1+ H_{2(m-1)}^{E}$

The table below shows these values wherein we see an approximate pattern of arithmetic progression by 7.

$\begin{array}{cccc} m & n & m & n \\ 1 & 4 & 11 & 78 \\ 2 & 11 & 12 & 85 \\ 3 & 19 & 13 & 92 \\ 4 & 26 & 14 & 100 \\ 5 & 33 & 15 & 107 \\ 6 & 41 & 16 & 115 \\ 7 & 48 & 17 & 122 \\ 8 & 55 & 18 & 129 \\ 9 & 63 & 19 & 137 \\ 10 & 70 & 20 & 144 \end{array}$

By examining the pattern in the table, we can get a simple rule to estimate the number of completely overhanging number of cards m, with an error of utmost one, for n cards stacked.

$m = round(\frac{n}{7.4})=round(\frac{10n}{74})$.

Reference:

Popular Problems and Puzzles in Mathematics by Asok Kumar Mallik, IISc Press, Foundation Books.

Hope you enjoyed the detailed analysis…

More later,

Nalin Pithwa

# Pick’s theorem: a geometry problem for RMO practice

Pick’s theorem:

Consider a square lattice of unit side. A simple polygon (with non-intersecting sides) of any shape is drawn with its vertices at the lattice points. The area of the polygon can be simply obtained as $B/2+I-1$ square units, where B is the number of lattice points on the boundary; I = number of lattice points in the interior region of the polygon. Prove this theorem.

Proof:

Refer Wikipedia 🙂 🙂 🙂

https://en.wikipedia.org/wiki/Pick%27s_theorem

Cheers,

Nalin Pithwa.

# Pre-RMO or RMO algebra practice problem: infinite product

Find the product of the following infinite number of terms:

$\frac{7}{9} \times \frac{26}{28} \times \frac{63}{65} \times \ldots = \prod_{m=2}^{\infty}\frac{m^{3}-1}{m^{3}+1}$

$m^{3}-1=(m-1)(m^{2}+m+1)$, and also, $m^{3}+1=(m+1)(m^{2}-m+1)=(m-1+2)((m-1)^{2}+(m-1)+1)$

Hence, we get $P_{m}=\frac{7}{9} \times \frac{26}{28} \times \frac{63}{65} \times \ldots \times \frac{m^{3}-1}{m^{3}+1}$, which in turn, equals

$(\frac{1}{3} \times \frac{7}{3}) \times (\frac{2}{4} \times \frac{13}{7}) \times (\frac{3}{5} \times \frac{21}{13})\times \ldots (\frac{m-1}{m+1} \times \frac{m^{2}+m+1}{m^{2}-m+1})$, that is, in turn equal to

$\frac{2}{3} \times \frac{m^{2}+m+1}{m(m+1)}$, that is, in turn equal to

$\frac{}{} \times (1+ \frac{1}{m(m+1)})$, so that when $m \rightarrow \infty$, and then $P_{m} \rightarrow 2/3$.

personal comment: I did not find this solution within my imagination !!! 🙂 🙂 🙂

The credit for the solution goes to “Popular Problems and Puzzles in Mathematics” by Asok Kumar Mallik, IISc Press, Foundation Books. Thanks Prof. Mallik !!

Cheers,

Nalin Pithwa