Cigars on Circular Table

Problem

Let's say we play a simple game. I have a circular table and an unlimited supply of identically shaped Cuban cigars. We each take turns placing a cigar on the table without disturbing any other cigars already there in the process and without overlapping any pair of cigars. The winner will be last person to successfully place a cigar on the table subject to the given restrictions. If I give you the option of going first, how would you play in order try and win

 

Solution

Since the circle is symmetric.around the centre..except the centre there would always be one position exactly symmetric and opposite..to place the cigar..

1. So i will start by placing the CIGAR in the centre in the first move.
2. My Consecutive moves would be governed by where the other person is placing the cigar..i would place the cigar,symmetrically opposite to where he is placing in each move.

 

References

• http://sudhansu-codezone.blogspot.in/2011/12/cigars-on-circular-table.html

 

Read More

Measure 45 minutes

Problem

You have two strings of rough non-countinuous composition (in other words these strings are not ideally uniform.) You know that each will take exactly half an hour to burn no matter which end is lit. How can you measure a time interval of 45 minutes with
1.2 match sticks available
2.only one match (which only sustains a flame for a few seconds)

Solution

Solution with 2 matches...
Old solution for 2 matches.
1.Burn one string full..measure 30 min.
2. Burn second string from both sides..and measure 15 min.
3. Total time measure = 45 min.

Idea - Now we have one match..which means we can light it only once..some how we have to make sure that after the first string is burn...the second one start's with the left over fire of the first.

Solution - Make a ring of the second string and tie it up at the end of the first string.
1. First string will burn in 30 min.
2. When the first string ends, the second string is a ring so it would start off to burn at both the ends parallely and would end in 15 min.
3. Total time = 30 + 15 = 45, 1 match used.

References

• http://sudhansu-codezone.blogspot.in/2011/12/measure-45-minutes.html

Read More

Cards with Vowel & Even number

Problem

There are 4 cards on a table. Each has a number on one side and a letter on the other. The cards show A,B,1 and 2. Which 2 cards would you turn over to test the rule that "All cards with a vowel on one side have an even number on the other".

 

Solution

A and 1, since by elimination...

1.we have to take A as if there is a odd no.. back of A then our rule get's violated so without picking A we can't be sure that our rule holds good.

2. B we can leave since it doesn't satisfy the rule at all, doesn't have a vowel so it really doesn't matter whether it has a even number on the other side; eliminate it.

3. 2, also we can eliminate since if it has a consonant on the other side..then also...our rule doesn't violate..since converse of our rule is not true..(if it a even no. on one side then it has to have a vowel on the other). However if 2 has a vowel on the other side..then our rule holds good..so without picking 2 we can be sure that our rule would hold good in case of 2; hence eliminate that.

4. 1, however we can't go away with 1; since if it has a VOWEL on the back side..then our rule would violates..so we can be sure by picking 1 along with A to make sure..that

hence Ans = A,1

References

• http://sudhansu-codezone.blogspot.in/2011/12/cards-with-vowel-even-number.html

 

Read More

Wire Connections

Problem

There are 66 wires connecting from the top floor to the ground floor. You can see the ends of the wires but you don't know which one on the ground floor connects to which one on the top floor. You can tie the ends of several wires together and test the connections at the other end by using a bulb and battery. For example, if you first tie wires A, B, and C together at the ground floor and then go up to the top floor, you will figure out that the bulb will light if you put it between A and B, A and C, or B and C. You can do the reverse thing by tying the ends at the top floor and test on the ground. Assume you start at ground floor with none of the wire tied, what's the minimum number of trips up and down you need to make before you can figure out all the connections from the ends on the top floor to the ends on the ground floor, which is a one-to-one mapping between them?

What happens if the number of wires is 67......

Read More

OLD MONKS

Problem

There are monks in a monastry who don't speak(or communicate in any sense) with each other and have no have no mirrors or any reflective surface at their disposal. Evn the water they drink is from a "surahi" type pitcher(the opening is narrow and no reflection can be seen) and the floor is of extremely porous clay so that if u drop water to see reflection, the ground soaks it up so fast that it won't work.Now their leader is allowed to speak and he tells them that some monks have been infected with a disease that has marked their forehead and that they should leave of their own accord. But they are not told who is infected. If there are n monks how many days it takes for them to realise that they are infected and leave ?

 

Solution

 

Read More

Handshakes at Party

Problem

I was at a party with MS one evening where he got bored and started keeping track of the number of handshakes made by people. A person was called "odd person" if he made an odd number of handshakes, otherwise he was called "even person". After some time MS said to me, "Hey AD, do you know that there are an even number of odd persons?" I replied, "Big deal, MS. There will be always an even number of odd persons!" But still he seemed confused. Justify ...


 SAME NUMBER OF HANDSHAKES-------------------------
At a dinner party, many of the guests exchange greetings by shaking hands with each other while they wait for the host to finish cooking.
After all this handshaking, the host, who didn't take part in or see any of the handshaking, gets everybody's attention and says: "I know for a fact that at least two people at this party shook the same number of other people's hands."
How could the host know this? Note that nobody shakes his or her own hand.

Read More

Key Exchange Puzzle

Problem

Jan and Maria have fallen in love (via the internet) and Jan wishes to mail her a ring. Unfortunately,
they live in the country of Kleptopia where anything sent through the mail will be stolen unless it
is enclosed in a padlocked box. Jan and Maria each have plenty of padlocks, but none to which the
other has a key. How can Jan get the ring safely into Maria's hands?

Solution

Diffe Hilemann key exchange work's in a similar way...

Jan sends the ring in a box with padlock A. Maria receives it she put her padlock B and sends it back to Jan. Jan opens his padlock A and send it back to Maria, who then opens her padlock B to get the ring.

References

• http://sudhansu-codezone.blogspot.in/2011/12/key-exchange-puzzle.html

Read More

Russian Roulette

Problem

Lets play a game of Russian roulette. You are tied to a chair and can't get up. Here is the gun , six chambers all empty. Now I put two bullets in the gun and I put these bullets in the adjacent chambers. I close the barrel and spin it. I put the gun to your head and pull the trigger. Click and the slot was empty. Now before we start the interview I want to pull the trigger one more time , which one do you prefer , that I spun the barrel first or that I just pull the trigger ?

What happens if  the two bullets aren't adjacent to each other in the barrel.... 

 

Solution

1st Case:
Possible combinations of both bullets
1,2
2,3
3,4
4,5
5,6
6,1


Don't Spin case
---------------

Since you are not shot in the first one so (6,1)& (1,2) doesn't have the bullet's and they are in one of the other possible 4 slots

P(death)=1/4 = .25
p(survival)= .75

Spin it case-
-------------
P(death)=2/6=1/3 = .33
p(survival) = .77

So don't spin it.

2nd case:
Don't Spin It case
------------------
Not hit in the first case so
P(death) in second hit = 2/5 = .4

Spin it case
--------------
P(death) in second hit = 2/6 = .3

So he should spin it if bullets aren't adjacent

References

• http://sudhansu-codezone.blogspot.in/2011/12/russian-roulette.html

Read More

Ages of Sons

Problem

There are two guys standing before a building with multiple floors.
First: "I have three children, the product of their ages is 36, can you guess their ages?"
Second: "No"
First: "The sum of their ages is equal to the number of floors in the opposite building, can you guess now?"
Second: "No"
First: "My youngest son is a very good dancer"
Second: "Yeah, I know now"
Assuming that both these guys are extremely intelligent and follow common-sense logic to find out the ages of first's children.

Read More

Cut a rectangular Cake

Problem

How do you cut a rectangular cake into two equal pieces when someone has already taken a rectangular piece from it?
The removed piece an be any size or at any place in the cake. You are only allowed one straight cut. 

 

Solution

Join the centers of the original and the removed rectangle. It works for cuboids too!

References

• http://sudhansu-codezone.blogspot.in/2011/12/cut-rectangular-cake.html

Read More

