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.
See also best riddles or new riddles.logicshort
What is the next number in the sequence?
The next number it: 13112221. Each number describes the previous number. Starting with 1, the second line describes it 11 (one 1). Then the third line describes 11 as 21 (two 1’s). Then the fourth line describes 21 as 1211 (one 2, one 1). This is the pattern.
Without looking at a calendar, within a minute name a boys name using 5 consecutive first letters of 5 consecutive months.
JASON - July August September October November.logic
You're standing in front of a room with one lightbulb inside of it. You cannot see if it is on or off. Outside the room, there are 3 switches in the off positions. You may turn the switches any way you want to. You stop turning the switches, enter the room and know which switch controls the lightbulb. How?
You turn 2 switches "on" and leave 1 switch "off" and wait about a minute. Then enter the room, but just before you enter, turn one switch from "on" to "off". Once in the room, feel the lightbulb - if it is warm, but off, it has to be the last switch you turned off. If it is on, it has to be the switch left on. If it is cold and is off, it has to be the switch you left in the off position.logicmath
Three people check into a hotel room. The bill is $30 so they each pay $10. After they go to the room, the hotel's cashier realizes that the bill should have only been $25. So he gives $5 to the bellhop and tells him to return the money to the guests. The bellhop notices that $5 can't be split evenly between the three guests, so he keeps $2 for himself and then gives the other $3 to the guests.
Now the guests, with their dollars back, have each paid $9 for a total of $27. And the bellhop has pocketed $2. So there is $27 + $2 = $29 accounted for. But the guests originally paid $30. What happened to the other dollar?
This riddle is just an example of misdirection. It is actually nonsensical to add $27 + $2, because the $27 that has been paid includes the $2 the bellhop made.
The correct math is to say that the guests paid $27, and the bellhop took $2, which, if given back to the guests, would bring them to their correct payment of $27 - $2 = $25.cleanfunnylogic
You leave home, make three left turns, and return home where you find two men wearing masks. Who are they?
A catcher and an umpire. logicmysteryscary
A man is found hanging in a room 30 feet off the ground. There is nothing else in the room except for a large puddle of water on the ground. The police can't see any way the man could have climbed the walls to get to where he is hanging.
How did this man hang himself?
He stood on a tall block of ice and put the noose around his neck. Once the ice melted, he was hung, and all that was left was a puddle of water on the ground.logicmath
A man who lives in Middletown has two girlfriends, one in Northtown and one in Southtown. Trains from the Middletown train station leave for Northtown once every hour. Separate trains from the station also leave for Southtown once every hour. No trains go to both Northtown and Southtown.
Each day he gets to the Middletown train station at a completely random time and gets onto the first train that is going to either Northtown or Southtown, whichever comes first.
After a few months, he realizes that he spends 80% of his days with his girlfriend from Northtown, and only 20% of his days with his girlfriend from Southtown.
How could this be?
The train to Northtown leaves every hour, on the hour (9:00AM, 10:00AM, etc...).
The train to Southtown leaves at 12 after the hour (9:12AM, 10:12AM, etc...).
So there is only a 12/60 (1/5) chance that he will end up on the train to Southtown each day, since he will usually get to the station during the 48 minutes of each hour when the train to Northtown will be the next to come.logic
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 proprietorcleanlogic
You are in a cabin and it is pitch black. You have one match on you. Which do you light first, the newspaper, the lamp, the candle, or the fire?
You light the match first!logicmathshort
I know a number which is spelled in an alphabetical order. Do you?