Riddle #782


Engineers and Managers

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.
93.70 %
40 votes

Similar riddles

See also best riddles or new riddles.



What can go up a chimney down but not down a chimney up?
An umbrella.
93.05 %
36 votes


Mt. Everest

Before Mt. Everest was discovered, what was the highest mountain in the world?
Mt. Everest; it just wasn’t discovered yet.
92.86 %
35 votes


Young girl was found murdered

On the first day of the school a young girl was found murdered. Police suspect four male teachers and question them. They were asked what they were doing at 8:00 am. Mr. Walter: I was driving to school and I was late. Mr. Thomas: I was checking English exam papers. Mr. Benjamin: I was reading the newspaper. Mr. Calvin: I was with my wife in my office. The police arrested the killer. How did the police find the murderer?
Mr.Thomas as he cannot be checking exam papers on the first day of school.
92.46 %
33 votes


Burning fire

Alexander is stranded on an island covered in forest. One day, when the wind is blowing from the west, lightning strikes the west end of the island and sets fire to the forest. The fire is very violent, burning everything in its path, and without intervention the fire will burn the whole island, killing the man in the process. There are cliffs around the island, so he cannot jump off. How can the Alexander survive the fire? (There are no buckets or any other means to put out the fire)
Alexander picks up a piece of wood and lights it from the fire on the west end of the island. He then quickly carries it near the east end of he island and starts a new fire. The wind will cause that fire to burn out the eastern end and he can then shelter in the burnt area. Alexander survives the fire, but dies of starvation, with all the food in the forest burnt.
90.86 %
46 votes


Sock drawer

You have a sock drawer. It has 4 black socks, 8 brown socks, 2 white socks and 8 tan socks. You need to pull out a matching pair of socks in the dark. There is no light and you couldn’t see the socks. How many socks you should pull out in the dark to get one matching pair of socks? .
Five. You have only four different colors of socks. If you pick 5, you can surely get one pair of matching socks.
93.39 %
38 votes


Burning Rope Problem

A man has two ropes of varying thickness (Those two ropes are not identical, they aren’t the same density nor the same length nor the same width). Each rope burns in 60 minutes. He actually wants to measure 45 mins. How can he measure 45 mins using only these two ropes. He can’t cut the one rope in half because the ropes are non-homogeneous and he can’t be sure how long it will burn.
He will burn one of the rope at both the ends and the second rope at one end. After half an hour, the first one burns completely and at this point of time, he will burn the other end of the second rope so now it will take 15 mins more to completely burn. so total time is 30+15 i.e. 45mins.
93.70 %
40 votes

cleanlogicshortwhat am I

I cannot be seen

I repeat only the last word you say. The more I repeat, the softer I got. I cannot be seen but can be heard. What am I?
An Echo.
92.46 %
33 votes


Half of two plus two

Is half of two plus two equal to two or three?
Three. It seems that it could almost be either, but if you follow the mathematical orders of operation, division is performed before addition. So... half of two is one. Then add two, and the answer is three.
93.98 %
42 votes