[Guest]

A building has 16 rooms, arranged in a 4x4 grid.  There is a door between every pair of adjacent rooms ("adjacent" meaning north, south, west, and east, but no diagonals).  Only the room in the northeast corner has a door that leads out of the building.

At the start, there is one person in each room.  The person in the southwest corner is a serial killer.  The killer has the following traits:  If he enters a room where there is another person, he immediately kills that person.  But he also cannot stand the sight of blood, so he will not enter any room where there is a dead person.

Only he knows about the exit door in the northeast corner of the building.

Part 1: As it happened, from that initial configuration, the killer managed to get out of the building after killing all the other 15 people.  What path did he take?

(Details for part 1: The other 15 people do not change rooms)

Part 2: If everyone in the bulding knows about the exit door and that there is a serial killer in the SW corner room, what is the maximum and the minimum number of people that the killer can kill assuming that if any one of the other 15 people is in the NE corner room, he will go out of the building (same day)?

(Details for part 2: At a time, there can only be one person (excluding the killer) in one room. If a person A wanting to change room sees someone else already in the room, A will look to move to some other room (or go back to his room). If two people walk into an empty room simultaneously, only one of them stays in that room and the other one looks for some other room (or goes back to his room). The other 15 people can change the room once a day and the killer changes the room once a day.)

[Guest]

For part 1

Can't he just go through all the rooms in order? like room 1 on southwest then he goes east to room2 and then east (room3) then east again (room4) and then north (room5) then west(room6) etc....

Edit was just that i thought it was an 8x2 grid, then changed it to a 4x4

Edited July 22, 2009 by Assassinator

[Guest]

For part 1

Can't he just go through all the rooms in order? like room 1 on southwest then he goes east to room2 and then east (room3) then east again (room4) and then north (room5) then west(room6) etc....

Edit was just that i thought it was an 8x2 grid, then changed it to a 4x4

Try it on a piece of paper. In this case he will end up on the NE corner with some rooms left unvisited.

[Guest]

well..

then he can go into the northern room and then back into his own room and then follow a number of different paths

[Guest]

d31b0y beat me to it. Took a while to realize he could re-enter the room in which he started(still sleeping).

Ken

[Guest]

well..

Exactly. Now for the second part...

[Guest]

for part 2, by trial and error (not going to post as I did with pen and paper) I have that the minimum he could kill is 2.

[Guest]

I'm probably grossly misinterpreting this problem but I'd say the maximum number of deaths would be 15 since it says the people "can" switch rooms once a day, but dont have to. If a person in the NE corner has to leave to leave, then I guess the answer would be 14 since the person who starts there will already be out by the time the game begins. If everyone stays put, its the same situation as the first problem.

As for the minimum number of deaths, I'd say they can all get out although there is probability of a stalemate if the killer keeps moving between the NE door and some other spot. Then the killer and some amount of people which I didn't bother trying to figure out would be doomed to live their lives in this 4x4 grid and probably die of starvation. Horrible way to go.

This solution only works if a person can move into a room that was immediately previously held by someone else. For example, there are 4 people in north row (1 in each row), they can all simulateneously move east (with one guy exiting). Also, the people running away from the killer also miraculously know the path the killer was taking before he made his move. Like a clairvoyance of sorts. So if we look at the initial grid with everyone in it, the NE guy would leave and then everyone else would sort of move into the open space always away from where the killer leaves. When possible, people would escape.

Like I said, this theory could be completely botched with my assumptions.

[Guest]

if he killes someone at the exit then he wont be able to go back so therefore people would have a better chance of escaping ? im still working on it

[Guest]

Ok, so, quick clarification,

assume there are two people in this grid, Killer in Southwest and Person to his East. If both people want to move east, does the Person die? or does the person move first?

If the person moves first and escapes the killers grasp, then i can think of many solutions where the killer does not kill anyone for the minimum.

Still working on the max

[Guest]

Part 1: 2 ways both require killer to re-enter his own room.

Part 2: Minimum 0, Maximum 15 (Victims CAN move, Killer MUST move)

[Guest]

Ok, so, quick clarification,

assume there are two people in this grid, Killer in Southwest and Person to his East. If both people want to move east, does the Person die? or does the person move first?

If the person moves first and escapes the killers grasp, then i can think of many solutions where the killer does not kill anyone for the minimum.

Still working on the max

Assume that the other 15 people move after the killer has moved. So, on the first day, 1 person will die when the killer moves to a different room.

[Guest]

Part 1: 2 ways both require killer to re-enter his own room.

Part 2: Minimum 0, Maximum 15 (Victims CAN move, Killer MUST move)

Victims CAN move means they move only if an adjacent room is not occupied. By the way, even if no one moves, at least the person in the NE corner will escape!

[Guest]

The minimum is going to be 1 because the killer moves 1st. But after that the minimum stays at 1. If the killer goes the other way, he's going to get at least 5 people. But after that I don't know how to solve it. There's too many combinations. I'll try this. Min: 1; Max: 6.

Max 6 because there's always going to be someone in the NE corner for him to kill if he's exiting.

Edited July 22, 2009 by Dunpeal