Saturday, June 20, 2015

Problems conceived by me

1. Recall the laws of divisibility by 2-11. Prove them.
2. Devise laws of remainders like "Remainder of a number by 2-11" etc...
    a. [Open problem] Devise law of remainder for 7.
3. Prove Fermat's little theorem,
         `a^p = a (mod p)` where `p` is a prime number.
4. For a number `N = \pi_{i=1}^k p_i^{e_i}`, given the prime number expansion, find out the sum of all factors of `N` (including `1` and `N` itself). Prove that it is,
         `\pi_{i=1}^k [(p_i^{e_i + 1} - 1)/(p_i - 1)]`
5. Sum of reciprocals of all factors of a number is given by,
         `\pi_{i=1}^k [(p_i - p_i^{-e_i})/(p_i - 1)]`.
6. Prove that for a number `N = \pi_{i=1}^k p_i^{e_i}`, the number of factors is given by
          `\pi_{i=1}^k (e_i + 1)`.
7. Only numbers having odd number of factors are ____________ numbers.

Wednesday, November 7, 2012

JEE maths sample paper

Permutations and Combinations.

1. How many numbers less than `n!` are divisible by all prime numbers less than `n`? What is the number for `1000`? Please show the work-out.
2. Prove that `2nCn` is always divisible by `2^{2}`, except when n is a power of 2.
3. Prove that `2^{n+1}C2^{n}` is divisible by 2, but not by 4, for all positive integral values of `n`.
4. Prove that, if `p` is a prime, then for any non-negative number `a`, `(a^p = a) mod p`.
5. Choose integer dimensioned rectangles (both width and height), so that, width `<= 2n` and height `<= 2n`. What is the probability that the resulting rectangle's areas is less than `n^{2}`.
    a. If you were to bet on whether the resulting rectangles area will be less than `n^{2}` or not, what would you bet on?
6. Consider the quadratic equation `ax^2 + bx + c = 0`, with integer (not necessarily positive) co-efficients `a`, `b` and `c`, such that all of them are less than or equal to 100, in absolute value. How many numbers from 1 to 100 are roots of such an equation with some `a`, `b` and `c` combination?
7. Define a nice number as a rational number, with numerator and denominator positive and not exceeding some number. indicates the number of nice numbers, in , What is the formula for N?.
8. Find the number for nice numbers (question 3), when numerator can exceed `x` and denominator can exceed `y`, but they should be reducible to something where they do not exceed `x` and `y`, respectively. If a formula is not possible, give an explanation why?

9. How many 4 digit numbers are there such that, the minimal positive difference between their digits is 1. "minimal" means, if the number is  `abcd`, then taking any combination like, `a + b + c - d` or `a - b - c + d` that results in a positive number, can one get 1? (Use only plus and minus).
10. What is the minimum length (lower bound) of a string of digits, that contains all possible permutations of numbers 1 to 9?
    a. Prove that such a string will be not be more than `9 * 9!` in length.
11. The distance between `2` permutations of numbers `1` to `n`, is defined as the least number of position flips, to make one permutation same as the other. For example, `123` is at a distance of `2` to `231`, because it can be got by first flipping `1` and `2` in `123`, getting `213`, then again flipping `1` and `3`, getting `231`
    a. What is the minimum distance between two distinct permutations from `1` to `n`.
    b. What is the maximum distance between two distinct permutations from `1` to `n`.
    c. What is the sum of all pairwise distances of all permutations of `n` elements, from `1` to `n`. (Distance between `p_{a}` and `p_{b}` is counted only once, not twice).