Truth AND Lies

Problems

1.When a person has to find out which of the two paths lead to his destination and there are two guys sitting there, one of which always speaks the truth and the other always lies. What is the single question he can ask to reach his aim?

2.There are two ways (like previous question). One right and the other wrong. But there are 3 guys. One will always speak the truth or keep mum(if he does not know the answer). One will always lie or keep mum(if he does not know the answer). The third will never keep mum and may speak the truth or lie with equal probability. You can ask two questions. Find out your destination.

3.There are three people named Larry, Curly and Moe. One always tells the truth, one always tells a lie and the other gives unpredictable answers, but all of them can only answer yes or no questions (with yes or no). Like any classic Smullyan puzzle (from whom I believe this problem originates), the goal is to ask a certain number of questions to figure out who is who. In this case, the three know who is which and now you are allowed three yes or no questions (each directed to only one of the three at a time) to figure it out for yourself. How's do you do it?

4.You are now quite definitely talking to True, but he refuses to
answer you in English and will only say da or ja. What one yes-no question can you
ask True to determine whether or not Dushanbe is in Kirghizia?

5.Suppose that, somehow, you have learned that you are speaking not
to Random but to True or False — you don’t know which — and that whichever
god you’re talking to has condescended to answer you in English. For some reason,
you need to know whether Dushanbe is in Kirghizia or not. What one yes-no
question can you ask the god from the answer to which you can determine whether
or not Dushanbe is in Kirghizia

Solution

SOLUTION FOR 1------------------
He asks to any one "What would the other guy say if I ask him the direction to my address?" and take the opposite of the answer he gets.

SOLUTION FOR 2------------------
Idea - In the first question you should be able to eliminate the random guy; so that you are sure that next question you ask is asked to either of TURE or FALSE guy.

Idea2 - The second question should be asked to one guy and only in his context...

Question1. Is B more likely to tell the truth than C. If the answer is YES choose C else choose B.

Now let's consider all the possible cases in this scenario

