Morgan Stanley

Here are few puzzles asked in the Morgan Stanley's test yesterday:

1. i) Prove that Trace(A) = sum of eigen values.

ii) If Trace(A)=1, Trace(A^2)=3, Trace(A^3)=9, then find the value of det(A).

2. You have a square matrix of size N x N. From each block you can move to any of the 8 adjacent blocks. Moving to one particular block(zero cost direction) has a cost of zero. Moving to rest of the 7 blocks has cost 1. You have been given two points S and E. You have been also given the zero cost direction for each block. Give an efficient algorithm to find the optimal path from S to E.

3. You have been given [m(m-1)^2+1] points in a Cartesian plane. Each the these points is an integer point i.e. both x and y co-ordinates are integer. Prove that you can always find m points such that centroid of those m-points is also integer point.

4. Let A be a array of integers. Find the minimum of all k-consecutive elements in O(n) time.

Ex: if A=[2 3 5 1 3 5 6] and k=3 then your answer should be [2 1 1 1 3].

Two fathers and their sons

Good to see so many people actually trying out puzzles I posted. Seeing more than 600 hits in 5 days(200 on Sunday) was quite impressive.

Thanks for the suggestions especially regarding the last two posts. For many of you those were very easy puzzles but main motive behind those was to get away from the mathematical point of view and think in a slightly different way. So, if those are easy, then lets solve some easy puzzles.

Some also asked about the solutions of the puzzles I have posted. To solve that problem, I will request the puzzle solvers to put your solutions on the blog rather than discussing it on the chat with me. This way, many people might benefit from your solutions and also, I won't have to write all the solutions by myself.

Here are few more puzzles. Have fun solving puzzles!

1. In a rectangle that's 2 by 200 units long, it's trivial to draw 400 non-overlapping unit-diameter circles. But in the same rectangle, can you draw 401 circles? (non-overlapping, unit-diameter.)

2. Two fathers took their sons to a fruit stall. Each man and son bought an apple, But when they returned home, they had only 3 apples. They did not eat, lost, or thrown. How could this be possible?

3. If F(n) denotes the nth Fibonacci number. Then, prove that F(k*n) is a multiple of F(k).

Please leave your solutions as comments. Thanks!

Logic Puzzles-2

1. Four angels sat on the Christmas tree amidst other ornaments. Two had blue halos and two – yellow. However, none of them could see above his head. Angel A sat on the top branch and could see the angels B and C, who sat below him. Angel B, could see angel C who sat on the lower branch. And angel D stood at the base of the tree obscured from view by a thicket of branches, so no one could see him and he could not see anyone either. Which one of them could be the first to guess the color of his halo and speak it out loud for all other angels to hear?

2. Three Palefaces were taken captive by a hostile Indian tribe. According to tribe’s custom they had to pass an intelligence test, or die. The chieftain showed 5 headbands – 2 red and 3 white. The 3 men were blindfolded and positioned one after another, face to back. The chief put a headband on each of their heads, hid two remaining headbands, and removed their blindfolds. So the third man could see the headbands on the two men in front of him, the second man could see the headband on the first, and the first could not see any headbands at all.
According to the rules any one of the three men could speak first and try to guess his headband color. And if he guessed correctly – they passed the test and could go free, if not – they failed. It so happened that all 3 Palefaces were prominent logicians from a nearby academy. So after a few minutes of silence, the first man in the line said: "My headband is ...".
What color was his head band? Why?

Logic Puzzles

These are not brain teasers and don't require much of knowledge of mathematics. Just common sense is enough to solve each of these.

Have fun solving puzzles!

1. A man who lives on the tenth floor takes the elevator down to the first floor every morning and goes to work. In the evening, when he comes back; on a rainy day, or if there are other people in the elevator, he goes to his floor directly. Otherwise, he goes to the seventh floor and walks up three flights of stairs to his apartment. Can you explain why? (Courtsey Harshvardhan Mandad)

This puzzle is taken from the movie Fermat's Room(nice movie)

2. There are two rooms. In one of the room A, there are three light bulbs and in another room B, there are three switches corresponding to these bulbs. Initially, you are in the room B
How can you identify which switch correspond to which bulb with just one trip to room A.

3. How can you throw a ball as hard as you can and have it come back to you, even if it doesn't bounce off anything? There is nothing attached to it, and no one else catches or throws it back to you.

4. You are in a room with no metal objects except for two iron rods. Only one of them is a magnet. How can you identify which one is a magnet?

Probability Puzzles

