A man needs to send important documents to his friend across the country. He buys a suitcase to put the documents in, but he has a problem: the mail system in his country is very corrupt, and he knows that if he doesn't lock the suitcase, it will be opened by the post office and his documents will be stolen before they reach his friend.
There are lock stores across the country that sell locks with keys. The only problem is that if he locks the suitcase, he has no way to send the key to his friend so that the friend will be able to open the lock: if he doesn't send the key, then the friend can't open the lock, and if he puts the key in the suitcase, then the friend won't be able to get to the key.
The suitcase is designed so that any number of locks can be put on it, but the man figures that putting more than one lock on the suitcase will only compound the problem.
After a few days, however, he figures out how to safely send the documents. He calls his friend who he's sending the documents to and explains the plan.
What is the man's plan?
The plan is this:
1. The man will put a lock on the suitcase, keep the key, and send the suitcase to his friend.
2. The friend will then put his own lock on the suitcase as well, keep the key to that lock, and send the suitcase back to the man.
3. The man will use his key to remove his lock from the suitcase, and send it back to the friend.
4. The friend will remove his own lock from the suitcase and get to the documents.
Search: Man-in-the-middle attack
A monk leaves at sunrise and walks on a path from the front door of his monastery to the top of a nearby mountain. He arrives at the mountain summit exactly at sundown. The next day, he rises again at sunrise and descends down to his monastery, following the same path that he took up the mountain.
Assuming sunrise and sunset occured at the same time on each of the two days, prove that the monk must have been at some spot on the path at the same exact time on both days.
Imagine that instead of the same monk walking down the mountain on the second day, that it was actually a different monk. Let's call the monk who walked up the mountain monk A, and the monk who walked down the mountain monk B. Now pretend that instead of walking down the mountain on the second day, monk B actually walked down the mountain on the first day (the same day monk A walks up the mountain).
Monk A and monk B will walk past each other at some point on their walks. This moment when they cross paths is the time of day at which the actual monk was at the same point on both days. Because in the new scenario monk A and monk B MUST cross paths, this moment must exist.
You are standing in a pitch-dark room. A friend walks up and hands you a normal deck of 52 cards. He tells you that 13 of the 52 cards are face-up, the rest are face-down. These face-up cards are distributed randomly throughout the deck.
Your task is to split up the deck into two piles, using all the cards, such that each pile has the same number of face-up cards. The room is pitch-dark, so you can't see the deck as you do this.
How can you accomplish this seemingly impossible task?
Take the first 13 cards off the top of the deck and flip them over. This is the first pile. The second pile is just the remaining 39 cards as they started.
This works because if there are N face-up cards in within the first 13 cards, then there will be (13 - N) face up cards in the remaining 39 cards. When you flip those first 13 cards, N of which are face-up, there will now be N cards face-down, and therefore (13 - N) cards face-up, which, as stated, is the same number of face-up cards in the second pile.
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.