A B C
----------------
T T/F F (Expected Ans=YES, A's answer = YES; CHOSEN=C.)
T F T/F (Expected Ans =NO, A's answer = NO; CHOSEN=B.)
------------------
F T/F T (Expected Ans=No, A's answer = YES(since A is liar); CHOSEN=C)
F T T/F (Expected Answer=Yes, A's answer=NO(since A is liar); CHOSEN=B
--------------------
T/F T F
T/F F T
In the above 2 cases you would have chosen any of B and C it doesn't matter since they would be either T or F

Conclusion from Question 1- We are always getting CHOSEN guy as either T or F guy so in the first question we have removed the chance of RANDOM to be the second guy whom we ask).

Question2.Are you TRUE iff(if and only if) This is the correct path.

let's call
Are you TRUE as Stmt1
This is correct Path as Stmt2.

Remember how iff works..it would be TRUE if both the statements in between iff is put are TRUE or BOTH are false..if one is TRUE and the other is FALSE then iff would be FALSE...

Consider all the possible cases since our CHOSEN guy can be either of TRUE or FALSE so the following four cases.

Case1. True guy and CorrectPath = Both Satement's (Stmt1 and Stmt2)are TRUE so Answer = YES

Case2. True guy and IncorrectPath=
(Stmt1 is TRUE and Stmt2 is FALSE)
so Answer = NO

Case3. False guy and CorrectPath=
(Stmt1 is False and Stmt 2 is True)..Expected Answer = NO, but he guy whose replying is a liar so ANSWER= YES

Case4. False guy and IncorrectPath=
(Stmt1 is False and Stmt2 is False)..Expected Ans= YES, but liar will say ANSWER=NO.

Now from above Case1..4 we see that if we get a YES for Question2 we take that path else we take the opposite path..will always help us get the right path.

SOLUTION FOR 3-----------------------
T = truth guy
F = false guy
R = random guy

our guys A B C
ask the same first question to know who is the guy which is definitely not the random guy.. say A

so A is T/F

now ask A "Is B more likely to say the truth than C"
===============
if ans is "yes"

if A = T B=R C=F
if A = F B=R C=T
==============
if ans is "no"

if A = T B=F C=R
if A = F B=T C=R

so if A answers yes B is the random guy else C is the random guy

once we know who is random ask the third question to any of the other 2 guys.

the 3rd question should be an obvious question like "is 2+3=5?"

if the guy answers "yes" he is T else F ----------------

References

• http://sudhansu-codezone.blogspot.in/2011/12/truth-and-lies.html

Read More

Rope Around EARTH

Problem

A fool wants to tie a rope around the earth. So he buys a rope of 40,000 KM and ties it around the world. His neighbour, also a fool, wants to do the same only he wants the rope on sticks 1 meter above the ground.
How much more rope does he need?

 

Solution

The outline of a circle is 2*PI*r. If you want a rope that is one meter above the ground rnew=r+1. So you need 2*PI*(r+1)-2*PI*r more rope.
So,
x=2*PI*(r+1)-2*PI*r
x=2*PI*r+2*PI-2*PI*r
x=2*PI
x=6.28
It does not matter what the radius of the circle is. You always need 2*pi more rope.

References

http://sudhansu-codezone.blogspot.in/2011/12/rope-around-earth.html

Read More

THE DEVIL & COLORED HATS

100 people find themselves at the gates of hell. The devil tells them that they'll have a chance to go to heaven instead, but first they'll have to play a game.
The devil is going to line them all up in a straight queue, each person facing the back of the next person in line. The order of people in this line will be randomly chosen when the game starts.
He is then going to put a red or blue hat on each person. Each hat can be red or blue at random. Nobody knows the color their hat will be before the game starts.
Each person will be able to see the hat of everyone in front of them, but won't be able to see the hats of anyone behind them. Everyone can hear everyone else.
The devil will then then ask each person the color of their hat, starting at the back of the line and moving forward. Each person must just say "red" or "blue", without any extra intonation. People cannot communicate at all beyond merely saying the word "red" or "blue". If a person correctly says the color of their own hat, then they will be sent to heaven;; if they get the color wrong they stay in hell.
Before the game starts, the people are allowed to come up with a strategy to save as many people as possible. One man proposes that every other person says the color of the hat of the person in front of them, and then the people in between repeat that color to save themselves. "That will save a guaranteed 50 people, and will probably save around 75," he says.
"No," a woman says. "I've got a plan that is guaranteed to save 99 of us, maybe all of us."
What is the woman's plan?

Read More

Black and white hats - Who knows what he is wearing

There are four man standing in front of a firing-squad. Two of them (nr.1 & 3) wear a black hat and two of them (nr.2 & 4) wear a white hat. They are all facing the same direction and between nr.3 and nr.4 stands a brick wall (see picture). So nr.1 can see nr.2 & 3, nr.2 sees nr.3, nr.3 sees only the wall and nr.4 doesn't see a thing. The men know that there are two white and two black hats.
The commander of the firing-squad is willing to let the men go if one of them can say what color hat he is wearing. The men are not allowed to talk. The only thing they may say is "I'm wearing a white/black hat". If one of the men knows which hat he is wearing he must tell it and all men will be free.
Which man knows 100% sure what color hat he's wearing?

Variant
In a variant of this puzzle there are 3 hats of one colour and only 1 hat of another, and the 3 prisoners can see each other i.e. A sees B & C, B sees A & C and C sees A & B. (D again not to be seen and only there to wear the last hat

Read More

Prisoners and Boxes

You are the janitor at a prison with 100 prisoners locked in separate, soundproof and windowless cells.
You watch one day as the warden brings the prisoners out to a central room where there are 100 boxes laid out, labeled 1 through 100. He hands each prisoner a slip of paper and a pen, and asks everyone to write their name on their slip and hand it back to him. All the prisoner's have different names.
The warden then makes a proposition to the prisoners. He will put them back in their cells and will put each of the 100 slips of paper into a different box. The prisoners will then be brought out one by one in a random order. When a prisoner comes out, he will get to open 50 boxes. He doesn't need to preselect which boxes he'll open; he can choose as he goes along. He is also not allowed to rearrange the boxes or the names as he does this.
If any of the 50 boxes he opens contains the slip with that prisoner's name on it, then that prisoner "passes" the test. He will be sent back to his cell, all of the boxes will be closed, and the next prisoner will be brought out. However, if any prisoner opens 50 boxes and none of them contain his name, then all 100 prisoners will be executed. Note that prisoners have no way of passing information on to any of the prisoners who go after them.
If all of the prisoners are able to "pass" the test, then they will all be set free, and you'll receive a big promotion.
Luckily for the prisoners, the warden is going to let you help them in the following way. After he's put all of the names in the boxes, he will bring you into the room, let you look at all the names in all the boxes, and then, if you choose to, switch two names with each other. For example, you could switch the names in boxes 35 and 77. You are only allowed to make one switch.
After you help with this task, you will be sent out of the prison and will not be able to communicate with the prisoners.
Before this strange game begins, you get to meet with the prisoners to discuss a strategy. This strategy must have two parts:

1. How do you decide which names to switch, if any at all?
2. How does each prisoner decide which 50 boxes he will open?

What plan do you come up with to ensure that the prisoners will all go free?

Read More

Prisoner and lightbulb

Problem

There is a prison with 100 prisoners, each in separate cells, which are sealed off, soundproof and windowless. There is a lobby in the prison with a lightbulb in it. Each day, the warden will pick one of the prisoners at random (even if they have been picked before) and take them out to the lobby. The prisoner will have the choice to flip the lightbulb switch if they want. The lightbulb starts in the "off" position.
When a prisoner is brought out to the lobby, he also has the option of saying "Every other prisoner has been brought out to the lobby." If a prisoner chooses to say this and it is true, all the prisoners will go free. However, if a prisoner chooses to say this and it's wrong, all the prisoners will be executed. So a prisoner should only say this if he knows it is true for sure.
Before the first day of this process begins, all the prisoners are allowed to get together to discuss a strategy to eventually save themselves.
What strategy could they use to ensure their eventual salvation?

Solution

Make one of the prisoners the "lead" prisoner. This prisoner is the ONLY one who is allowed to turn the light off.

Each time any of the other prisoners goes into the lobby, if the light is off, they will turn the light on, but only if they've never turned it on before. This means that each prisoner will only ever turn the light on once.

Meanwhile, every time the lead prisoner goes into the lobby, he will turn the light off if it's on. He will keep track of the number of times he has turned the light off.

Once the lead prisoner turns off the light for the 99th time, he knows that every other prisoner has turned the light on once (and thus has been in the lobby). At this point, he may say that all the prisoners have been to the lobby, and they will all go free.

Read More

Any five Cards

Problem

You meet a magician and his assistant, who decide to show you a trick.
The assistant leaves the room, and the magician hands you an ordinary deck of 52 cards. He has you choose any 5 cards from the deck and give them to him.
He looks over the 5 cards you chose, takes one of them, and hands it back to you.
"That going to be your card," he says. He asks you to put it in your pocket out of sight.
He then takes the four remaining cards and arranges them in a stack in a special order. All four cards in the stack are face-down.
He hands you the stack of four cards and asks you to place them on the table however you like (as long as you don't change the order). He then calls the assistant back in. The assistant picks up the four cards, looks them over, and promptly tells you what your card is.
Note that the magician did not do anything extra to communicate information to the assistant. The only information the assistant has in figuring out your card is the order of the four cards on the table.
How was the assistant able to figure out your card?

Read More

Travelling MONK

A monk leaves at sunrise and walks on a path from the front door of his monastery to the top of a nearby mountain. He arrives at the mountain summit exactly at sundown. The next day, he rises again at sunrise and descends down to his monastery, following the same path that he took up the mountain.
Assuming sunrise and sunset occured at the same time on each of the two days, prove that the monk must have been at some spot on the path at the same exact time on both days.

Read More

Leap year Birthday

Problem

Bill and Stacie are delighted when their new baby, Patrick, is born on February 29th, 2008. They think it's good luck to for him to be born on the special day of the leap year. But then they start thinking about when to celebrate his next birthday. After some thought, they decide that they want to celebrate Patrick's next birthday (when he turns 1) exactly 365 days after he was born, just like most people do.
What will be the date of this birthday?

Answer

28th, 2009.

Solution

 At first it might seem like his birthday should be March 1st, 2009, since February 29th is the day after February 28th in the leap year, while March 1st is the day after February 28th in non-leap years. But this is the wrong way to think about it.
The right way to think about it is that 365 days after the day before March 1st is always February 28th, regardless of whether it's a leap year or not. So Patrick's birthday will be February 28th

 

Read More

Crossing the BRIDGE past the GUARD

Problem

A guard is stationed at the entrance to a bridge. He is tasked to shoot anyone who tries to cross to the other side of the bridge, and to turn away anyone who comes in from the opposite side of the bridge. You are on his side of the bridge and want to escape to the other side.
Because the bridge is old and rickety, anyone who tries to cross it does so at a constant speed, and it always takes exactly 10 minutes to cross.
The guard comes out of his post every 6 minutes and looks down the bridge for any people trying to leave, and at all other times he sits in his post and snoozes. You know you can sneak past him when he's sleeping, but the problem is that you won't be able to make it all the way to the other side of the bridge before he sees you (since he comes out every 6 minutes, but it takes 10 minutes to cross).
One day a brilliant idea comes to you, and soon you've successfully crossed to the other side of the bridge without being shot. How did you do it?

Solution

walk for 5 minutes than walk for 1 minute to the opposite side. The guard will turn you away from the bridge.

Read More

NEWYORK HAIR (Pigeonhole Principle)

Problem

You are visiting NYC when a man approaches you.
"Not counting bald people, I bet a hundred bucks that there are two people living in New York City with the same number of hairs on their heads," he tells you.
"I'll take that bet!" you say. You talk to the man for a minute, after which you realize you have lost the bet. What did the man say to prove his case?

Solution

This is a classic example of the pigeonhole principle. The argument goes as follows: assume that every non-bald person in New York City has a different number of hairs on their head. Since there are about 9 million people living in NYC, let's say 8 million of them aren't bald.

So 8 million people need to have different numbers of hairs on their head. But on average, people only have about 100,000 hairs. So even if there was someone with 1 hair, someone with 2 hairs, someone with 3 hairs, and so on, all the way up to someone with 100,000 hairs, there are still 7,900,000 other people who all need different numbers of hairs on their heads, and furthermore, who all need MORE than 100,000 hairs on their head.

You can see that additionally, at least one person would need to have at least 8,000,000 hairs on their head, because there's no way to have 8,000,000 people all have different numbers of hairs between 1 and 7,999,999. But someone having 8,000,000 is an essential impossibility (as is even having 1,000,000 hairs), So there's no way this situation could be the case, where everyone has a different number of hairs. Which means that at least two people have the same number of hairs.

 

Read More

Paying with RINGS

Problem

A man comes to a small hotel where he wishes to stay for 7 nights. He reaches into his pockets and realizes that he has no money, and the only item he has to offer is a gold chain, which consists of 7 rings connected in a row (not in a loop).
The hotel proprietor tells the man that it will cost 1 ring per night, which will add up to all 7 rings for the 7 nights.
"Ok," the man says. "I'll give you all 7 rings right now to pre-pay for my stay."
"No," the proprietor says. "I don't like to be in other people's debt, so I cannot accept all the rings up front."
"Alright," the man responds. "I'll wait until after the seventh night, and then give you all of the rings."
"No," the proprietor says again. "I don't like to ever be owed anything. You'll need to make sure you've paid me the exact correct amount after each night."
The man thinks for a minute, and then says "I'll just cut each of my rings off of the chain, and then give you one each night."
"I do not want cut rings," the proprietor says. "However, I'm willing to let you cut one of the rings if you must."
The man thinks for a few minutes and then figures out a way to abide by the proprietor's rules and stay the 7 nights in the hotel. What is his plan?

Solution

He cuts ring number 3 (OO | O | OOOO).
1st night: O.
2nd: OO
3rd: OO O.
4th: OOOO
5th: O OOOO.
6th: OO OOOO.
7th: OO O OOOO.

Read More

The MISSING Servent

Problem

A king has 100 identical servants, each with a different rank between 1 and 100. At the end of each day, each servant comes into the king's quarters, one-by-one, in a random order, and announces his rank to let the king know that he is done working for the day. For example, servant 14 comes in and says "Servant 14, reporting in."
One day, the king's aide comes in and tells the king that one of the servants is missing, though he isn't sure which one.
Before the other servants begin reporting in for the night, the king asks for a piece of paper to write on to help him figure out which servant is missing. Unfortunately, all that's available is a very small piece that can only hold one number at a time. The king is free to erase what he writes and write something new as many times as he likes, but he can only have one number written down at a time.
The king's memory is bad and he won't be able to remember all the exact numbers as the servants report in, so he must use the paper to help him.
How can he use the paper such that once the final servant has reported in, he'll know exactly which servant is missing? 

Solution

  When the first servant comes in, the king should write down his number. For each servant that reports in, the king should add that servant's number to the current number total. Once the final servant has reported in, the number on the paper should equal

1 + 2 + 3 + ... + 99 + 100) - Missing Servant's Number.

If they had all shown up it would have been 5050, since 1 + 2 + 3 + ... + 99 + 100 = 5050.

So to get the number of the missing servant just subtract the number that is on the paper from 5050.

5050 - Amount On Paper = Missing Servant's Number.

Read More

TWO HOURGLASSES to measure 2 minutes

Problem

You have two sand hourglasses, one that measures exactly 4 minutes and one that measures exactly 7 minutes. You need to measure out exactly 2 minutes to boil an egg. Using only these two hourglasses, how can you measure out exactly 2 minutes to boil your egg? 

What if boiling eggs  take 9 minutes?

 

Solution

Boiling the eggs take 2 minutes

4 minutes : 7 minutes

#1:#2
4 : 7 Start both timers
0 : 3 After 4 min
4 : 3 Invert #1
1 : 0 After 3 min
1 : 7 Invert #2 and start cooking egg
0 : 6 After 1 min (egg half-cooked)
0 : 1 Invert #2 (7-6 = 1)
0 : 0 Stop cooking egg.

 

Total time from start: 7 min  

Boiling the egg taking 9 minutes

4 minutes : 7 minutes

#1:#2
4 : 7 Start both timers
0 : 3 After 4 min
4 : 3 Invert #1
1 : 0 After 3 min...#1 has 1 minute remaining
1 : 0  Leave #2 and start cooking egg
4 : 0 Invert #1. After 1 min (egg is 1 min-cooked)
0 : 0 Invert #1
4 : 0 Stop cooking egg.

 

1+4+4 = 9 minutes

 

Read More

TRUTH OR LIES

Problem

You're walking down a path and come to two doors. One of the doors leads to a life of prosperity and happiness, and the other door leads to a life of misery and sorrow. You don't know which door is which.
In front of the door is ONE man. You know that this man either always lies, or always tells the truth, but you don't know which. The man knows which door is which.
You are allowed to ask the man ONE yes-or-no question to figure out which door to go through. To make things more difficult, the man is very self-centered, so you are only allowed to ask him a question about what he thinks or knows; your question cannot involve what any other person or object (real or hypothetical) might say.
What question should you ask to ensure you go through the good door?

Solution

You should ask: "If I asked you if the good door is on the left, would you say yes?"

Notice that this is subtly different than asking "Is the good door on the left?", in that you are asking him IF he would say yes to that question, not what his answer to the question would be. Thus you are asking a question about a question, and if it ends up being the liar you are talking to, this will cause him to lie about a lie and thus tell the truth. The four possible cases are:

• The man is a truth-teller and the good door is on the left. He will say "yes".
• The man is a truth-teller and the good door is on the right. He will say "no".
• The man is a liar and the good door is on the left. He will say "yes" because if you asked him "Is the good door on the left?", he would lie and say "no", and so when you ask him if he would say "yes", he will lie and say "yes".
• The man is a liar and the good door is on the right. Similar to the previous example, he'll say "no".

So regardless of whether the man is a truth-teller or a liar, this question will get a "yes" if the door on the left is the good door, and a "no" if it's not.

Read More

Ants on a board

Problem

There are 100 ants on a board that is 1 meter long, each facing either left or right and walking at a pace of 1 meter per minute.

The board is so narrow that the ants cannot pass each other; when two ants walk into each other, they each instantly turn around and continue walking in the opposite direction. When an ant reaches the end of the board, it falls off the edge. From the moment the ants start walking, what is the longest amount of time that could pass before all the ants have fallen off the plank? You can assume that each ant has infinitely small length.

Solution

If you were looking at the board from the side and could only see the silhouettes of the board and the ants, then when two ants walked into each other and turned around, it would look to you as if the ants had walked right by each other.

In fact, the effect of two ants walking into each other and then turning around is essentially the same as two ants walking past one another: we just have two ants at that point walking in opposite directions.

So we can treat the board as if the ants are walking past each other. In this case, the longest any ant can be on the board is 1 minute (since the board is 1 meter long and the ants walk at 1 meter per minute). Thus, after 1 minute, all the ants will be off the board.

Answer

The longest amount of time that could pass would be 1 minute.

Read More

Engineers & Managers

Problem

You have just purchased a small company called Company X. Company X has N employees, and everyone is either an engineer or a manager. You know for sure that there are more engineers than managers at the company.
Everyone at Company X knows everyone else's position, and you are able to ask any employee about the position of any other employee. For example, you could approach employee A and ask "Is employee B an engineer or a manager?" You can only direct your question to one employee at a time, and can only ask about one other employee at a time. You're allowed to ask the same employee multiple questions if you want.
Your goal is to find at least one engineer to solve a huge problem that has just hit the company's factory. The problem is so urgent that you only have time to ask N-1 total questions.
The major problem with questioning the employees, however, is that while the engineers will always tell you the truth about other employees' roles, the managers may lie to you if they like. You can assume that the managers will do their best to confuse you.
How can you find at least one engineer by asking at most N-1 questions? 

Solution

You can find at least one engineer using the following process:

Put all of the employees in a conference room. If there happen to be an even number of employees, pick one at random and send him home for the day so that we start with an odd number of employees. Note that there will still be more engineers than managers after we send this employee home.

Then call them out one at a time in any order. You will be forming them into a line as follows:

• If there is nobody currently in the line, put the employee you just called out in the line.
• Otherwise, if there is anybody in the line, then we do the following. Let's call the employee currently at the front of the line Employee_Front, and call the employee who we just called out of the conference room Employee_Next.

So ask Employee_Front if Employee_Next is a manager or an engineer.

• If Employee_Front says "manager", then send both Employee_Front and Employee_Next home for the day.
• However, if Employee_Front says "engineer", then put Employee_Next at the front of the line.

Keep doing this until you've called everyone out of the conference room. Notice that at this point, you'll have asked N-1 or less questions (you asked at most one question each time you called an employee out except for the first employee, when you didn't ask a question, so that's at most N-1 questions).

When you're done calling everyone out of the conference room, the person at the front of the line is an engineer. So you've found your engineer!

But the real question: how does this work?

We can prove this works by showing a few things.

First, let's show that if there are any engineers in the line, then they must be in front of any managers.

We'll show this with a proof by contradiction. Assume that there is a manager in front of an engineer somewhere in the line. Then it must have been the case that at some point, that engineer was Employee_Front and that manager was Employee_Next. But then Employee_Front would have said "manager" (since he is an engineer and always tells the truth), and we would have sent them both home. This contradicts their being in the line at all, and thus we know that there can never be a manager in front of an engineer in the line.

So now we know that after the process is done, if there are any engineers in the line, then they will be at the front of the line. That means that all we have to prove now is that there will be at least one engineer in the line at the end of the process, and we'll know that there will be an engineer at the front.

So let's show that there will be at least one engineer in the line. To see why, consider what happens when we ask Employee_Front about Employee_Next, and Employee_Front says "manager". We know for sure that in this case, Employee_Front and Employee_Next are not both engineers, because if this were the case, then Employee_Front would have definitely says "engineer". Put another way, at least one of Employee_Front and Employee_Next is a manager. So by sending them both home, we know we are sending home at least one manager, and thus, we are keeping the balance in the remaining employees that there are more engineers than managers.

Thus, once the process is over, there will be more engineers than managers in the line (this is also sufficient to show that there will be at least one person in the line once the process is over). And so, there must be at least one engineer in the line.

Put altogether, we proved that at the end of the process, there will be at least one engineer in the line and that any engineers in the line must be in front of any managers, and so we know that the person at the front of the line will be an engineer.

Read More

Worm Crawls

A rubber string is 10 meters long. A worm crawls from one end to the other at 1 meter/hr. After each hour the string stretches to become 1 meter longer than it's last length.Will it reach the end ?

Solution

Yes, the worm will reach the end because at the end of every hour when rubber band stretches, the distance travelled by the worm in past hr(s) will also increase and remaining distance to travel becomes less as compared to earlier.

For exapmle:
at the end of 1st hour:
worm has tarvelled: 1meter

Now, when the whole length of rubber band becomes 11m then effective distance travelled by the worm in past 1hr becomes 1.1 merter.

if we calculate remaining distance to travel: 11 - 1.1 = 9.9 meters

Clearly it has reduced from 10 metres.

Read More

The Knight's Tour is a famous chess problem, in which a knight starts on the top-left square of an ordinary chessboard and then makes 63 moves, landing on every square of the chessboard exactly once (except for the starting square).
Can you complete the Knight's Tour? For a further challenge, can you find a "closed" solution, meaning that the knight can make a 64th move to land back on the starting square (thus making the solution circular)?

Solution

This pictures shows a non-cyclical solution. The strategy is to essentially cover the border (outer 3 rows/columns) first, and then cover the inner part of the board

Reference

• http://sudhansu-codezone.blogspot.in/2012/01/switch-doors-or-not.html

Read More

Given 9 Dots, draw 4 Lines without picking up pen

Problem

Look at the 9 dots in this image. Can you draw 4 straight lines, without picking up your pen, that go through all 9 dots?

Solution

Read More

Putting numbers in 3X3 matrix - s.t. Rows OR columns or diagonals add till 15

How can you place the numbers 1 through 9 in a 3x3 grid such that every row, column, and the two diagonals all add up to 15?

Solution

It first seems logical to put the 5 in the middle square becuase it is the median and mean of the numbers from 1 to 9 (and also the average of any 3 numbers adding up to 15).
The next thing to do is place the 1 since it's the smallest and will thus be likely to quickly constrain what we can do afterward. We can try to place the 1 in either a side square or a corner square, but once we place it, it forces us to place the 9 on the opposite side. At this point, we just play around with the remaining numbers to see if we can work out a solution.

Though this is all about magic square. Read more here.

Read More

Robots on a line

Two robots are placed at different points on a straight line of infinite length. When they are first placed down, they each spray out some oil to mark their starting points.

You must program each robot to ensure that the robots will eventually crash into each other. A program can consist of the following four instructions:

• Go left one space
• Go right one space
• Skip the next instruction if there is oil in my current spot
• Go to a label

[Note that a "label" is a name that refers to a line of your code. For example, you could label the third line of your program "surveying". Then, the instruction "goto surveying" would jump to line 3 and start executing from there on the next cycle.]
A robot will carry out one instruction per second. Both robots need not have the same program. Note that you won't know ahead of time which robot is on the left and which is on the right.

Solution

 The first thought most people have it to try to get each robot to go back and forth, centered on their original spot, each time going a little further out in each direction. This won't work.

Another insight is that since you don't know which robot will be on the left or right, it probably doesn't make sense to give them different programs.

The solution to this problem is to just have both robots move consistently in one direction, but not at full speed. Then, have either robot pick up to full speed when it sees oil again (which will only happen for one robot). This robot will eventually catch up to the other robot, causing a collision.
Here is a working program, which you will give to both robots. Note that our "move_slowly" section is able to move slowly by moving an extra right and left space.


[Label: move_slowly]
1 Move Right
2 Move Right
3 Move Left
4 Skip Next Instruction If On Oil
5 GOTO move_slowly

[Label: move_quickly]
6 Move Right
7 GOTO move_quickly 

References

• http://www.placementadda.com/placement-study/discussion/?id=278
• http://sudhansu-codezone.blogspot.in/2012/01/two-robots-are-placed-at-different.html

Read More

Brothers and sisters

Problem

You and a friend are standing in front of two houses. In each house lives a family with two children.
"The family on the left has a boy who loves history, but their other child prefers math," your friend tells you.
"The family on the right has a 7-year old boy, and they just had a new baby," he explains.
"Does either family have a girl?" you ask.
"I'm not sure," your friend says. "But pick the family that you think is more likely to have a girl. If they do have a girl, I'll give you $100."
Which family should you pick, or does it not matter?

Solution

They offer these charts for the houses:

Left house:
Younger Older
Girl Boy
Boy Girl
Boy Boy

Right house:
Younger Older
Girl Boy
Boy Boy

They also tell us:

"This is a very counter intuitive riddle. It seems like there should always be a 1/2 chance that a given child is a girl. And in fact there is. The key word there is "given". Because we are not asking about a "given" child for the house on the left. We are asking about what could be either child."

And I'll just stop it right there. In the riddle, you ask your friend "Does either family have a girl?", and the friend responds "pick the family that you think is more likely to have a girl."

This, to me, seems to be specifically asking the question "Is or is not the other child a girl?"

When the solution says "We are asking about what could be either child.", they seem to be suggesting that, at some point, they were asking the specific question "Is the other child a younger girl, a younger boy, an older girl, or an older boy?"

The riddle itself, however, was not asking this question; the riddle was asking if, yes or no, the other child was a boy or girl, and that the family had a child that was a girl, regardless of age.

If they were asking "what could be either child", they might as well have added in more factors, such as whether or not the other child could have been a long or short haired, green or brown eyed, taller or shorter, stronger or weaker, younger or older boy or girl.

There are a lot of things the other child could have been, but I don't think any of those other factors have anything to do with what the riddle asks, which is to "pick the family that you think is more likely to have a girl." And age doesn't have anything to do with whether the child is more likely to be a girl, correct?

The solution seems to me to be asking a question that the riddle itself was not.

And this doesn't seem to be an open-ended riddle either, that has a case of "we're both right"; the way this riddle is set up, and with the solution they give, they are saying that there is a single solution to this riddle of which house has a higher probability.

Please correct me if I'm wrong, and point out any flaws on my end. I honestly believe their solution is incorrect, or they changed around the original question to something that it actually wasn't. Something just doesn't seem right here. :/

Answer

We should pick the house on the left, as there is a 2/3 chance that the house on the left has a girl, and a 1/2 chance that the house on the right has a girl, as the age of the children on the left house are never given.

Read More

Using 5,5,5,5,5 can you make 37 along with any arithmetic operation.

Using 5,5,5,5,5 can you make 37 along with any arithmetic operation.

Read More

Make 3 3 7 7 equal to 24

Using only and all the numbers 3, 3, 7, 7, along with the arithmetic operations +,-,*, and /, can you come up with a calculation that gives the number 24? No decimal points allowed.

Read More

Cards in the Dark

Problem

You are standing in a pitch-dark room. A friend walks up and hands you a normal deck of 52 cards. He tells you that 13 of the 52 cards are face-up, the rest are face-down. These face-up cards are distributed randomly throughout the deck.
Your task is to split up the deck into two piles, using all the cards, such that each pile has the same number of face-up cards. The room is pitch-dark, so you can't see the deck as you do this.
How can you accomplish this seemingly impossible task?

Solution

There are 13 cards with face up, and rest 39 are face down. 
Take the first 13 cards off the top of the deck and flip them over. This is the first pile. The second pile is just the remaining 39 cards as they started.
This works because if there are N face-up cards in within the first 13 cards, then there will be (13 - N) face up cards in the remaining 39 cards. When you flip those first 13 cards, N of which are face-up, there will now be N cards face-down, and therefore (13 - N) cards face-up, which, as stated, is the same number of face-up cards in the second pile.

Read More

Islanders with dotted forheads

Problem

There is an island with 100 women. 50 of the women have red dots on their foreheads, and the other 50 women have blue dots on their foreheads.
If a woman ever learns the color of the dot on her forehead, she must permanently leave the island in the middle of that night.
One day, an oracle appears and says "at least one woman has a blue dot on her forehead." The woman all know that the oracle speaks the truth.
All the woman are perfect logicians (and know that the others are perfect logicians too). What happens next?

Solution

Base case. Imagine the same situation, except with 1 blue dot and 99 red dots. The woman with the blue dot will see 99 red dots, and will realize the one blue dot must be her own. She will leave on the first night.
The next day, the other 99 women will see that the one woman they all knew had a blue dot is gone. This indicates to them that their own dot cannot be blue (since the woman wouldn't have left on the first night if she'd seen any blue dots). So they all know their dots are red. All 99 of them will leave on the second night.
Now for the inductive step.
Inductive hypothesis: If there are exactly N blue dots, every woman with a blue dot will leave on night N.

Read More

Get the job puzzle

Problem

A company plan to recruit people. But, ends up finding many more than eligible people.So, they plan a strategy to cut short the people to their suit the headcount of their requirement.
People will be lined up in a queue 1, 2, 3… N.  At first phase, people at odd locations will be eliminated. Same thing will apply for next phase.
For example,
Round 1: 1, 2, 3, 4, 5, 6….N
Round 2:  2, 4, 6.. N  (People at odd locations eliminated)
Round 3: 4, 6… N (People at odd locations eliminated)

Given the value of N, where will you position yourself to take up the job ??

Solution

I would choose position is the last power of 2 within N for example, if N=17, the last power of 2 is 16 (2^4)
To be more specific,We have to chose the position of 2 raised to the power of x, where x is the no. of eliminations required to reduce n number of people to a final one.
x can be calculated by using a simple while loop.

x=0;
while(N>1)
{
    N=N/2;
    x=x+1;
}

Reference

• http://sudhansu-codezone.blogspot.in/2012/02/get-job-puzzle.html

Read More

ATM Money Withdrawal Limit

Problem

Assumptions:
a) I have infinite money in my account
b) The daily limit of amount of money that can be withdrawn from an ATM is finite
c) You can login into an ATM Machine only once a day
d) If you login into the machine and enter a large number to withdraw, you will not get anything. And hence, you will not be able to withdraw anything from the ATM for the day.
e) I do not know what the daily limit is.