1. Alice had some unknown number of unbiased coins with her (say x). And Bob has one more coin with him than Alice. Alice flips all her coins in one go and observes the number of heads and so does Bob. What is the probability that Alice has more number of heads than Bob? (Courtesy Romil Goyal)

2. Bothra and Tiwari are playing a fair game repeated for one paise each game. That is both put one paise in the game, and the winner takes back two paise.

If originally Bothra had A paise and Tiwari had B paise, what is the chances of Bothra winning all of Tiwari's money, assuming that they will play until one person has lost all of his money.

Sorry for the delay in posting the solutions to the earlier puzzles. I will try doing that today. Have fun!

Mantra Treat

Hi all, this is one of the series of puzzles where I will keep some prize on the puzzle. It might be a Gulmohar treat, Mantra treat or a Canteen treat depending on the difficulty of the problem.

Problem in this post is more like a research problem than a puzzle and won't be asked in any interview or written test. So, if you don't want to solve such a puzzle then skip this part and solve the second problem. This problem was part of an R&D project, we are doing with Prof. Nutan Limaye. I and Pritish have been trying this problem for quite some time. Although we have some solutions but optimal solution still seems to be hidden somewhere.

Some definitions:

Depth: Length of the longest path from input to the output.

Problem: Given two numbers in binary form (n bit numbers), can you make a addition circuit using O(n*log(n)) gates in O(1) depth? Only and, or, not gates are allowed. Number of inputs to a gate can be arbitrary large.

No treat for the next puzzle:

2. Does there exist a number of the form 1111.....111 that is divisible by 2097? Explain your answer.

World Quant

First puzzle was asked in the World Quant's test last year. I will post more from that test tomorrow.

1. Let a and b are two real numbers. What is the probability that leading digit of a/b is 1. Leading digit in 0.001980 is 1.

Random Puzzle:

2. There are hundred prisoners and everybody is locked in a different cell. There is a room with a switch which can be either on or off. Initially, the switch is on. Jailer randomly takes one prisoner at a time into the room and ask the following question: "Has everybody been here at least once?"

You can see the state of the switch and decide. If you say yes and all other 99 prisoners have been in the room at least once, you all are saved. But, if not all have been in that room, all die. If your answer is no, then he will give you a chance to toggle the switch. You might toggle or you might not. Then, he locks you to your room. He again takes one random prisoner and do the same.

What should be the strategy of the prisoners such that probability that everybody is eventually saved is 1?

Clarification: Jailer takes a "random" prisoner among 100 prisoner. Same prisoner might be picked twice.

Hello World

I don't have much experience in writing blogs so I will just start with a short description and then some puzzles.

Placement season has been going good for me. Although I am not much interested in joining a company but solving puzzles has been fun. You just have to go, solve some questions and get selected. One of the most striking thing you would notice is attitude of people towards puzzle solving. It has changed drastically since last two months. Usually, if I ask somebody a problem, I get comments like "Kya fart maar raha hai", "such a nerd" (for more click here). But suddenly, everybody seems to be doing puzzles and that too a lot.

So, I thought why not we all do it together. We may find multiple approaches to solve the same problem. Here, I will try posting puzzles of the tests taken by companies, practice questions for the future tests, solutions and some random puzzles and some difficult mathematic problems. If you have some good puzzles and want to share please send them to me. Feel free to comment about anything. Also post your solutions in the comments.

I will start off with some of the questions from yesterday's test. Have fun!

Puzzles from the Optiver test

1. Can you make 25 by using numbers 2,4,6,8 ( using each number exactly once) with the operations +,-,*,/

2. Suppose you and your friend are wearing a hat. I came and marked either 0 or 1 on both the hats. Both the numbers might be same or different. Now, you can see the number on your friend's hat but not your own. Similarly your friend can see number on your hat.

Now, I will ask both of you one question, "What is the number on your hat?". If at least one of you answer correctly then you are saved else I will kill both of you. What will you and your friend do?

Clarification: You and your friend can not communicate after the numbers are written. The only information available is the number on the other person's hat. You can decide the strategy beforehand.

General Case: What if there are n people and the hats are marked from numbers 0 to n-1 ?

Random Puzzle:

3. Consider a town with only one circular street. There are four companies of milk which want to set their business in the town. Density of population is uniform across the circle and every person goes to the nearest store to get the milk. Company A get to chose a location first, then B, then C and finally D. Each company want to have as much as business as possible. Each company knows that others also want the same.

What location should company B choose relative to A?

Clarification: If there are two gaps of equal size left for D, then D will chose at random either one of those. B has to chose according to the worst case scenario.

I will post the solutions tomorrow.