10
$\begingroup$

A person was trapped in a building, and you have to save him. You are a police officer and you will arrive at the building at 7 o'clock in the morning. The building looks like this:

enter image description here

Every 2 minutes, you, the person and the interior walls will become invisible. You don't know where the person is but you know that he will move to an adjacent room every 2 minutes. However, you can check any room in the building every 2 minutes because you have a cop car.

Unfortunately, at 7:29 am, the entire building will explode, killing both of you! You have to find a way to save the person, there is not much time left! Note: Your first checking is at 7:02 a.m.

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ What's the role of the building interior turning invisible every 2 minutes? It strikes me as very odd, but I can't see how that affects the problem in any way - you can still only search one room at a time. $\endgroup$
    – Nuclear Hoagie
    Nov 19, 2020 at 18:13
  • 1
    $\begingroup$ If all the interior walls turn invisible, why can't you just park yourself in room 3, wait for the walls to turn invisible, and look all the way down each wing in turn to find out where the missing person is? $\endgroup$
    – Michael Seifert
    Nov 19, 2020 at 19:39
  • $\begingroup$ @NuclearHoagie well there are no doors, so $\endgroup$
    – Matheinstein
    Nov 19, 2020 at 23:43
  • 1
    $\begingroup$ My point is that if you're in Room 3, and all the walls are invisible, you can see into Room 2 and see if the person is there. And you can see all the way through Room 2 into Room 1 and see if he's there. In fact, if all the interior walls are invisible, you can see the entire interior of the building from Room 3. I assume this isn't what you intended; I merely say this to point out that the "invisible walls" thing is confusing, and you might want to rephrase it for clarity. $\endgroup$
    – Michael Seifert
    Nov 19, 2020 at 23:51
  • 1
    $\begingroup$ @Matheinstein Now I understand it even less. So this is a building with no doors where the interior walls and everybody inside turns invisible every two minutes. What's the point of any of that information? You can't see anything except the exterior wall when the invisibility turns on, so I don't see how it helps or hinders you in any way. It seems like the question would be unchanged if it were a regular building, with doors between rooms and opaque walls. $\endgroup$
    – Nuclear Hoagie
    Nov 20, 2020 at 13:30

2 Answers 2

Reset to default
18
$\begingroup$

If the person can stay in those 2 minutes, the problem will be unsolvable because he can only move if and only if we check his room.

Otherwise, here is a solution with exactly 15 14 (thanks @JaapScherphuis!) checkings, just in time!

Let $x$ be his possible rooms and the yellow cell is the room to be checked.

enter image description here

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Well, the person will always move since they are trying to escape. $\endgroup$
    – Matheinstein
    Nov 19, 2020 at 9:50
  • 3
    $\begingroup$ Good job, but there are solutions with 14 checkings $\endgroup$
    – Matheinstein
    Nov 19, 2020 at 10:07
  • 2
    $\begingroup$ Your second move seems to be redundant, as the rooms marked with an x remain the same. $\endgroup$
    – Jaap Scherphuis
    Nov 19, 2020 at 10:37
  • $\begingroup$ OOPS, you're right @JaapScherphuis ! The second move is actually redundant. Will fix it once I get my laptop, thanks! $\endgroup$
    – athin
    Nov 19, 2020 at 11:19
4
+50
$\begingroup$

This is not a new solution but an easy way to understand how it works:

The first thing to do is a standard checkerboard coloring so the person to catch will alternate colors with every move. Let's assume the center square is black.

If we knew parity it would be easy: At black moves we sit in the center, that way the person cannot change arms without running into us. At white moves we check the arms one after the other. This is possible because there is only one white room per arm. We can start this procedure at a white square and it will take 7 moves.

Now, we do not know parity, but there are only 2 possibilities. we can simply check them one after the other and will be finished after at most 2x7 = 14 moves. enter image description here

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.