What strategy should I choose so that I can withdraw N rupees in minimum number of days?

Solution

Of course, you can do it in N days (withdrawing only one rupee daily)
you could do it in N-limit + ceiling(N/limit)-1 days (check N, check N-1, .. check limit. Once you know the limit, and you have already withdrawn 'limit' rupees, you will take ceiling ((N-limit)/limit) days more.

Another approach can be first day we go and withdraw Re 1, and then Rs 2, 4, 8 and so on. The day will come when we will not be able to withdraw the money. Note that you can do it for (log limit +1) days. By that time you would have accumulated (2^M-1) rupees(using Geometric progression sum).
For the remaining rupees N-2^limit + 1, draw at the rate last accepted by the ATM. So, we will have log (limit ) +1 + (N - (2^M-1))/limit

Read More

Number the 8 boxes so that no consecutive numbers touch

There are 8 boxes. Place the numbers 1 through 8 in each square so that no consecutive number touches another (including diagonally). In other words, 1 cannot touch 2, 5 cannot touch 6, 5 cannot touch 4, etc, etc.

Read More

Minimum Sips

Problem

Given 1000 bottles of juice, one of them contains poison and tastes bitter. Spot the spoiled bottle in minimum sips.

Solution

We can do it in log(n) and that would be 10 sips. Of course it can be done in 1000 sips by checking each bottle but to do it in 10 sips you can take one drop from 500 bottles and mix them, if it is sour than the bottle is in those 500 or it is in different 500.Then out of those 500 you take 250 and do the same and rest is the binary search  .

Read More

Aeroplanes round the world

Problem

On Bagshot Island, there is an airport. The airport is the homebase of an unlimited number of identical airplanes. Each airplane has a fuel capacity to allow it to fly exactly 1/2 way around the world, along a great circle. The planes have the ability to refuel in flight without loss of speed or spillage of fuel. Though the fuel is unlimited, the island is the only source of fuel.
What is the fewest number of aircraft necessary to get one plane all the way around the world assuming that all of the aircraft must return safely to the airport? How did you get to your answer?
Notes:
(a) Each airplane must depart and return to the same airport, and that is the only airport they can land and refuel on ground.
(b) Each airplane must have enough fuel to return to airport.
(c) The time and fuel consumption of refueling can be ignored. (so we can also assume that one airplane can refuel more than one airplanes in air at the same time.)
(d) The amount of fuel airplanes carrying can be zero as long as the other airplane is refueling these airplanes. What is the fewest number of airplanes and number of tanks of fuel needed to accomplish this work? (we only need airplane to go around the world)

Solution

The fewest number of airplane is 3!

Imagine 3 airplane: A (black), B (red) and C (green). A is going to fly round the world. All three aircraft start at the same time in the same direction.

Check out the pics (where blue arrow shows fuel transfer):

After 1/6 of the earth's circumference, C passes 1/3 of its fuel to B and returns home, where it is refueled and starts immediately again to tail A and B.

So, at 1/6 circumference:
A = 2/3 fuel left
B = 2/3 (fuel left) + 1/3 (refueled by C) = Full tank
C = 2/3 (fuel left) - 1/3 (refueling B) = 1/3 fuel left
Then C backs to the airport with 1/3 fuel left.


Now A and B go to the 1/4 earth's circumference, meaning that they're gonna spend another 1/6 fuel in their tanks to reach that point. At this point, B transfer fuel to A until A's tank is full.

So, at 1/4 circumference:
A = 1/2 (fuel left) + 1/2 (refueled by B) = Full tank
B = 5/6 (fuel left) - 1/2 (refueling A) = 1/3 fuel left.
After that B returns to 1/6 circumference, which consumes B fuel until only 1/6 tank left and doesn't enough to bring it back to the airport.
Luckily, C already departed at the point with fuel of 2/3 tank and now awaits to refuel B.
B and C then return to the airport with 1/3 fuel each.


A (now with full tank) can go 1/2 world's length, meaning it will reach 3/4 earth's distance.

With the same scheme as above, B now goes to the opposite direction from the airport and awaits A at point 3/4 circumference with 5/6 tank of fuel. A who runs out of fuel is saved by B and received 1/2 tank of fuel.

So, at 3/4 circumference:
A = 0 (fuel left) + 1/2 (refueled by B) = 1/2 fuel left.
B = 5/6 (fuel left) - 1/2 (refueling A) = 1/3 fuel left.
A now has the enough fuel to go straight home to the airport.

B (with only 1/3 fuel left on the tank) then refueled by C at 5/6 circumference, and both plane now have enough fuel to go back to the airport.

References

• http://sudhansu-codezone.blogspot.in/2012/02/aeroplane-round-world.html

Read More

River, Soldiers & Boat and children

Problem

 Consider there are 10 soldiers on the one side of the river. They need to go to the over side of the rever. There is no bridge in the rever and no one can swin in the rever. One of the soldiers spots the boat with two boys inside. The boat is very small and the boys in the boats also very small. The boat can either hold two boys or one soldier. Now tell me how can all soldiers go to the other side of the river using this boat ?

Solution

First you have the two boys take the boat to one side of the river and leave a boy on that side of the river. One boy takes the boat back to the other side and stands on the shore. Then a soldier gets in the boat and rides it to the other side. When he arrives on the other side, then the boy gets in the boat and takes it back to the other side and picks up the other boy. They ride back to the other shore and drop off one of the boys and continue this process until all the soldiers are on the other side of the river.

Read More

Measure weights in balance

Problem

Puzzle 1:

The puzzle is if the shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1, 3 and 4 only. Now the question is how many minimum weights and names the weights you will need to measure all weights from 1 to 1000. This is a fairly simple problem and very easy to prove also. Answer for this puzzle is given below.

Solution :

This is simply the numbers 2^0,2^1,2^2 ... that is 1,2,4,8,16... So for making 1000 kg we need up to 1, 2, 4, 8, 16, 32, 64, 128, and 512. Comments your suggestions or other answers.

Puzzle 2:

This is same as the above puzzle with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000. For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg. Answer for this puzzle is given below.

Solution:

For this answer is 3^0, 3^1, 3^2... That is 1,3,9,27,81,243 and 729.

Read More

Last ball of Red Balls & Blue Balls

Problem

A bag has 20 blue and 14 red balls.Each time you randomly take two balls out of the bag.(Assume each ball has equal probability of being taken).You do not put the two balls back.Instead,if both balls are of same color,you add a blue ball to the bag;if they have different color,red ball is put in the bag.Assume that you have infinite supply of red and blue balls,if you keep on repeating this process ,what will be color of last ball left in the bag.Will the case remains same if we have 13 red balls????

Hint:
Analyze the number of balls remaining after each withdraw

Solution:
Since we are adding only 1 ball after withdrawing 2 balls, eventually all balls would be withdrawn.

If you start with r red balls and b blue balls here is what can happen:

1) Both red: Now you have r-2 red and b+1 blue balls
2) Both blue: Now you have r red and b-1 blue balls
3) 1 red and 1 blue: Now you have r red and b-1 blue balls.

