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.

$\endgroup$
  • 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 '20 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 '20 at 19:39
  • $\begingroup$ @NuclearHoagie well there are no doors, so $\endgroup$ – Matheinstein Nov 19 '20 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 '20 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 '20 at 13:30
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

$\endgroup$
  • 2
    $\begingroup$ Well, the person will always move since they are trying to escape. $\endgroup$ – Matheinstein Nov 19 '20 at 9:50
  • 3
    $\begingroup$ Good job, but there are solutions with 14 checkings $\endgroup$ – Matheinstein Nov 19 '20 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 '20 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 '20 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

$\endgroup$
  • $\begingroup$ If you illustrate the solution I will accept your solution $\endgroup$ – Matheinstein Nov 24 '20 at 10:22

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.