## Monthly Archives: June 2016

### The Josephus Problem

The Jewish historian Josephus was trapped in a cave with forty other Jews, all of them trying to evade their Roman conquerors who had captured their place Jotapat. The Jews decided to kill themselves rather than be captured by the invaders. However, Josephus and a friend of his did not wish to die. To avoid expressing dissent in the midst of all present, he suggested a sequential process of killing each a member. He arranged all 41 in a circle and starting with a given person, made the rule that every third man was to be killed. Of course, in this way, the circle would get progressively shorter, till only one person would be left, who was to commit suicide. Josephus placed himself and his friend in such positions with respect to the starting one that they were the last two left and thus escaped. The question is, where were they placed initially?

To solve this problem, number all the positions and progressively eliminate every third one till only two are left. The answer is that the positions 16 and 31 are the last to go. Thus, Josephus and his friends occupied these positions.

We can check this as follows:

The original positions are:

1,2,3,4,5,6,7,8,9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41.

After the last position 41, follows the position 1 in the circle, of course. Now, let us go around the circle once, removing every third number along the way:

1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41.

Continuing to go around the circle the second time, after 40 and 41, the third number is 1, which has to go. So, after the second round, we are left with:

2, 4, 7, 8, 11, 13, 16, 17, 20, 22, 25, 26, 29, 31, 34, 35, 38, 40.

And, so we continue going round and round, and successively reducing the size of the circle:

2, 4, 8, 11, 16, 17, 22, 25, 29, 31, 35, 38.

2, 4, 11, 16, 22, 25, 31, 35.

2, 4, 16, 22, 31, 35.

4, 16, 31, 35.

16, 31.

So, this is the strategy that helped Josephus to plan his own and his friend’s survival!

Ref: Fun and Fundamentals of Mathematics by Jayant V Narlikar and Mangala Narlikar

More fun offered by Professor Narlikar to be shared later,

-Nalin Pithwa

### A little note : IITJEE foundation maths

Example:

Solve $2(x^{2}-6)=3(x-4)$

Solution:

We have $2x^{2}-12=3x-12$

that is, $2x^{2}=3x$ call this as Equation (1)

Transposing, $2x^{2}-3x=0$ $x(2x-3)=0$

Hence, $x=0$, or $2x-3=0$

Thus, the roots are 0 and $\frac{3}{2}$

Note:

In equation (1), above, we might have divided both sides by x and obtained the simple equation $2x=3$, hence, $x=\frac{3}{2}$, which is one of the solutions of the given equation. But, the student must be particularly careful to notice that whenever an x, or a factor containing x, is removed by division from every term of an equation, it must not be neglected, since the equation is satisfied by $x=0$, which is therefore, one of the roots.

More on IITJEE foundation maths later,

Nalin Pithwa

### Some Arithmetic Titbits — as shared by Prof Jayant Narlikar

(Ref: Fun and Fundamentals of Mathematics by Jayant V Narlikar and Mangala Narlikar)

We will look at some interesting games and puzzles involving numbers. They will not entail anything more complicated than the four basic operations of  arithmetic: addition, subtraction, multiplication and division. To set the ball rolling, let us consider a simple three-digit number, any number, whose first and last digits are not the same. Let us take, say, $568$

Now, reverse it to get $865$

Next, subtract the smaller of the two from the other: $865-568=297$ $792+297=1089$.

So, you end up with the number 1089. What is so special about it? Nothing, except that, you always get this number as the final answer, no matter how you started!

Try again with another number, say, with 841. We have the following 4 steps as above:

(1) Reversal: 148

(2) Subtraction: $841-148=693$

(3) Reversal: $396$

(4) Addition: $693+396=1089$.

The answer of the subtraction made at the beginning must, however, be considered as a “three digit number”. If the subtraction gives the answer as 99, it is to be considered as 099. This happens if the difference between the first and the third digits of the original number is 1.

You can use this result as  a guessing game. You can ask your friend to start with any three digit number and perform these operations, in secret, without telling you. Then, you impress him/her by telling him/her the answer!