Notice that case 2) and case 3) produce same final result and can be combined.

Also notice that parity of red balls don't change (i.e. if there are even number of red balls to start with, we will have even number at end vice-versa). This means if we have odd number of red balls to start with we will have 1 in end else 0.

Whenever two balls are withdrawn, the number of blue balls remaining change by 1 (either increases or decreases) whereas the number of red balls remaining change by 2. Since, the number of red balls initially is 14; there will always be even number of red balls remaining after each withdraws of balls. Hence, the last ball to be withdrawn would be blue.

Similarly, if the number of red balls initially is 13, there would be odd red balls remaining every time. Hence, the last ball to be withdrawn would be red.

Read More

Deck of cards - Pick the cards with same color

Problem

 A casino offers a card game using a normal deck of 52 cards.The rule is that you turn over two cards at a time.If both of them are red,they go to your pile ;if both are black they go to dealer's pile;and if one black and one red they are simply discarded.The process is repeated until you go through all the 52 cards.If you have more cards in your pile you will get $100,otherwise(including ties)you will get nothing.The casino allows you to negotiate price you want to pay for the game.How much you would be willing to pay for the game.

Solution

To come soon. I will always loose, no matter how many time this game is repeated

Read More

Honest Man and single Question

Problem

An honest man holds a card with one of the three possible numbers on it “1”, “2” or “3”. You can ask one question and the man allowed to answer only “Yes”,”No” and “I don’t know”. The honest man obviously never lies. Which question would you ask to say with 100% certainty which number is on the card the honest man holds?

