Many people hate 'Mount Fuji' style interview questions. Questions such as:
"How many barbers are there in your home town?"
or
That last one being the most well known of these types of questions and the one from which the rest get their name. These questions were initially popularized by Microsoft, but many of the most well-known tech companies have used them since. They have recently fallen a bit out of favour, but you're still likely to come across some if you do few tech interviews here and there.
There is a good reason why many people don't like these types of questions. Most of the time, they don't really have a good answer. The question is designed to put a person under pressure (when they can't immediately see a way to tackle the problem) and see how they handle it, as well as see if they can come up with a creative solution on the spot. Some developers tend to enjoy that kind of challenge, others seem to loath it which is why opinions about these questions are highly polarised. While I personally don't think these questions are the be-all-end-all, I do believe they have their value, but that is not what I want to talk about.
You see the people who hate these questions, hate them with a passion. Whenever an interview contains a 'Mount Fuji' or two and people do badly, they know exactly where to cast the blame. "It was all because of the stupid Mount Fuji questions. I was never good at those, plus I wouldn't want to work for a company that would ask them anyway." That's the excuse you give to yourself. Makes you feel better about failing – which is actually not a bad rationalisation as far as rationalisations go. But, there is an issue with this thinking because sometimes, a question that sounds like a 'Mount Fuji' question isn't really one at all and with all the hate we direct towards them we might end up missing it completely. So, what excuse do we give ourselves then, hmmm :)?
What I want to do is present a couple of these 'Non-Mount Fuji' questions here. While they might seem like one of 'those' at first, they are actually very reasonable questions, relevant, with concrete solutions. In my opinion, very decent interview fodder as well, but you're likely to fail them just as badly as any 'Mount Fuji' problem if you haven't practiced, so let's have a look.
Here is the first:
There is a village full of people. One day the priest gathers all the villagers together and declares that their God has told him that some among the villagers are sinners. All sinners will be marked with a sign on their forehead so that all other people will be able to see if a person is a sinner or not, but noone will know if there is a mark on their own forehead. Furthermore, the mark will not be visible in the mirror and one person is forbidden from telling another if they are a sinner. The villagers must work out which among them are sinners at which point all sinners are to leave the village. The village has been given one week and if at the end of the week, there are still sinners present, the whole village will be destroyed.
The villagers go about their own business during the day, however the whole village gathers in the square at the end of every day so that everyone can see if there are still any sinners left among them. After the third such gathering all the sinners pack up their stuff and leave the village.
How many sinners were there? How did you arrive at that number?
This is a deductive reasoning question. We tend to use this kind of reasoning all the time when writing software, so the question is highly relevant to the software development profession. This question has many different forms and is pretty common, so you may have heard it before. If you have you should be able to answer it easily right :)?
Here is the second:
You are one of several recently arrested prisoners. The warden, a deranged computer scientist, makes the following announcement:
You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.
I have setup a "switch room" which contains a light switch, which is either on or off. The switch is not connected to anything.
Every now and then, I will select one prisoner at random to enter the "switch room". This prisoner may throw the switch (from on to off, or vice-versa), or may leave the switch unchanged. Nobody else will ever enter this room.
Each prisoner will visit the "switch room" arbitrarily often. More precisely, for any N, eventually each of you will visit the "switch room" at least N times.
At any time, any of you may declare: "we have all visited the 'switch room' at least once". If the claim is correct, I will set you free. If the claim is incorrect, I will feed all of you to the crocodiles. Choose wisely!
- Devise a winning strategy when you know that the initial state of the switch is off.
- Devise a winning strategy when you do not know whether the initial state of the switch is on or off.
This is a distributed coordination problem. The reasoning used to solve this one is relevant when it comes to both distributed computing and concurrency. Infact, I 'stole' this question from Chapter 1 of the "The Art of Multiprocessor Programming", which is a great book I've been browsing recently (it really is a very interesting book and I will likely be going through it in a lot more detail, don't worry though, you'll read about it right here when that happens :)). In my opinion this is an even better question than the last, it feels more 'computery' for whatever reason. More than that, once you've worked it out, the solution can pretty easily be expressed in code to validate your reasoning (which is exactly what I did). Infact, with a little bit of creative thinking, even the first question can be validated through some code. If you can express something in code it's a winner as far as I am concerned.
So What Do We Do With These?
What I want you to do is use this as an opportunity to practice. It doesn't really even matter if you're likely to ever get this kind of question in an interview; these are good questions to give the old programming brain a bit of a workout. Not only is this an opportunity to problem-solve, but it can also be an opportunity to write some quick, interesting code. After going through this exercise, if you ever do see these kinds of questions in an interview, you'll hopefully be able to distinguish them from the 'hated Mount Fuji' ones :).
So, get your thinking caps on and try to solve these questions – then post your solutions in the comments below. The first person to get everything right gets a prize, actually I lie, there is no prize, but apparently incentives don't work anyway, so it doesn't matter. What you will get is a decent mental workout and the satisfaction of solving an interesting problem. Don't worry if you can't get it though, you'll get better with practice as long as you give it a go. Anyway, I won't leave you in the lurch, I'll post my solutions to both of those questions in a few days, including the code I wrote to validate the second one (I might even write some code for the first one if I get time). If you're really brave, then also post how long it took you to work out the answer (it doesn't really matter, getting these right at all would be a very decent effort, but if you want to show everyone how much of a genius you really are, this is your chance :)). I am really looking forward to seeing what you come up with.
Related posts:
- How To Answer A Programming Interview Question And Look Good Doing It
- An Interview Question That Prints Out Its Own Source Code (In Ruby)
- The Best Way To Interview A Developer
- To Code With Or Without Music That Is The Question
- A “FizzBuzz” Faux Pas
- The Secret To Getting More Ideas (And Better Ones Too)
- The Real Measure Of Code Quality
{ 3 trackbacks }
{ 55 comments… read them below or add one }
I think the second problem has a solution of the following form (not sure if this is the best way to handle it but still):
1. Everyone enters the room but leaves the switch in the ‘off’ position. They count the times they have entered the room, and when they reach N, they will put the switch to “ON”. If anyone find the switch on “ON”, they declare.
2. I suppose they could just count the times they enter the room, and when they hit N, they leave (so they have no use of the switch in this case, because everyone would have to hit N).
I suppose that the problem was actually saying that “for each N visits, each of you would have visited the room at least one time” , not “N times” because that would be impossible.
Or maybe I misunderstood.
About the first problem, I’m not sure I get the constraints, because it seems to me that people would be able to tell the sinners from the first night (for instance one person could check everybody and make a list of the sinners, or they could pair up and check each other…)
I think you misunderstood the problem a little bit the whole thing about N was basically to say that every prisoner will enter the room at some point and potentially more than once, it is probably easier to ignore the N all together, looking at it now, it probably confuses the problem a little bit.
For the first problem, you missed the constraint that noone can tell another person if that person is a sinner or not, so there is no way for anyone to find out if they are a sinner unless they are able to deduce it somehow.
Ah, well you have to make a few things clearer; it was not clear from the problem that one could not tell another if they were *not* a sinner, only that they could not tell if they *were* a sinner…
Also, for the result, do you expect a hard number? like 5 or 2 or a percentage? Or is that a trick question?
Ah, I obviously didn’t read further :) Don’t even bother answering my question, a couple of people have already provided the right solution!
PSPS
I guess the answer is: it doesn’t matter?
“Furthermore, the mark will not be visible in the mirror and one person is forbidden from telling another if they are a sinner. ”
Can a villager tell another villager they aren’t a sinner?
No they can not.
Ok, I just wrote a long comment answering the second question, and when I hit the “Submit” button, I got a big nice 404 error,
So to be short:
- I suppose the text of the problem meant “when the total number of visits hits N, everyone has visited at least once” , because the way it looks now “for N visits, everyone visited the room N times” means everyone visited the room together
- for the second question, part 1: each visitor visits the room and doesn’t touch the switch. they keep count of the number of visits to the room. the first one to make N visits turns the switch to ‘ON’. The following visitors can see that the switch is “ON” and make the claim to leave.
- part 2: each one counts to N visits and then leaves the room, regardless of the switch
for the first question, it’s not really clear to me what are the constraints, because they could just do it in the first night (for instance one person could check everybody, or they could check each other in pairs…)
Sorry about that 404, I really need to consider moving to some better hosting. It’s less about the money and more about finding the time to do all the leg work of actually finding a decent host and then installing all the relevant bits (LAMP stack etc), then moving the blog over, making sure everything still works. I am hoping if I moan long enough, some hosting company will come along and help me out by doing it all for me :). Anyways, sorry about that little bitch-session.
As I said in response to your first comment, it is probably better to ignore the whole N think all together it really does make it confusing. I should have taken it out and just said, that any prisoner can visit the room any number of times and in any order, but all prisoners are guaranteed to visit eventually.
My solution to the prisoner problem:
- Group elects a leader. Leader is responsible for making the “we have all visited the switch room” declaration.
- Leader will turn switch off if it is on. Each time he/she switches it off, he/she increments a count. When count is the same a the number of prisoners (assuming initial switch state is off) or greater than the number of prisoners (assuming initial switch state is on) then all prisoners will have visited the room.
- All other prisoners will turn the switch on if it is off. They will only do this once. All other times they visit the room they do not alter the state of the switch.
Haven’t figured out how to handle an unknown initial switch state yet.
Hey Stephen,
That’s correct, electing the leader is the thing to do, this would usually be the case in a problem involving multiple machines (distributed coordination). It is a lot easier when one machine is the master and the others are slaves (leader and followers), which is what makes this problem relevant in my opinion. The second part is solved along similar lines, some of the people in the comments below have the right idea.
I would hire the person who told me flat out,
“You’re not going to move Mt. Fuji. Its not going to happen”
Because at the end of the day being realistic about a problem and communicating realistic boundaries is as important as blowing sunshine upwards.
I’ve seen some spectacular failures and endless schedule delays from people not having the guts to state reality or management failing to listen to reality.
That would be a decent initial answer, but the interviewer would likely then ask you ignore whether it is possible or not and describe how you would do it if you had to. Think of it this way, if someone gives you a business requirement which you know is impossible, but you need to do your due diligence anyway if only to be able to point at all the things you did try and how unsuccessful they were. I’ve had to do this more than once in my work.
Thats a CYA strategy, not a bad idea, but leads to trouble. Better to stick to one’s guns if you really believe it, imho.
First and foremost: Thanks for posting these! My brain appreciates the workout. Now, on to my results:
I can’t solve the first problem. There’s something about it that I’m totally blind to, and after staring blankly at it for about 10 minutes with no progress, I’ve given up :)
The second problem, however, took me about 25 minutes to solve. Here is my solution:
For part 1, where the switch is known to start at off, the group chooses one “leader” during the initial meeting, and that leader makes a mental note of how many prisoners there are in total, including himself. To keep nomenclature simple, let’s call the other prisoners “followers”.
When a follower enters the switch room, he will do nothing if the switch is off. If the switch is on, the follower will switch it off the first time only; any subsequent visit where the switch is on, he’ll leave it on.
Whenever the leader walks into the switch room, he will do nothing if the switch is on. If the switch is off, he will flip it on, and keep track of how many times he has done this. Once he has flipped the switch on X times, where X is the total number of prisoners including himself, he can safely alert the warden that everyone has visited the room.
This works because it allows the leader to keep a count of how many unique visits there have been to the room, since each follower will only take action one time, and never before the leader has started the count by flipping the switch on for the first time.
For part 2, the plan is very similar except for two changes:
First, instead of only flipping the switch from on to off once, each of the followers flips the switch from on to off twice before never touching it again.
Second, instead of declaring victory after X flips, where X is the total number of prisoners, the leader waits until he has flipped the switch from off to on 2X-1 times.
This works because there can only be up to 1 on-to-off flips before the leader’s first visit. If there is a pre-leader flip, the leader will reach 2X-1 flips after all prisoners have flipped the switch exactly twice. In the case where there is not a pre-leader flip, the leader will reach 2X-1 flips when all the followers have flipped the switch exactly twice, except for one follower who has flipped the switch exactly once.
I’m curious to know if there are more efficient solutions than mine, and if there is a way to do it without a leader. Also, my plan will fall apart if any of the prisoners makes an error, maliciously interferes with the plan, or dies. Is there an alternate solution that has any tolerance for failure?
Hi Dan,
I am glad you found these interesting. The thing to do with the first one, is make some assumptions with the most specific case of the problem. If there is only one sinner, will they be able to work it out on their own. After you get that one, what would happen if there were 2 sinners. After that you can pretty much generalise and come up with a solution.
Your solution to problem 2 is correct, both parts. I came up with these exact solutions the first time around as well, I do believe there is a more efficient way of doing the second one, but I would like to validate it with some code before I say anything. It will likely be in my post which will solve both of these problems.
At the risk of looking extremely stupid:
If there was one sinner, he’d be able to figure it out on the first day.
So, if everyone comes back on the second day, there’s got to be more than one.
If you were a sinner, and could see one other on the second day, you’d know there was exactly two and would leave.
Extension of this reasoning leads me to conclude the answer is 3. Annoyingly, I guessed the answer, but spent several minutes convincing myself of it.
2)
Split the prisoners into two groups. Call all but one signallers, the other is the monitor.
Signaller Strategy: If I’ve never switched the light on, and it’s off, switch it on. Otherwise leave it alone.
Monitor Strategy: Always switch the light off. Keep count of how many times you’ve seen the light on. When that is the number of signallers, inform the warden.
Wasted five to ten minutes trying to come up with a symmetric solution, it was pretty obvious once I let go of that assumption.
Hey Julian,
Your reasoning is correct, this is exactly the way to do it. Your solution to the second one is also correct. I also wasted about 5 minutes trying to think of a solution where any of the prisoners can declare :).
This is highly relevant to me because i have an interview tomorrow.
Question 1) I think the answer is 3. If there were only 1 sinner, he would look around, see no one else marked, and realize he was the sinner on the first day. Generally, if it has been n days, all the sinners will simultaneously realize they are sinners. Because when day n+1 comes, if a villager sees only n sinners, he will then know he is also one. The same process will be occurring with all the other sinners simultaneously.
Question 2) Assuming a known off starting position, Prisoner A switches it to on, and Prisoner B declares the end when he sees the switch is on. Without that assumption, the best I can do is say that each prisoner should switch the switch each time they see it, and declare the end when they return to find it changed. This is vulnerable to a pathological case where each prisoner visits an even number of consecutive times though. Assuming the choice of prisoner is really random though, the probability this continuing approaches zero.
I think I’ve spent 13 minutes on these, counting the time to type them.
Hey Tom,
Your answer to the first one is correct, but the second one is not quite right, you can have a look at some of the other comments which get both parts of that question correct, or alternatively, I will post my solutions in a couple of days.
1. Everyone leaves…
The last sinner in the village either thinks all the sinners are gone, in which case everyone else leaves, and then so does he (if he realizes he’s a sinner). Or he thinks he’s a sinner, in which case he leaves.
2.1 One person is allowed to turn the light off, you are only allowed to turn the light on once if the light is off when you go there.
Whomever turns the light off counts the number of times it was on.
2.2 idk
Your answer to the first one is not quite right. Part 1 of the second one is correct though.
I think this is correct. Haven’t tested it:
All prisoners except one are ‘up-flippers’: if (switch_is_off && toggle_count (prisoner_count – 1)*2-1) declare_all_visited().
That’s basically it yeah.
For the unknown initial position prisoner problem: All prisoners except one are ‘up-flippers’: if (switch_is_off && toggle_count is less than 2) {toggle(on). ++toggle_count.}
One prisoner is a ‘down-flipper’: if(switch_is_on) {toggle(off). ++visitor_count.} if(visitor_count is greater than (prisoner_count – 1)*2-1) declare_all_visited().
Since the initial position of the switch can cause an off-by-one error, we ask each up-flipper to toggle twice. This assures that each prisoner has visited at least once.
You’re also right about this one :)
###########
Problem 1:
###########
-Answer: Three sinners.
-Time: The solution took me one minute, but I’ve seen variations of this
problem before.
-Reasoning: If there was one sinner, he would see that no other people are sinners, and leave immediately. If there are N sinners, each sees N-1 sinners at the first meeting. Each waits until the (N-1)th meeting, to see if they all leave. When they don’t, each sinner realizes that they themselves are the Nth sinner. So, after the Nth meeting, they and all the other N-1 sinners leave.
############
Problem two:
############
-Time: about 30 minutes
-Solutions:
Case 1: the switch starts in the off state.
————————————————–
Say there are N men. They designate one man to be the census taker. He initializes a count at 0.
Every time a man goes into the room:
-If he is NOT the census taker: if the switch is off, he turns it on. After his first visit, he never toggles the switch again.
-If he is the census taker: if the switch is off, he turns it on and adds 1 to his count. If his count is N, he goes to the warden and demands release.
This solution works because each time the census taker finds the switch off, he knows there has been a new visitor (starting with himself).
Case 2: the switch starting state is unknown.
——————————————————
Same rules as Case 1, but with two changes:
-Non-census-takers toggle from on->off twice, not once.
-The designated census taker demands freedom when his count reaches 2*N-2
To see why this works, consider the two possible starting states:
1. The switch starting state is “off”. See “Case 1″, above. Stopping at N is sufficient, so stopping at 2*N-2 is also sufficient.
2. The switch starting state is “on”. The first man to to toggle the switch to “off” will not be counted. Hence, only one of his toggles will be counted. Both toggles from each of the other N-2 non-census-takers will be counted. That is 2*(N-2) + 1 = 2*N – 3 toggles. Since the census taker also counts himself, that is 2*N – 2 toggles total. Once the count reaches this level, he knows that everyone has visited at least once; in fact, everyone except the first visitor has visited at least twice.
You’re quite right on all counts, and very good job on the analysis of the second case of problem 2 (i.e. spotting 2N-2).
Kemal, good catch on the second prisoner case being 2*N-2; I mistakenly assumed 2*N – 1, forgetting that the census-taker doesn’t need to count himself twice.
Also, for the first problem, I assumed it was possible that there were no sinners. Without that assumption the problem makes a lot more sense :)
Althought your solution would still work fine 2N-1, just not as efficient :). And you’re right, you definitely have to assume there is at least one sinner which is why their god must have started the whole problem in the first place :).
For problem 1, everyone is saying 3, and basing it on the sinner seeing 2 other sinners, and at the end of 3 days, leaving.
I don’t think this works.
If the last sinner leaves at the end of day 3, because “I don’t see any more sinners, I must be the last one”, what’s to prevent a non-sinner from thinking the same thing on day 4? What’s to prevent the last one to leave (on day 3) from thinking he’s a non-sinner, and “the sinners have left, we’re all safe, hooray!” ?
Hi Alex,
This does work, because each sinner doesn’t leave at the end of every day, all sinners leave together at the end of the third day since that’s how long they needed to deduce that each one of them was a sinner based on the continued presence of the others.
Answer one: everybody. Villagers aren’t very good logicians, so on the third night they crack under the pressure and split.
Maybe I’m just rationalising my failure to deduce the correct answer (*sigh*), but in my experience the real challenge of working in a technical field has little to do with the actual ability to reason. Given enough time and energy, any logical problem that can be solved will be solved. Said in another way, a given set of postulates–taken together with the rules of inference–contains all possible consequences of these postulates. A proof just articulates an inevitable consequence of the givens.
The truly difficult parts of working in a technical field are the human aspects of ambiguous situations and interpersonal relationships. A 30-page essay on why the content management system your boss chose to purchase is technically inferior will be ignored at best, and would probably antagonize your boss if it’s actually read. Technologically superior products are not guaranteed to achieve market penetration–I’m sure we’ve all used products that were better than the competition, but folded anyway. One recent example from my own experience is Lala.com
And the examples pile up: it’s rarely possible to spend the time necessary to thoroughly research all available options before making a decision on whether or not to adopt the hot new scripting language of the moment. Your marketing staff won’t care that their decade-old contact management system is impossible to update and requires specialty hardware–it works for them and they don’t want to retrain on a new system.
To me, these are the challenges. Especially because techies have to be thinking rationally and analytically about the project du jour while they’re engaged in the human aspect of business, such as selling the project to upper management.
Take with a grain of salt because I’m not in the interviewer’s chair, but personality and charisma count for a lot in my book.
Haha, I like your answer, regardless of its incorrectness :).
I agree with everything you say, personality and communication skills definitely count for a lot in software, but I do believe that ability to reason is important as well especially in some of the more complex areas of software development (i.e. not business webapp development ).
Kemal, dont you mean
“-If he is the census taker: if the switch is ON, he turns it OFF and adds 1 to his count. If his count is N, he goes to the warden and demands release.”
To question one:
‘one person is forbidden from telling another if they are a sinner’
As the villagers are gathered together, someone could simple state the rule that no-one talk to those with a mark on their head all day. If you haven’t been spoken to all day, then you must leave. This could possibly mean that all sinners have left by the second day, and that the number of sinners cannot be deteremined.
However, if the statement above were to say:
‘one person is forbidden from indicating to another if they are a sinner’
Then it would be a more difficult problem.
It’s the second one, so it is the more difficult problem :), although you can still reason it out as many of the people in the comments above have done.
I only had time to think about problem 1, so here are my thoughts:
The key here is that everyone knows that sinners will see N – 1 sinners and non-sinners will see N sinners. Villagers just need to figure out if they see the smaller number. When I approached this problem the first time, I came up with a quick solution to simply figure out how many sinners there were with any given random set of villagers and their random “sin status” using this information. I think this follows the rules in general – you have everyone count up the number of sinners they see and then share their totals. Those who have a total of N are non-sinners, while those with a total of N – 1 are sinners. There are only two possible values villagers will come up with when totaling the number of sinners they see, so you can figure out N and N – 1. I was pretty satisfied with this basic fact (though obvious), but it doesn’t solve the actual problem. We know that sinners packed up and left _after_ the third meeting. They did not just count things up like this at the first meeting, but instead waited it out like the villagers they are, unless I missed something about the rules. For example, what if there were 100 sinners? This would never work and the village would be destroyed. That didn’t happen, so they were lucky. I think they should have been destroyed for taking 3 meetings to figure this out though.
Everyone can simply assume they’ve been counted as a sinner. Perhaps they are not all clear on their God’s rules :-) Therefore, they can assume they see N – 1 sinners, but maybe they see N sinners and were good (and will get Christmas presents or something). What to do? We know if someone sees no other sinners, he is the sinner. N = 1, and he sees N – 1. Because there is at least one sinner, that’s the only conclusion he can make. He leaves _before_ the first meeting. It took 3 meetings to figure this out in the inefficient villager “we hope there are fewer than 8 or so sinners or we’re dead” way. The sinners didn’t figure this out until after the 3rd meeting. This means it takes 3 days to realize they are a sinner:
- If someone left before meeting 1, there was 1 sinner.
- If someone left before meeting 2, there were 2 sinners.
- If someone left before meeting 3, there were 3 sinners.
- The sinners realize they are hosed on the 3rd meeting. They leave on day 4 after the 3rd meeting, just to spend some extra time with their more well behaved friends. Why did they almost bring such wrath?
You can only figure out that you need to leave if meeting number M is N – 1. Of course, if N is 1, then you can leave before meeting (no meeting required).
M = N – 1
3 = N – 1
N = 4
I assume the first meeting is after they get the bad news which requires the formulation of an algorithm that’s almost surely bound to doom any village that I am familiar with. This seemed like a one by off problem to me anyway…
Hi Shaun,
Haha, that’s some awesome analysis :).
Why do they need three nights? If at the meeting, everyone counts how many sinners they see individually (if you can’t say it out loud, write it on a piece of ballot paper, and all numbers read out by the chief). Assuming you could remember your own number, you would immediately know if you are a sinner or not after the first night. If 10 villagers, 3 sinners, you would have 7 counts of 3, and 3 counts of 2. The 3 would leave. I can’t figure out why it would take them 3 nights?
The villagers are not allowed to share their observations with other villagers in any way, which includes writing it on a piece of paper or reading it out loud.
I may be thick, but I think the sinners problem does not have an iterative answer, but is simply a case of a solution existing if there is exactly one sinner, and no solution if there is more than one. The only case where a sinner gains information about their own state is when they see no other sinners.
I do not see how the progression of time adds information to the problem space. If you start out with X sinners, any given villager will see either X or X-1 sinners, but without knowing how many sinners there are, a villager has no way to know whether they are a sinner or not, and the passage of an extra day does not add to the information a villager has.
Please explain my error.
I don’t know about the elegance of these solutions but here goes my attempt:
a) (Start position off). Give only one person, A, the authority to turn the switch off. Everyone else turns the switch on the first chance they get and never again. A can keep count of how many times someone else turned it on.
b) (Start position unknown). One person, A, switches the switch every time he goes into the room. All the other people turn the switch on the first time they find it off AFTER seeing the switch in two different positions. Every time A comes back to find it on after leaving if off he knows that someone he hasn’t counted has been in the room.
Ok, now to go read the other comments. I came up with the first solution relatively quickly. I thought about the second actively for a while (can’t really say how long to be honest: maybe 10 minutes maybe 20 minutes) then I went to watch some tennis (Nadal vs Almagro). Two sets in that idea occurred to me.
@TomP,
Does this work as a fuller answer to the sinners problem?
1) Suppose there is one sinner. On the first day, he will look around and see no other marks. He will therefore know he is the only sinner and leave. Assuming each villager is able to follow this logic, then if no-one has left after the first day, everyone can logically conclude that there are at least two sinners.
2) Suppose there are two sinners. Each of those sinners will see exactly one other sinner, and if each has thought through Point 1, then on the second day each will (a) know that there have to be at least two sinners, and (b) only see be able to one other sinner, so each can conclude that they have to be a sinner, and by this logic both should leave. (On the first day, each sinner would wait, because of the possibility that the other sinner is the only sinner.) Conversely, if no-one has left after the second day, everyone can conclude that there are at least three sinners.
3) Suppose there are 3 sinners. Each of those would see two other sinners. They would then know that there are either 2 or 3 sinners, depending on whether or they themself are a sinner. By the third day they would know that, because of Point 2 above, there can’t be only two sinners, so they would leave. Conversely, if no-one has left after the third day, everyone can conclude that there are at least four sinners.
Since the sinners all leave on the third day, there are therefore 3 sinners.
I am confused by the 3 argument. The sinners don’t leave on the third day. They leave after the third meeting. The third meeting is at the end of the third day. The problem states that they leave after the third gathering. It seems to me that you are stating they leave after the second gathering. Your sinners don’t show up to the third gathering. The problem states that after they are told, they go about their business and meet at end of the day (the gathering) to see if they should leave following your logic, which I also agree with. After the third of said gatherings, they pack up and leave. There has to be 4 sinners they way I read this.
Fair point. The question says ” the whole village gathers in the square at the end of every day so that everyone can see if there are still any sinners left among them”, so I should have referred to gatherings rather than days. Ie, they look around during the gathering, perform do their thinking, and leave at the end.
Thank you for explaining this in detail. It finally makes sense to me :)
By the way, I hadn’t worked it out until after I saw the earlier solutions.
I’m with TomP, I don’t see the logic in presenting the progression of 1, 2, 3 sinners.
On day one, meeting one, N sinners see N-1 sinners. But they don’t know if they’re seeing N-1 or N, they have to assume one or the other.
And the saints (non-sinners) see N sinners, but don’t know if they are actually seeing N-1 sinners or not, because no one can indicate in any way to anyone else their status as sinner.
So what is it about meeting three that is different than meetings one and two that makes all the sinners leave? Why don’t all the saints leave, assuming they are the Nth sinner because they don’t know if they’re seeing N-1 or N sinners?
I think most of the analysis so far is dependent on the progression from 1, 2, 3, and sinners leaving because they assume they’re sinners, while totally neglecting the saints who are just as likely to leave because they assume they’re sinners as well. And the progression from 1 to 2 to 3 isn’t valid, because we would start with N sinners at meeting one, not 1 sinner at meeting one, and 2 sinners at meeting two, etc.
My idea for a solution is a toss-up between doing some sort of binary search by splitting the group successively smaller, or maybe because people can tell each other that they are saints (not sinners) through some loophole in 11th commandment “Thou shalt not tell the sinner if they are a sinner.”
For the first one:
How about, the whole town picks one random dude from the crowd, and he sorts everyone depending on what he can see about them. Everyone know knows what he is, but do not know what they are, and he knows what everyone is, but not himself.
At this point, he picks a guy from each group to represent it as a whole, and he asks one of these representatives, (let choose the sinner), to take his place and sort him out. At this point, the first one knows what he is because if he is in the same group as the third one, he’s not sinner, if he is in the group of the third one he knows he’s not a sinner, and now the one sorting also knows what he is, as he knows where he put the first one. If in the group of the third one, then he knows himself does not belong in that group, or he first one is in the contrary group to the third guy, the second knows he’s in the same group as the first.
At this point, the three guys know what they are, and at least one of them is a sinner, so the whole town should follow the representative in his group, if he goes out of town, then they know they should go to.
(It’s a bit of a mess to explain with words, not sure if I was clear)
I was typing as I was thinking, so I repeated a few sentences and I can’t edit, I am sorry.
And there are a few special cases in case everyone is a sinner or not sinner, etc. But these are easy to work out.
And I just realized I answered the wrong question, I read the thing and assumed things. Feel free to not include my answer or these additional comments. !
I think the first question only works if the following condition is added: “No villager can communicate with another villager using any means.”
If there is any communication, then information from the whole group can be used to instantly figure out who are the sinners. For example, here is a solution that works just as quickly regardless of the number of sinners:
The village chief tells everyone, “as soon you see don’t see any more sinners, just break out and party”. Then he selects a random villager to just say if he sees odd or even number of sinners in the village. Everyone else can see if this randomly selected villager is a sinner. So the logic is:
For everyone else:
1. If the selected villager is NOT a sinner, and what you see does not match what he says, then you are a sinner. So you leave.
2. If the selected villager is a sinner, and what you see matches what he says, then you are a sinner. So you leave.
At this point, the selected villager may or may not be the only sinner left. If he sees everyone else starting to party, then he’s not a sinner. If everyone is standing still, he knows he’s the last sinner so he leaves.
It took me a while to follow the reasoning for the sinner question. What helped was setting an arbitrary number of villagers and then putting it all on a spreadsheet, including each person’s thoughts:
https://spreadsheets.google.com/pub?key=0AvDAAxZ4Y8OedFZiVU1hdUdtZVgyclJ0V2xXd3NMUmc&hl=en&output=html