Tuesday, May 26, 2015

Glass half full puzzle

Problem

How can I reduce a cylindrical glass that is 100% filled with water to 50% filled with water without using any kind of measurement instrument?

Solution

Tilt the glass and pour out the water, until the water just touches the bottom surface of the glass, as shown in the picture below. (Picture courtesy - http://www.quora.com/You-have-a-cylindrical-glass-100-full-of-water-How-can-you-make-it-50-half-full-without-using-a-scale-or-any-type-of-measuring-instrument)

Milkmen in India have known solution to this problem for ages. They been using cylindrical 1 Liter measuring cup to give you half liter milk. They fill up the 1 liter cup, and start pouring the milk till they are just able to see bottom of the cup emerge at one corner. That’s it, you got half cup emptied
.

References

Sunday, May 3, 2015

Prove that for every prime p, p>3. p^2-1 is always divisible by 24.

Problem:
Prove that p^2 – 1 is divisible by 24 if p is a prime number greater than 3?

Solution:
We can factorize p^2 - 1 to (p-1)*(p+1) = 2*3.4(k), k is some integer

The most elementary proof , without explicitly mentioning any number theory: out of the three consecutive numbers p–1, p, p+1, one of them must be divisible by 3; also, since the neighbors of p are consecutive even numbers, one of them must be divisible by 2 and the other by 4, so their product is divisible by 3⋅2⋅4=24 — and of course, we can throw p out since it’s prime, and those factors cannot come from it.

Thursday, February 16, 2012

Ant's travel in a grid

 http://tech-queries.blogspot.in/2010/03/ants-travel-in-grid.html

Friday, December 30, 2011

Gold bar with 7 segments


You’ve got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?
Break the 7 piece gold bar to make a piece of 1 segment size and the other of 2 segments size.( the remaining 4 segments intact)
i.e 7= 1 + 2 + 4 (only two breaks needed)
1- 1st day
2- 2nd day
(1+2) - 3rd day
4 - 4th day
(4+1) - 5th day
(4+2) - 6th day
(4+2+1) - 7th day.

Wednesday, December 28, 2011

Pick a Random Byte


Question: You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.
Answer: Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it?
Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time.
When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After picking one, we replace the current stored byte with the one we picked. Now it gets interesting. When we get the third one, it has 1/3 probability of being picked and the one we have stored has a 2/3 probability of being picked. We pick one of the two bytes based on this probability. We can keep doing this forever.
Just generalizing, when we get the nth byte, it has a 1/n probability of being picked and the byte we have stored has (n-1)/n probability of being picked.
Sometimes, this question is a little confusing. The question said you have only space to store one byte but there is an assumption that you have space to store variables to track the number of bytes and so on. Another assumption is that the stream of bytes is not infinite. If not, we won’t be able to calculate (n-1)/n.
If you have suggestions or comments, they are always welcome.

Three Switches

Question: You are standing outside a room next to three switches, all of which are off. Each switch operates a different light bulb in the room. The room door is closed, so you cannot see which switch operates which bulb. You are only allowed to go into the room once. Determine which switch operates which bulb.

Answer: Stumped? The issue lies in the fact that there are only two possible positions for each switch (on or off), but three bulbs to identify. Identifying one bulb is super easy, just set one switch on and then go into the room to check which one is on. But then, how do we detect the other two?

So let’s think deeper, what are the other properties of a light bulb operated by a switch? Light bulbs definitely produce light, but they also produce heat (a not so very important characteristic!). Any chance we can use this idea to help solve our problem? Since a light bulb would take sometime to lose its heat after being switched off, you could still determine if it had ever been on by touching it.

So now, we can easily determine which bulb is operated by which switch. First, we turn the first switch on and leave the other two off. After 5 minutes, we turn the first switch off, turn the second switch on and leave the third switch off. Then we go into the room and touch one of the bulbs which is turned off. After that, it would be easy to tell that the first switch matches the warm bulb, the second switch matches the bulb thats turned on and the third switch matches the colder bulb.



Monday, December 19, 2011

Flipping Coins on the table

There are twenty coins sitting on the table, ten are currently heads and tens are currently tails. You are sitting at the table with a blindfold and gloves on. You are able to feel where the coins are, but are unable to see or feel if they heads or tails. You must create two sets of coins. Each set must have the same number of heads and tails as the other group. You can only move or flip the coins, you are unable to determine their current state. How do you create two even groups of coins with the same number of heads and tails in each group?

Answer: Create two sets of ten coins. Flip The coins in one of the sets over, and leave the coins in the other set alone. The first set of ten coins will have the same number of heads and tails as the other set of ten coins.