Riddle #782

logic

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.
90.47 %
44 votes

Similar riddles

See also best riddles or new riddles.

cleanlogicshort

It directs us when to come and go

It regulates our daily movements, but it feels no interest in our lives. It directs us when to come and go, but does not care if we pay attention. What is it?
A clock.
83.67 %
51 votes

logic

The mean King

A king decided to let a prisoner try to escape the prison with his life. The king placed 2 marbles in a jar that was glued to a table. One of the marbles was supposed to be black, and one was supposed to be blue. If the prisoner could pick the blue marble, he would escape the prison with his life. If he picked the black marble, he would be executed. However, the king was very mean, and he wickedly placed 2 black marbles in the jars and no blue marbles. The prisoner witnessed the king only putting 2 black marbles in the jars. If the jar was not see-through and the jar was glued to the table and that the prisoner was mute so he could not say anything, how did he escape with his life?
The prisoner grabbed one of the marbles from the jar and concealed it in his hand. He then swallowed it, and picked up the other marble and showed everyone. The marble was black, and since the other marble was swallowed, it was assumed to be the blue one. So the mean king had to set him free.
89.33 %
39 votes

logic

Three friends

At a local bar, three friends, Mr. Green, Mr. Red and Mr. Blue, were having a drink. One man was wearing a red suit; one a green suit; and the other a blue suit. "Have you noticed," said the man in the blue suit, "that although our suits have colors corresponding to our names, not one of us is wearing a suit that matches our own names?" Mr. Red looked at the other two and said, "You're absolutely correct." What color suit is each man wearing?
Since none of the men are wearing the color of suit that corresponds to their names, and Mr. Red was replying to the man in the blue suit, it had to be Mr. Green to whom he replied. We then know that Mr. Green is wearing a blue suit. Therefore, Mr. Red is wearing a green suit and Mr. Blue is wearing a red suit.
88.20 %
48 votes

logicscaryshort

No electricity in the house

It was very dark. There was no electricity in the house. They had no candles or lanterns. The house was completely dark. A girl was reading and preparing for her exams. How?
Simple! The girl was blind and she was reading through Braille method.
74.17 %
65 votes

logicmathmystery

Tricky but simple Math Equation

100 people are standing in a circle. The person standing at number 1 is having a sword. He kills the person next to him with the sword and then gives the sword to the third person. This process is carried out till there is just one person left.
Till the number is the power of 2, the last person to survive will be the one who started it. But since the number here is not the power of 2, we will take the greatest power of 2 that is less than the number which is 64. 100 - 64 = 36 36 people are killed as 2, 4, 6, ..., 72. Thus the sword will now be given to the 73rd person. Now he is the first person to start in the remaining 64 people. Thus he will be the one to survive.
39.95 %
139 votes

cleanlogicshort

Beggar's brother

A beggar's brother died, but the man who died had not brother. How could this be?
The beggar was a women.
84.48 %
45 votes

cleanlogicshort

Reading in the dark

A girl is sitting in a house at night that has no lights on at all. There is no lamp, no candle, nothing. Yet she is reading. How?
The woman is blind and is reading braille.
85.10 %
47 votes