Race to 50:

Here, is a game that apparently involves addition only, but in reality also requires you to think of a strategy to win. The rules of the game are as follows:

Two players, and B, play it with each alternately adding any number from 1 to 6, to a score, starting from zero. Whosoever adds the number that brings the score to 50 wins.

The game could proceed, for example, as follows: $\begin{array}{cccc} Round \hspace{0.1 in}No & A \hspace{0.1 in }adds & B \hspace{0.1 in}adds & Total \\ 1 & 4 & 0 & 4 \\ 2 & 0 & 5 & 9 \\ 3 & 3 & 0 & 12 \\ 4 & 0 & 6 & 18 \\ 5 & 5 & & 23 \\ 6 & 0 & 2 & 25 \\ 7 & 6 & 0 & 31 \\ 8 & & 4 & 35 \\ 9 & 1 & & 36 \\ 10 & & 3 & 39 \\ 11 & 6 & 0 & 45 \\ 12 & 0 & 5 & 50 \end{array}$

Thus, B wins.

The above is just an example. Now, you should think of a strategy so that you will necessarily win. Is it possible to ensure victory for both A and B?

More fun later with thanks to Professor Narlikar,

Nalin Pithwa

### Cyclic Fractions for IITJEE foundation maths

Consider the expression $\frac{1}{(a-b)(a-c)}+\frac{1}{(b-c)(b-a)}+\frac{1}{(c-a)(c-b)}$

Here, in finding the LCM of the denominators, it must be observed that there are not six different compound factors to be considered; for, three of them differ from the other three only in sign.

Thus, $(a-c) = -(c-a)$ $(b-a) = -(a-b)$ $(c-b) = -(b-c)$

Hence, replacing the second factor in each denominator by its equivalent, we may write the expression in the form $-\frac{1}{(a-b)(c-b)}-\frac{1}{(b-c)(a-b)}-\frac{1}{(c-a)(b-c)}$ call this expression 1

Now, the LCM is $(b-c)(c-a)(a-b)$

and the expression is $\frac{-(b-c)-(c-a)-(a-b)}{(b-c)(c-a)(a-b)}=0$.,

Some Remarks:

There is a peculiarity in the arrangement of this example, which is desirable to notice. In the expression 1, the letters occur in what is known as cyclic order; that is, b follows a, a follows c, c follows b. Thus, if a, b, c are arranged round the circumference of a circle, if we may start from any letter and move round in the direction of  the arrows, the other letters follow in cyclic  order; namely, abc, bca, cab.

The observance of this principle is especially important in a large class of examples in which the differences of three letters are involved. Thus, we are observing cyclic order when we write $b-c$, $c-a$, $a-b$, whereas we are violating order by the use of arrangements such as $b-c$, $a-c$, $a-b$, etc. It will always be found that the work is rendered shorter and easier by following cyclic order from the beginning, and adhering to it throughout the question.

Homework:

(1) Find the value of $\frac{a}{(a-b)(a-c)} + \frac{b}{(b-c)(b-a)} + \frac{c}{(c-a)(c-b)}$

2) Find the value of $\frac{b}{(a-b)(a-c)} + \frac{c}{(b-c)(b-a)} + \frac{a}{(c-a)(c-b)}$

3) Find the value of $\frac{z}{(x-y)(x-z)} + \frac{x}{(y-z)(y-x)} + \frac{y}{(z-x)(z-y)}$

4) Find the value of $\frac{y+z}{(x-y)(x-z)} + \frac{z+x}{(y-z)(y-x)} + \frac{x+y}{(z-x)(z-y)}$

5) Find the value of $\frac{b-c}{(a-b)(a-c)} + \frac{c-a}{(b-c)(b-a)} + \frac{a-b}{(c-a)(c-b)}$

More later,

Nalin Pithwa

### The Game of Four 4s

1.1 The Fourth Ranked King

Perhaps, nothing can give you as much fun and experience of ordinary arithmetic operations as the game of four 4s.

(Professor and eminent scientist) Jayant Narlikar, had come across it when he was in middle school. It was introduced through the following story:

A king was proud of his vast empire, and thought that his was the top-ranking kingdom in the world. He asked the scholars in his court to verify it through a world wide search. In those (pre-internet) days of the past, people had to physically travel to obtain information. And, so  the wise men travelled to the East, to the West, to the North and the South. They returned in due course with the following tidings:

“Your Majesty! Yours is the fourth largest empire on the Earth.”

The  King was disappointed and also furious. He was about to issue commands to behead these bearers of unwelcome tidings, when his Vizier stepped in.

“Sir, it is indeed a happy circumstance that you are ranked Number Four”, he added. “For, if I may be permitted to say so, of the ten primary digits 4 is the most versatile so  far as arithmetical operations are concerned.”

“Explain yourself!”, snapped the king.

The King, whatever his other shortcomings were, was well versed in elementary arithmetic. He would not be easily fobbed off.

So, the Vizier showed him the following game, a game which seemed very simple at first, but grew progressively more involved and interesting.

See for yourself, how far you can progress in the game of four 4s.

1.2 Rules of the Game

The rules of this game are simple. You are to use the number 4, four times in the well established operations of arithmetic. And you are required to construct integers 1, 2, 3, …etc.

What are the permitted operations?

(1) You can, of course, use the four fundamental operations of addition, subtraction, multiplication and division. Thus, you can express zero, one, two and three, as: $4+4-4-4=0$ $\frac{4}{4} \times \frac{4}{4}=1$ $\frac{4}{4} + \frac{4}{4}=2$ $\frac{4+4+4}{4}=3$

II) Next, you can use the square root sign $\sqrt{}$. The fact that 4 is  a perfect square, helps, of course. Thus, you can construct $\sqrt {4}=2$, which may prove useful. The square root sign can cover big expression too, for example, $\sqrt {4+4+\frac{4}{4}}=3$.

Likewise, one can raise expressions to powers, example, $4^{4}=256$

III) The next important operation is of decimalization, both regular and recurring. For example, the following expressions can be useful in constructing some numbers: $\frac{4}{.4}=\frac{4}{\frac{4}{10}}=10$, $\frac{4}{.\overline{4}}=\frac{4}{.444444\ldots}=\frac{4}{\frac{4}{9}}=9$

IV) A very useful permitted operation is the “factorial”. In general, for any integer N, we write $N! = 1 \times 2 \times 3 \ldots \times N$. Therefore, $4! = 1 \times 2 \times 3 \times 4=24$.

That is, about all! In other words, using all these operations on the number 4, use four and only four times, using no other number or symbol, but using parentheses as required, how  far can you go, starting with 1?

1.3 Examples

Just to see, how these operations work, let us try out a few examples:

1.3.1 The number 13

To make 13, we can proceed in many ways. For example, $13 = \frac{4!}{\sqrt{4}}+\frac{4}{4}$

or $13 = 4 + 4 + \frac{\sqrt{4}}{4}$

And, of course, there are other ways. Some are more elegant than others, but as long as an expression is mathematically correct, that is all that matters. You should have no difficulty in reaching 100 or going well past it. See, for example, a way of making a number like 87 next.

1.3.2 The number 87

This may appear difficult at first !! But, practice with smaller numbers will show the way: $87=4 \times 4! - \frac{4}{.\overline{4}}$

Note: $.\overline{4}$ means $.4$ recurring decimal.

Of course, there will come a stage when you are unable to make the next number with four 4s. The larger this number is the better is your score.

1.4 In the end…

The Vizier got the King interested in this game to such an extent that the latter forgot his dismay at being ranked Number 4. And, of course, instead of being punished, the Wise Men were rewarded for their tidings.

1.5 Some problems for you!

Now that you are yourself hooked onto this game, try the following problems:

1. Construct the following numbers using four 4s:
(a) 516 (b) 641 (c) 3634 (d) 2187
2. Instead of four 4s, try working with three 3s. or  five 5s, to see how much better the game was with four 4s.
3. What is the largest number that you can construct with four 4s?