12. In a `2m` page book, some sheets are missing. In how many ways, some `n` sheets that may be missing from the `2m` page book. (A sheet has `2` pages, no cover for the book).
13. `10000! = (100!)^{k} * p`, for some  positive numbers k, p. Determine the maximum value for k.
14. Find the limit of `1/1! + 1/(1! + 2!) + 1/(1! +2! + 3!) + ...`, when the number of terms in denominator tends to infinity.
15. Prove that `1! + 2! + 3! + ... + n! < 2 * \sqrt{n} * ((n + e) / e)^n` for positive n.
16. Prove that `1! + 2! + 3! + ... + n! > (e + 1)/sqrt_{2 \pi} * (n / e)^n` for positive n.
17. Prove that `(6n + 4) C (3n + 2)` is always divisible by 3.
18. Consider a quadrilateral to be a pythagorean, if all its sides are integers, and diagonal measures are also integers. Find the number of pythagorean quadrilaterals with dimensions (`<= N`).
19. Prove that there are infinitely many values of `n` for which `2nCn` is not divisible by a given odd prime number `p`.
20. Prove that only every 3rd number in fibonacci sequence is divisible by 2, only every 4th is divisible by 3, and every 5th by 5, and every sixth number is divisible by 8. What are the numbers for the lucas sequence? Prove them.  

(Many more sample papers available on purchase). 

Monday, November 5, 2012

Calculus: The concepts of limit and infinity

"Limit n tends to infinity", something that people use often in calculus. And this is what baffles some students as these concepts are unknown to them till the study of calculus starts. It can be said that the other notions of calculus, like continuity and differentiability etc... depend on these concepts, either directly or indirectly. So, it is very important to know and understand these concepts. Here, in this post, I will give a practical perspective on these concepts.

Long ago, someone posed this game: Take Achilles, the greatest of the warriors in Rome, and a Tortoise. Have a race between them. Say who wins? Achilles, right. But someone said otherwise. His argument is as follows:

Let tortoise start a foot ahead of Achilles. Now, start the race, with Achilles slightly behind the tortoise. Now, it takes some time for Achilles to cover the distance of 1 foot and come at par with Tortoise's starting point. Lets say, Achilles takes 1 second to cover 1 feet. But, by then, tortoise would have moved ahead, say to 1/2 foot. Again Achilles needs to cover that 1/2 foot. By the time he covers, tortoise moves ahead again, this time by somewhat smaller amount, like 1/4 foot. Achilles again has to cover that 1/4 foot. So, he reasoned that, whatever Achilles does, the tortoise will still be ahead of him (by a very small margin), and he still needs to cover that distance again. Therefore, Achilles should be losing to the Tortoise, he concluded.

But, we know, in practice that, if a better runner is behind someone in the race, he can overtake them in time.  His argument says that it is impossible,  but we know in practice that, it is not true. So, what is wrong with this argument (apart from being a joke on Achilles)?

A sum of infinite numbers is not always infinity

Lets consider the distances traveled by the tortoise, when Achilles was trying to reach it's current location. More clearly, tortoise moves ahead while Achilles comes to its current position, right? Lets see, how much does it move ahead.

Ok, we know that Achilles speed is 1 foot per second, and lets say tortoise's speed is 1/2 foot per second. And the tortoise is ahead by a foot, at the beginning of the race, as  we said above. Achilles takes 1 second to cover the foot, by which the tortoise is ahead of him. In that 1 second time, the tortoise moves by 1 second * 1/2 foot per second = 1/2  foot distance forward.

Now (After one second), the gap between Achilles and the tortoise is 1/2 foot. Achilles needs to cover this distance. As we know his speed, he takes 1/2 second to cover it. 1/2 second = 1/2 foot / (1 foot per sec). In the same time, tortoise would have moved 1/2 second * 1/2 foot per second = 1/2 * 1/2 foot = 1/4 foot.

Next time, when Achilles gets to the tortoise's last position, it moves ahead by 1/8 foot, as you can verify. (Don't worry if you can't understand this, there is another nicer example ahead).