Solution

         Question should be: "If I substract 2 from your number, and then take squery root, would the result be greater than zero?"

Man's number 3 -> Sqrt(3-2)=Sqrt(1)=1, (1>0)==TRUE, so the answer is "YES"
Man's number 2 -> Sqrt(2-2)=Sqrt(0)=0, (0>0)==FALSE, so the answer is "NO"
Man's number 1 -> Sqrt(1-2)=Sqrt(-1)=i, (i>0)==???, so the answer is "I DON't KNOW"

Read More

Elephant and Bananas

Problem

There are 2 cities A and B, 1000 Kms apart. We have 3000 bananas in city A and a elephant, which can carry max 1000 bananas at any given time. The elephant needs to eat a banana every 1 Km.

How many maximum number of bananas can be transferred to city B?
Note: The elephant cannot go without bananas.

Generalized Question:
There are 2 cities A and B, ‘D’ Km apart. We have ‘N’ bananas in city A and a elephant, which can carry max ‘C’ bananas at any given time. The elephant needs to eat ‘F’ banana every 1 Km.

Write a program that will compute ‘X’, the maximum amount of bananas that can be transported from city A to city B.

Solution

First, realize that if you take 1000 bananas and walk 1000 kilometers, you arrive with no banana at all. And the elephant is stuck in city B as there is no banana left for return journey. So the elephant needs to travel shorter distances or we can say that we need to subdivide distances.

