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.
93.84 %
41 votes

Similar riddles

See also best riddles or new riddles.

logicmathshort

Number 45

Can you write number 45 using only the number 4?
44+44/44
91.77 %
30 votes

logic

King's riddle

Allan, Bertrand, and Cecil were caught stealing so the king sent them to the dungeon. But the king decided to give them a chance. He mad them stand in a line and put hats on their heads. He told them that if they answer a riddle, they could go free. Here is the riddle: "Each of you has a hat on your head. You do not know the color of the hat on your own head. If one of you can guess the color of the hat on your head, I will let you free. But before you answer you must keep standing in this line. You cannot turn around. Here are my only hints: there are only black and white hats. At least one hat is black. At least one hat is white." Allan couldn't see any hats. Bertrand could see Allan's hat but not his own. Cecil could see Bertrand's hat and Allan's hat, but not his own. After a minute nobody had solved the riddle. But then a short while later, one of them solved the riddle. Who was is and how did he know?
Bertrand knew the answer because Cecil didn't say anything after one minute. If Bertrand and Allan's hats were both the same color, then Cecil would know what color his hat was. But Cecil didn't know. So Bertrand knew that Allan's hat was a different color than his. Since Allan's hat was black, Betrand knew his hat was white.
85.04 %
56 votes

cleanlogicshort

Longer line

You draw a line. Without touching it, how do you make the line longer?
You draw a shorter line next to it, and it becomes the longer line.
87.46 %
45 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.
78.06 %
49 votes

cleanEinstein’slogic

Five houses

There is a row of five different color houses. Each house is occupied by a man of different nationality. Each man has a different pet, prefers a different drink, and smokes different brand of cigarettes. The Brit lives in the Red house. The Swede keeps dogs as pets. The Dane drinks tea. The Green house is next to the White house, on the left. The owner of the Green house drinks coffee. The person who smokes Pall Mall rears birds. The owner of the Yellow house smokes Dunhill. The man living in the centre house drinks milk. The Norwegian lives in the first house. The man who smokes Blends lives next to the one who keeps cats. The man who keeps horses lives next to the man who smokes Dunhill. The man who smokes Blue Master drinks beer. The German smokes Prince. The Norwegian lives next to the Blue house. The man who smokes Blends has a neighbour who drinks water. Who has fish at home?
German.
82.20 %
54 votes

logic

Three Childrens' Ages

A deliveryman comes to a house to drop off a package. He asks the woman who lives there how many children she has. "Three," she says. "And I bet you can't guess their ages." "Ok, give me a hint," the deliveryman says. "Well, if you multiply their ages together, you get 36," she says. "And if you add their ages together, the sum is equal to our house number." The deliveryman looks at the house number nailed to the front of her house. "I need another hint," he says. The woman thinks for a moment. "My youngest son will have a lot to learn from his older brothers," she says. The deliveryman's eyes light up and he tells her the ages of her three children. What are their ages?
Their ages are 1, 6, and 6. We can figure this out as follows: Given that their ages multiply out to 36, the possible ages for the children are: 1, 1, 36 (sum = 38) 1, 2, 18 (sum = 21) 1, 3, 12 (sum = 16) 1, 4, 9 (sum = 14) 1, 6, 6 (sum = 13) 2, 2, 9 (sum = 13) 2, 3, 6 (sum = 11) 3, 3, 4 (sum = 10) When the woman tells the deliveryman that the children's ages add up to her street number, he still doesn't know their ages. The only way this could happen is that there is more than one possible way for the children's ages to add up to the number on the house (or else he would have known their ages when he looked at the house number). Looking back at the possible values for the children's ages, you can see that there is only one situation in which there are multiple possible values for the children's ages that add up to the same sum, and that is if their ages are either 1, 6, and 6 (sums up to 13), or 2, 2, and 9 (also sums up to 13). So these are now the only possible values for their ages. When the woman then tells him that her youngest son has two older brothers (who we can tell are clearly a number of years older), the only possible situation is that their ages are 1, 6, and 6.
91.04 %
47 votes

logic

The Monty Hall Problem

On the game show et´s Make a Deal, Monty Hall shows you three doors. Behind one of the doors is a new car, the other two hide goats. You choose one door, perhaps #1. Now Monty shows you what´s behind door #2 and it´s a goat.He gives you the chance to stay with original pick or select door #3. What do you do?
You should always abandon your original choice in favor of the remaining door (#3). When you make your first choice the chance of winning is 1 in 3 or 33%. When you switch doors, you turn a 2 in 3 chance of losing in the first round into a 2 in 3 chance of winning in the second round.
94.11 %
43 votes

logic

The manager

Mad Ade's Uncle, Phil Space, who doesn't like what passes for art these days, ran into the National Gallery and caused millions of pounds of damage to several masterpieces. Later that day, Uncle Phil was invited to meet the manager and was warmly thanked for his actions. How come?
Uncle Phil is a fireman The water from his house damaged the paintings as he put out a fire in the Gallery, but in the process rescuing hundreds of millions of pounds worth.
93.84 %
41 votes

logic

Paying With Rings

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?
The man cuts the ring that is third away from the end of the chain. This leaves him with 3 smaller chains of length 1, 2, and 4. Then, he gives rings to the proprietor as follows: After night 1, give the proprietor the single ring After night 2, take the single ring back and give the proprietor the 2-ring chain After night 3, give the proprietor the single ring, totalling 3 rings with the proprietor After night 4, take back the single ring and the 2-ring chain, and give the proprietor the 4-ring chain After night 5, give the proprietor the single ring, totalling 5 rings with the proprietor After night 6, take back the single ring and give the proprietor the 2-ring chain, totalling 6 rings with the proprietor After night 7, give the proprietor the single ring, totalling 7 rings with the proprietor
93.98 %
42 votes