So, the total distance moved by the tortoise, before Achilles overtakes it, is given by, the sum of these numbers 1/2, 1/4, 1/8 etc... Now, consider the sum of  first 2 terms, it is 1/2 + 1/4 = 3/4 < 1. Now, consider the sum of first three terms 1/2 + 1/4 + 1/8 = 7/8 < 1. First four would give 15/16 < 1. A pattern emerges from these sums, no matter how many of the starting terms you take, you will always get the sum to be less than 1! Isn't that surprising?

Now, consider the time taken by Achilles to travel these distances. Initially there is a gap of 1 foot between him and the tortoise, he takes 1 second (= 1 foot / 1 foot per second) to cover it. Then, it is 1/2 foot (from above), it takes 1/2 second (= 1/2 foot / 1 foot per second) for him to cover it. The times would be like, 1 second, 1/2 second, 1/4 sec, 1/8 sec etc... So, the total time for which he is trailing to the tortoise is the sum of these times, for which he is trying to catch up with it.

Consider the sum of first 2 terms, which is 1 + 1/2 = 3/2 < 2. The first  three terms yield, 1 + 1/2 + 1/4 = 7/4 < 2. First four terms give, 15/8 < 2. A pattern emerges here too, no matter how many of the starting terms you take, you will always get the sum to be less than 2. So, how many ever times he was behind the tortoise, those times; all of them, happened within the first two seconds.


I know what you are thinking. "But, aren't there too many such events, when Achilles is behind the tortoise. So, you mean "infinite" events can happen in a second? How is it even rational?", I can understand what you are saying. This is a perfect example, where theory follows practice.

Often, people do not understand that the theory is in fact, one possible explanation of practice, and try to reason as if the theory is of utmost importance. Any theory, is modeled after practice, takes some concepts from it, and leaves the rest away. The taken concepts form the theory. People miss this simple fact, and go on long ways to justify theories as stand-alone entities themselves.

"And, what kind of an explanation of practice is theory?", one might ask. To which the theoreticians would reply "any kind". "Any kind"!, that is true. Theory is "any kind" of explanation to reality, it does not need to be a practical explanation to practice, a physical explanation to physics, a logical explanation to logic etc... Theory can be "any kind". Exactly here, the concept of infinity comes into picture.

Strictly speaking, we do not know whether an infinite number of events can or can't happen in a second. We simply don't know. But, by assuming that is possible, we can explain the paradox above, that Achilles loses to a tortoise. Since an explanation warrants such an assumption, we assume in theory that, "infinite number of events can happen in a finite interval". This is an example, of theory following practice.

So, according to math, do infinities occur in nature? Yes, they do. They occur every second, when cars  overtake other cars on road, when athletes in Olympics overtake each other, and when Earth rotates around itself. They occur always, around us, everywhere.

A common mis-conception about infinity is that, people use it just like a number. What is tan(90^0)? One would say, it is infinity. As though, infinity can be the value of something. But, this is not right. Maths could assume infinities happen always, but, the properties of infinity mandate that, it be not treated as a number. A reasonable thing to think of infinity would be "something greater than any positive number". There is no number called "infinity" anywhere.

Properties of infinity

(To be continued...)

Monday, October 29, 2012

IIT JEE questions

    Maths online presents IIT JEE practice questions for the aspirants of the distinguished Indian Institute of Technology entrance test. Sample question is given below, please pay 1$ to get access to the questions (total 50 in number). Drop me a comment if you want the questions (and answers).

Sample question: 1. Prove that for every prime \[p, p^{n}\] does not divide \[((p - 1)*n)!\].
2. Define a nice number as a rational number, with numerator and denominator positive and not exceeding some number. \[N(x, y, n)\] indicates the number of nice numbers, in \[[0, n], a/b, a <= x and b <= y\], What is the formula for N?.
3. B.Stat question [Research problem conceived by me AFAIK]. Consider a prime number p. Consider all numbers having it as a factor. Repeatedly sum the digits of those numbers until you get a number less than or equal to p. In this sequence, will you ever get a p?