How can we subdivide distances?

If we subdivide distances for each kilometer. Notice if elephant wants to shift all the bananas 1 km, you will loose 5 bananas every km. Lets see how.

• In 1st trip, elephant will pick 1000 bananas, eat one at 1 km mark, leave 998 bananas at 1 km mark and keep 1 with him for return journey.
• In 2nd trip, elephant will pick next 1000 bananas, eat one at 1 km mark, leave 998 bananas at 1 km mark and keep 1 with him for return journey.
• In 3rd trip, elephant will pick next 1000 bananas, eat one at 1 km mark, leave 999 bananas at 1 km mark. This time, he doesn’t need to keep anything for return journey.

So we transferred 2995 (998+998+999) to one km distance. This process (loosing 5 bananas per km) will continue until we reach a point where we have one less round trip. In this example, that transit point will come after 200 km, when we will have 2000 bananas left with remaining distance of 800 km.

    Also note that the rate of consumption remains constant no matter how we subdivide the distance, as long as the number of trips required is the same.

So in place of shifting bananas every km, we can transferred the bananas 200 kilometers at once.

• In 1st trip, elephant will pick 1000 bananas, eat 200 till 200 km mark, leave 600 bananas at 200 km mark and keep 200 with him for return journey.
• In 2nd trip, elephant will pick next 1000 bananas, eat 200 till 200 km mark, leave 600 bananas at 200 km mark and keep 200 with him for return journey.
• In 3rd trip, elephant will pick next 1000 bananas, eat 200 till 200 km mark and leave 800 bananas at 200 km mark. This time, he doesn’t need to keep anything for return journey.

In this way, we are now left with 2000 bananas and 800 kms to go.

Now if you calculate, we will consume 3 bananas per km till next transit point. And what will be the next transit point. It should be when we are left with just 1000 bananas. This means that it will come after 333.33 (1000/3) kms.

Finally, we have 1000 bananas and 466.67 kms left. Since elephant can carry 1000 bananas at once, it will pick all 1000 bananas and reach the end with 533.33 (1000 - 466.67) bananas left. (Assumed that elephant eats the banana evenly in fractions of 1km as well.)

Generalized Answer:

So we have seen that if we have (Cn + y) where n is an integer and 0<y<=C at any point in time, our cost of walking each km is (2n+1). And from next transit point this rate will become (2n-1). We need to choose transit points such that we reduce one round time every time. In this manner, transit point will come when remaining bananas are integer multiple of C. Now you have a subset of bananas and distance left. You can apply the same process on remaining values.

This recursion will converge, when remaining bananas are less then or equal to C. (So that we can transfer all of them in single trip.)
Java code:

double transferBananas(double N, double D, double C, double F) {  
 // base case: remaining bananas <= C,  
 // so carry all the bananas in one trip  
 // at this point if distance is more than N/F,  
 // elephant can never reach destination, return 0  
 if (N <= C) {  
  double bananasAtDestination = N - D*F;  
  return (bananasAtDestination >= 0.0) ? 
    bananasAtDestination :  0.0;    // out of bananas!  
 }  
   
 // # trips you would travel back and forth  
 int numTrips = 2*(ceil(N/C) - 1) + 1;  
   
 // how many bananas you consume per km  
 double costPerKm = numTrips * F;  
   
 // remaining number of bananas after consumption, we want it  
 // as an integer multiple of C.  
 double remainingBananas = C*(ceil(N/C) - 1.0);  
   
 // this is the distance you are able to travel before you  
 // reach ONE LESS round trip fetching bananas  
 // derived from eq: N - costPerKm * traveled = remaining bananas  
   
 double traveled = (N - remainingBananas) / costPerKm;  
   
 // we are able to travel greater (or equal) than the remaining  
 // distance, so fetch the bananas right to the destination  
 if (traveled >= D)  
  return N - D*costPerKm;  
   
 // calculate recursively as we travel ONE less round trip now.  
 return transferBananas(remainingBananas, D-traveled, C, F);  
}  

References

• http://tech-queries.blogspot.in/2011/04/elephant-and-banana.html

Read More

50 Trucks with Payload

Problem

  Given a fleet of 50 trucks, each with a full fuel tank and a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Assume all the payload will fit in one truck.

Solution

We want to use as little fuel as possible so we try minimize the number of trucks we use as we go along. Let’s say we start with all 50 trucks with full fuel (5000 miles range).

For each mile, we lose 50 miles in range. After two miles, we lose 100 miles leaving us with 4900 miles. This can be supported by 49 trucks so we drop one truck.
As you can see for every 100 miles we lose in range, we drop a truck.

50 trucks: 100/50
49 trucks: 100/49
…

Total distance = 100/50 + 100/49 + 100/48 + … + 100/2 + 100/1 (harmonic series) = 449.920533833

Read More

Why does mirror lies sometimes?

Problem

Imagine you are standing in front of a mirror, facing it. Raise your left hand. Raise your right hand. Look at your reflection. When you raise your left hand your reflection raises what appears to be his right hand. But when you tilt your head up, your reflection does too, and does not appear to tilt his/her head down. Why is it that the mirror appears to reverse left and right, but not up and down?

Solution

The definition of left and right depends on the observer and is reversed when facing the opposite direction. The definition of up and down does not depend on the orientation of the observer. 

Well, I don’t think, its because humans are left-right symmetric and not top-down!!!

Just stand in front of a concave mirror (or might be the convex - I don’t remember, which exactly. Been some time, since I’ve read this physics) beyond the focal length and try the same excercise - one would obviously find the top-down symmetry also coming into play.

I think, the reason is that flat-mirrors’ focal length is infinity and we always stand within its focal lenght and don’t see the image inverted.

Correct me, if I’m wrong!

Read More

Average salary of n people in the room

Question:
How can n people know the average of their salaries without disclosing their own salaries to each other?

Solution:

Let's say salaries of n people (P1, P2, P3.....Pn) are S1, S2, S3.....Sn respectively. To know the average of the salary i.e. (S1 + S2 + S3 + ..... + Sn) / n, they will follow the following steps -

1. P1 adds a random amount, say R1 to his own salary and gives that to P2 (P2 won't be able to know P1's salary as he has added a random amount known to him only). In this case, P2 will receive the figure (S1 + R1) from P1.
2. P2 does the same and gives the final amount to P3 (without showing that to anyone). Now P3 will get the figure (S1 + R1 + S2 + R2).
3. Rest of the persons (P3, P4, P5.....Pn) do the same. Pn will give the final amount to P1. Now P1 will have (S1 + R1 + S2 + R2 + S3 + R3 + ...... + Sn + Rn).
4. Now P1 subtracts his random amount (R1) and gives the final figure to P2 (without showing that to anyone). B will now receive the figure (S1 + R1 + S2 + R2 + S3 + R3 + .... Sn  + Rn) - R1 = (S1 + S2 + R2 + S3 + R3 + ...... + Sn + Rn).
5. P2 subtracts his random amount (R2) and gives the final figure to P3 (without showing it to anyone). P3 will receive the amount (S1 + S2 + S3 + R3 + ..... Sn + Rn).
6. In the same way every person remaining except (Pn) will subtract their random amount and give it to the next one. Now Pn will have (S1 + S2 + S3 + ..... Sn + Rn).
7. Now Pn subtracts his random amount (Sn) and then the figure becomes (S1 + S2 + S3 + .... + Sn). Pn will divide this amount by n and get the average i.e. (S1 + S2 + S3 + ..... + Sn) / n and show to every one in the room.

References

• http://algods-cracker.blogspot.in/2014/02/average-salary-of-n-people-in-room.html

Read More

Point inside a triangle or NOT

Problem

Given three corner points of a triangle, and one more point P. Write a function to check whether P lies within the triangle or not.

Example

For example, consider the following program, the function should return true for P(10, 15) and false for P’(30, 15)

              B(10,30)
                / \
               /   \
              /     \
             /   P   \      P'
            /         \
     A(0,0) ----------- C(20,0) 

Solution

Method 1 - Area of triangles made by point and other 2 vertices of triangle
Let the coordinates of three corners be (x1, y1), (x2, y2) and (x3, y3). And coordinates of the given point P be (x, y)

1. Calculate area of the given triangle, i.e., area of the triangle ABC in the above diagram. Area A = [ x1(y2 - y3) + x2(y3 - y1) + x3(y1-y2)]/2
2. Area A1 = Calculate area of the triangle PAB (using the same formula)
3. Area A2 = Calculate area of the triangle PBC
4. Area A3 = Calculate area of the triangle PAC
5. If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.

 Here is the code

float area(int x1, int y1, int x2, int y2, int x3, int y3)
{
   return Math.abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0);
}

boolean isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)
{   
   // Calculate area of triangle ABC 
   float A = area (x1, y1, x2, y2, x3, y3);
 
   // Calculate area of triangle PBC   
   float A1 = area (x, y, x2, y2, x3, y3);
 
   // Calculate area of triangle PAC   
   float A2 = area (x1, y1, x, y, x3, y3);
 
   // Calculate area of triangle PAB    
   float A3 = area (x1, y1, x2, y2, x, y);
   
   // Check if sum of A1, A2 and A3 is same as A 
   return (A == A1 + A2 + A3);
}

But can this differentiate whether the point lies on the edges, I don't thing so. It can only tell whether it is in triangle or not.

Method 2 - Using Barycentric coordinates
Solve the following equation system:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

The point p is inside the triangle if 0 <= s <= 1 and 0 <= t <= 1 and s + t <= 1.
s,t and 1 - s - t are called the barycentric coordinates of the point p.

Now, the barycentric coordinates, generally called alpha, beta, and gamma, are calculated as follows:

float alpha = ((p2.y - p3.y)*(p.x - p3.x) + (p3.x - p2.x)*(p.y - p3.y)) /
        ((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
float beta = ((p3.y - p1.y)*(p.x - p3.x) + (p1.x - p3.x)*(p.y - p3.y)) /
       ((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
float gamma = 1.0f - alpha - beta;

If all of alpha, beta, and gamma are greater than 0, then the point p lies within the triangle made of points p1, p2, and p3.
The explanation behind this is that a point inside a triangle can be described using the points of the triangle, and three coefficients (one for each point, in the range [0,1]):

p = (alpha)*p1 + (beta)*p2 + (gamma)*p3

Rearranging this function gives you the formula to compute barycentric coordinates, but I feel like the steps to do so might be beyond the scope of the question. They are provided on the Wikipedia page that I linked up top.

References

• http://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/
• http://stackoverflow.com/questions/13300904/determine-whether-point-lies-inside-triangle

Read More