So, are you having fun now? Let me know how far you reached,

Nalin Pithwa

Reference: http://www.amazon.in/Fun-Fundamentals-Mathematics-Narlikar/dp/8173713987/ref=sr_1_1?ie=UTF8&qid=1465735705&sr=8-1&keywords=fun+and+fundamentals+of+mathematics/

### A problem on solutions of triangles (ambiguous case)

Problem 1:

Given $b=16$, $c=25$, $B= 33 \deg 13^{'}$, prove that the triangle is ambiguous and find the other angles, using five figure tables (log/trig).

Nalin Pithwa

PS: Can you check/prove/verify the ambiguous case of solutions of triangles using plane geometry of your high school days?

### Turtles all the way down

Infinity is a slippery idea. People talk fairly casually of “eternity” — an infinite period of time. According to the Big Bang theory, the universe came into being about 13 billion years ago. Not only was there no universe before then — there was “no before” before then. Some people worry about that, and most of them seem much happier with the idea that the universe has always existed. That is, its past has already been long.

This alternative seems to solve the difficult question of the origin of the universe, by denying that it ever had an origin. If something has always been here, it’s silly to ask why it is here now, isn’t it?

Probably. But, that doesn’t explain why it has always been here.

This can be a difficult point to grasp. To bring it into perspective, let me compare it with a rather different proposal. There is an amusing (and very likely true) that a brilliant, famous scientist — Stephen Hawking is often mentioned because he told the story in A Brief History of Time — was giving a lecture about the universe, and a lady in the audience pointed out that the Earth floats in space because it rests on the back of four elephants, which in turn rest on the back of a turtle.

“Ah, but what supports the turtle?”, Stephen Hawking asked.

“Don’t be silly,” she said, “It’s turtles all the way down!”

All very amusing and we don’t buy that explanation. A self-supporting pile of turtles is ludicrous, and not just because it’s turtles. Each turtle being supported by a previous one just doesn’t look like an explanation of  how the whole pile stays up.

Very well. But, now replace the earth by the present state of the universe, and replace each turtle by the previous state of the universe. Oh, and change “support” to “cause”. Why does the universe exist? Because a previous one did. Did all start a finite time in the past? No, it’s universes all the way back.

So, a universe that has always existed is at least as puzzling as one that has not.

Reference: A Brief History of Time by Stephen Hawking

Reference: Professor Ian Stewart’s Cabinet of Mathematical Curiosities.

More later,

Nalin Pithwa

### Solution of Triangles (Ambiguous Cases) : IIT JEE Maths

The three sides a, b, c and the three angles A, B, C are called the elements of the triangle ABC. When any three of these six elements (except all the three angles) of a triangle are given, the triangle is known completely; that is, the other three elements can be expressed in terms of the given elements and can be evaluated. This process is called the solution of triangles.

• If the three sides a, b,  and c are given, angle A is obtained from $\tan{(A/2)}= \sqrt{\frac{(s-b)(s-c)}{s(s-a)}}$ or $\cos{A}=\frac{b^{2}+c^{2}-a^{2}}{2bc}$. B and C can be obtained in a similar way.
• If two sides b and c and the included angle A are given, then $\tan{\frac{B-C}{2}}=\frac{b-c}{b+c}\cot{(A/2)}$ gives $\frac{B-C}{2}$. Also, $\frac{B-C}{2}=90 \deg - \frac{A}{2}$, so that B and C can be evaluated. The third side is given by $a=b \frac{\sin{A}}{\sin{B}}$, or, $a^{2}=b^{2}+c^{2}-2bc \cos{A}$.
• If two sides b and c and the angle B (opposite to side b) are given, then $\sin{C}=\frac{c}{b}\sin{B}$. And, $A=180\deg -(B+C)$, and $a=\frac{b \sin{A}}{\sin{B}}$ give the remaining elements.

By applying the cosine rule, we have: $\cos{B}=\frac{a^{2}+c^{2} - b^{2}}{2ac}$, or if we manipulate this, we get $a^{2}-(2c\cos{B})a+(c^{2}-b^{2})=0$

or, $a=c \cos{B} \pm \sqrt{b^{2}-(c\sin{B})^{2}}$

This equation leads to the following cases:

Case I:

If $b, no such triangle is possible.

Case II:

Let $b=c\sin{B}$. There are further following two cases:

Sub-case II a:

B is an obtuse angle, that is, $\cos{B}$ is negative. There exists no such triangle.

Sub-case II b:

B is an acute angle, that is, $\cos {B}$ is positive. There exists only one such triangle.

Case III:

Let $b >c \sin{B}$. There are following two cases further here also:

Sub-case IIIa:

B is an acute angle, that is, $\cos {B}$ is positive. In this case, two values of a will exist if and only if $c\cos{B} > \sqrt{b^{2}-(c \sin{B})^{2}}$ or, $c>b$, which means two such triangles are possible. If $c, only one such triangle is possible.

Sub-case IIIb:

B is an obtuse angle, that is, $\cos{B}$ is negative. In this case, triangle will exist if and only if $\sqrt{b^{2}-(c \sin{B})^{2}} > c |\cos{B}| \Longrightarrow b > c$. So, in this case, only one such triangle is possible. If $b , there exists no such triangle.

Note:

If one side a and angles B and C are given, then $A=180 \deg -(B+C)$, and $b=a \frac{\sin{B}}{\sin{A}}$ and $c=a\frac{\sin{C}}{\sin{A}}$.

If the three angles A, B and C are given, we can only find the ratios of the three sides a, b, and c by using the sine rule(since there are infinite number of similar triangles possible).

More theory later,

Nalin Pithwa

### Don’t get the goat

There used to be an American game show, hosted by Monty Hall, in which the guest had to choose one of three doors. Behind one was an expensive prize — a sports car, say. Behind the other two were booby prizes — goats.

After the contestant had chosen, Hall would open one of the other doors to reveal a goat. (With two doors to choose from, he could always do this — he knew where the car was.) He would then offer the contestant the chance to change their mind and choose the other unopened door.

Hardly, any one took this opportunity — perhaps, with good reason, as I will eventually explain. But, for the moment, let’s take the problem at face value, and assume that the car has equal probability (one in three) of being behind any given door. We will assume also that every one knows ahead of time that Hall always offers the contestant a change to change their mind, after revealing a goat. Should they change?

The argument against goes like this: the two remaining doors are equally likely to conceal a car or a goat. Since the odds are fifty-fifty, there’s no reason to change.

Or, is there?

(thanks to Prof Ian Stewart for such a nice little puzzle in probability theory).

### Are hard problems easy ? Or, how to win a million dollars by proving the obvious.

Actually, it is not that obvious. TANSTAAH, as science fiction author Robert A. Heinlein used to say — There Ain’t No Such Thing As A Free Lunch. But we can all dream.

I am referring here to one of the seven Millennium Prize Problems, whose solution will leave some lucky person a million dollars better off. Technically, it is known as “P=NP?” which is a pretty silly name. But, what it’s about is of vital importance: inherent limits to the efficiency of computers.

Computers solve problems by running programs, which are lists of instructions. A program that always stops with the right answer (assuming that the computer is doing what its designers think it should) is called an “algorithm”. The name honours the Arabic mathematician Abu Ja’far Muhammad ibn Musa al-Khwarizmi, who lived around AD 800 in present day Iraq. His book Hisab al-Jabr w’al-muqabala gave us the word “algebra”, and it consists of a series of procedures — algorithms — for solving algebraic equations of various kinds.

An algorithm is a method for solving a specific type of problem, but it is useless in practice unless it delivers the answer reasonably quickly. The theoretical limit issue here is not how fast the computer is, but how many calculations the algorithm has to perform. Even for a specific problem —- to  find the shortest route that visits a number of cities in turn, say —- the number of calculations depends on how complicated the question is. If there are more cities to visit, the computer will have to do more work to find an answer.

For these reasons, a good way to measure the efficiency of an algorithm is to work out how many computational steps it takes to solve a problem of a given size. There is a natural division into “easy” calculations, where the size of the calculation is some fixed power of the input data, and “hard” ones, where the growth rate is much faster, often exponential. Multiplying two n-digit numbers together, for example, can be done in $n^{2}$ steps using good old-fashioned long multiplication, so this calculation is “easy”. (Ref: Number Theory and Cryptography by Neal Koblitz for beautiful, illustrative examples on the “number of elementary computations” required for addition, subtraction, multiplication and division).  Finding the prime factors of an n-digit number, on the other hand, takes about $3^{n}$ steps if you try every possible divisor up to the square root of n, which is the most obvious approach, so this calculation is “hard”. (If you like programming, you can use the previous mentioned book of Neal Koblitz; also, “The Little Book of BIGGER Primes” by Ribenbohm; also, “How to Solve it by Computer” by R. G. Dromey — it gives a lucid explanation of computational complexity, efficiency of programs, so also you can write programs on “factoring methods”). The algorithms concerned here are said to run in polynomial time (class P) and non-polynomial time (non-P) respectively.

Working out how quickly a given algorithm runs is relatively straight forward. The hard work is to decide whether some or other algorithm might be faster. The hardest of all is to show that what you have got is  the fastest algorithm that will work, and basically we don’t know how to do that. So, problems that we think are hard might turn out to be easy if we found a better method for solving them, and this is where the million dollars comes in. It will go to whoever manages to prove that some specific problems is unavoidably hard — that no polynomial time algorithm exists to solve it. Or, just possibly to whoever proves that “There Ain’t No Such Thing As A Hard Problem — though that doesn’t seem likely, the  universe being what it is.

Before you rush out to get started, though, there are a couple of things you should bear in mind. The first is that there is a “trivial” type of problem that is automatically hard, simply because the size of the output is gigantic. “List all ways to  rearrange the first n numbers” is a good example. However fast the algorithm might be, it takes at least $n!$ steps to print out this answer. So, this kind of problem has to be removed from consideration, and this is done using the concept of a non-deterministic, polynomial time, or NP problem. (Note that NP  is different from not-P). These are the problems where you can verify proposed answer in polynomial time — that is, easily.

My favourite example of an NP problem is solving a jigsaw puzzle. It may be very hard to find a solution, but if someone shows you an allegedly completed puzzle you can tell instantly whether they have done it right. A more mathematical example is finding a factor of a number (once again: refer to “How to solve it by computer” R. G. Dromey for programming examples/assignments based on factoring methods): it is much easier to divide out, and see whether some number works than it is to find that number in the first place.

The “P=NP?” problem asks whether every NP problem is P. That is, if you can check a proposed answer easily, can you find it easily? Experience suggests very strongly that the answer should be “no” — the hard part is to find the answer. But, amazingly, no one knows how to prove that (as yet), or even whether it is correct. And, that’s why you  can pocket a million bucks for proving that P is different from NP, or indeed for proving that, on the contrary, the two are equal.

As a final twist, it turns out that all likely candidates to show that $P \neq NP$ are equivalent (in some sense). A problem is called NP-complete if a polynomial time algorithm to solve that particular problem automatically leads to a polynomial-time algorithm to solve any NP problem. Almost any reasonable candidate for proving that $P \neq NP$ is known to be NP-complete. The nasty consequence of this fact is that no particular candidate is likely to be more approachable than any of the others — they all live or die together. In short, we know why $P=NP?$ must be a very hard problem, but that doesn’t help us to  solve it.

I suspect that there are far easier ways to make a million dollars 🙂 🙂 🙂

More later,

Nalin Pithwa

Ref: Professor Ian Stewart Cabinet of Mathematical Curiosities

Other Ref: The Millennium Problems: The Seven Greatest Unsolved Mathematical Problems of our Time by Keith J. Devlin

http://www.amazon.in/s/ref=nb_sb_ss_i_1_8/277-6217103-8548915?url=search-alias%3Dstripbooks&field-keywords=keith+devlin&sprefix=keith+de%2Caps%2C260