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?
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.
Two men ride their horses to the town blacksmith to ask for his daughter's hand in marriage. To help decide who will get to marry her, the blacksmith proposes a very strange race:
"You will race your horses down the mile-long road from here to the center of town, and the man whose horse passes through city hall's gates LAST will get to marry my daughter."
The men have no idea how to proceed, but after a few minutes of thinking, they come up with a great idea to abide by the blacksmith's rules. 30 minutes later, one of the men is gloating, having won the daughter's hand in marriage.
What was the idea the men had?
Each man rides the other man's horse. They race as they normally would. The blacksmith said the man whose horse crosses last would win, so the man who wins the race would have his horse finish last.
You are blindfolded and 10 coins are place in front of you on table. You are allowed to touch the coins, but can't tell which way up they are by feel. You are told that there are 5 coins head up, and 5 coins tails up but not which ones are which.
How do you make two piles of coins each with the same number of heads up?
You can flip the coins any number of times.
Make 2 piles with equal number of coins. Now, flip all the coins in one of the pile.
How this will work? lets take an example.
So initially there are 5 heads, so suppose you divide it in 2 piles.
Case:
P1 : H H T T T
P2 : H H H T T
Now when P1 will be flipped
P1 : T T H H H
P1(Heads) = P2(Heads)
Another case:
P1 : H T T T T
P2 : H H H H T
Now when P1 will be flipped
P1 : H H H H T
P1(Heads) = P2(Heads)
Two fathers and two sons went fishing one day. They were there the whole day and only caught 3 fish. One father said, that is enough for all of us, we will have one each. How can this be possible?
There was the father, his son, and his son's son. This equals 2 fathers and 2 sons for a total of 3!
It was a Pink Island. There were 201 individuals (perfect logicians) lived in the island. Among them 100 people were blue eyed people, 100 were green eyed people and the leader was a black eyed one.
Except the leader, nobody knew how many individuals lived in the island. Neither have they known about the color of the eyes. The leader was a very strict person. Those people can never communicate with others. They even cannot make gestures to communicate. They can only talk and communicate with the leader. It was a prison for those 200 individuals.
However, the leader provided an opportunity to leave the island forever but on one condition. Every morning he questions the individuals about the color of the eyes! If any of the individuals say the right color, he would be released. Since they were unaware about the color of the eyes, all 200 individuals remained silent. When they say wrong color, they were eaten alive to death. Afraid of punishment, they remained silent.
One day, the leader announced that "at least 1 of you has green eyes! If you say you are the one, come and say, I will let you go if you are correct! But only one of you can come and tell me!"
How many green eyed individuals leave the island and in how many days?
All 100 green eyed individuals will leave on the 100th night.
Consider, there is only one green eyed individual lived in the island. He will look at all the remaining individuals who have blue eyes. So, he can get assured that he has green eyes!
Now consider 2 people with green eyes. Only reason the other green-eyed person wouldn't leave on the first night is because he sees another person with green eyes. Seeing no one else with green eyes, each of these two people realize it must be them. So both leaves on second night.
This is the same for any number. Five people with green eyes would leave on the fifth night and 100 on the 100th, all at once.
Search: Monty Hall problem
Why it's important for the solution that the leader said the new information "at least 1 of you has green eyes", when they must knew from the beginning, that there are no less than 99 green-eyed people on the island? Because they cannot depart the island without being certain, they cannot begin the process of leaving until the guru speaks, and common knowledge is attained.
Search: Common knowledge (logic)
This teaser is based on a weird but true story from a few years ago. A complaint was received by the president of a major car company: "This is the fourth time I have written you, and I don't blame you for not answering me because I must sound crazy, but it is a fact that we have a tradition in our family of having ice cream for dessert after dinner each night. Every night after we've eaten, the family votes on which flavor of ice cream we should have and I drive down to the store to get it. I recently purchased a new Pantsmobile from your company and since then my trips to the store have created a problem. You see, every time I buy vanilla ice cream my car won't start. If I get any other kind of ice cream the car starts just fine. I want you to know I'm serious about this question, no matter how silly it sounds: 'What is there about a Pantsmobile that makes it not start when I get vanilla ice cream, and easy to start whenever I get any other kind?'"
The Pantsmobile company President was understandably skeptical about the letter, but he sent an engineer to check it out anyway. He had arranged to meet the man just after dinner time, so the two hopped into the car and drove to the grocery store. The man bought vanilla ice cream that night and, sure enough, after they came back to the car it wouldn't start for several minutes. The engineer returned for three more nights. The first night, the man got chocolate. The car started right away. The second night, he got strawberry and again the car started right up. The third night he bought vanilla and the car failed to start. There was a logical reason why the man's car wouldn't start when he bought vanilla ice cream. What was it?
The man lived in an extremely hot city, and this took place during the summer. Also, the layout of the grocery store was such that it took the man less time to buy vanilla ice cream.
Vanilla ice cream was the most popular flavor and was on display in a little case near the express check out, while the other flavors were in the back of the store and took more time to select and check out. This mattered because the man's car was experiencing vapor lock, which is excess heat boiling the fuel in the fuel line and the resulting air bubbles blocking the flow of fuel until the car has enough time to cool.. When the car was running there was enough pressure to move the bubbles along, but not when the car was trying to start.
Two sentries were on duty outside a barracks.
One faced up the road to watch for anyone approaching from the North.
The other looked down the road to see if anyone was approached from the South.
Suddenly one of them said to the other, "Why are you smiling?"
How did he know that his companion was smiling?
Although the guards were looking in opposite directions, they were not back to back. They were facing each other.
In a one storey brown house, there was a brown person with a brown computer, brown telephone, and brown chair. He also had a brown cat and a brown fish – Just about everything was brown – What colour was the stairs?
As it was a one-storey house – there were no stairs.
You are standing before two doors. One of the path leads to heaven and the other one leads to hell. There are two guardians, one by each door. You know one of them always tells the truth and the other always lies, but you don’t know who is the honest one and who is the liar. You can only ask one question to one of them in order to find the way to heaven. What is the question?
The question you should ask is "If I ask the other guard about which side leads to heaven, what would he answer?"
It should be fairly easy to see that irrespective of whom do you ask this question, you will always get an answer which leads to hell. So you can chose the other path to continue your journey to heaven.
This idea was famously used in the 1986 film Labyrinth.
Here is the explanation if it is yet not clear.
Let us assume that the left door leads to heaven.
If you ask the guard which speaks truth about which path leads to heaven, as he speaks always the truth, he would say "left". Now that the liar , when he is asked what "the other guard (truth teller) " would answer, he would definitely say "right".
Similarly, if you ask the liar about which path leads to heaven, he would say "right". As the truth teller speaks nothing but the truth, he would say "right" when he is asked what "the other guard( liar ) " would answer. So in any case, you would end up having the path to hell as an answer. So you can chose the other path as a way to heaven.
In the land of Brainopia, there are three races of people: Mikkos, who tell the truth all the time, Kikkos, who always tell lies, and Zikkos, who tell alternate false and true statements, in which the order is not known (i.e. true, false, true or false, true, false). When interviewing three Brainopians, a foreigner received the following statements:
Person 1:
I am a Mikko.
Person 2:
I am a Kikko.
Person 3:
a. They are both lying.
b. I am a Zikko.
Can you help the very confused foreigner determine who is who, assuming each person represents a different race?
Person 1 is a Miko.
Person 2 is a Ziko.
Person 3 is a Kikko.
