19
$\begingroup$

You are the first officer aboard the Starship Enterpuzz, and moments after your captain departs for his week-long vacation, you discover that your ship is infested with tiny creatures called doorples.

Doorples come in two varieties: black and red. Both varieties love doors but hate each other.

Knowing that doorples multiply rapidly, you scour the ship and capture all doorples accessible to you, but there are still 16 doorples in a series of 11 rooms inaccessible to you and the crew, as shown below.

             drouble with doorples

The room in blue is a room you can access, but only doorples can pass in and out through the blue doors to the 11 rooms.

During the day, doorples sleep. But when evening comes, they become active and the following sequence of events takes place:

  1. Doorples love passing through doors, and so all the doorples in a room will pass through a door into an adjacent room. If there is only one door, all doorples will pass through that door. If there are two doors, half of the doorples will pass through each one. If there are three doors, a third will pass through each one, etc. All doorples migrate at the same time.

  2. Once the doorples are in their new rooms, if there are both black and red doorples in the same room, they fight. Each red doorple fights one black doorple and the two doorples eliminate each other. As many doorples as possible pair off in this way so that only one variety of doorple remains in the room (or all the doorples are dead).

  3. After all the fights are resolved, the doorples reproduce. Doorples are doorsexual and reproduce in the presence of doors. Doorples in a room with one door won't reproduce, but each doorple in a room with two doors will split into two identical copies of itself, each doorple in a room with three doors will split into three identical copies of itself, etc.

  4. Once reproduction is complete, the doorples settle in for the coming day and go back to sleep.

Since the rooms are inaccessible, the only way to eliminate the doorples is i) by capturing any that come in though the two blue doors during the nightly migration, and ii) by releasing new doorples through these doors during the migration.

Fortunately, you have a huge supply of both black and red doorples to work with. Every evening, you can send as many of either variety through the north door and as many of either variety through the east door as you wish.

Your goal is to eliminate every last one of the doorples in all 11 rooms, since even one doorple can quickly become a million if left unattended.

Can you figure out a strategy to eliminate all the doorples?

And for bonus credit: Can you figure out a strategy to eliminate all the doorples before the captain returns in a week (7 days)?

Good luck, first officer. You'll need it!

$\endgroup$
  • 2
    $\begingroup$ this seems to be a linear system of 11 variables $\endgroup$ – Jasen Jun 26 '16 at 6:35
11
$\begingroup$

If I'm understanding the question right, this strategy should work:

  1. On the first day, release 1 red doorple to the north and 14 black doorples to the east.
  2. On the second day, release 5 black doorples to the north and 13 black doorples to the east. Collect all doorples in the blue room.
  3. On the third day, release 19 red doorples to the north and 46 red doorples to the east. Collect all doorples in the blue room.
  4. On the fourth day, release 33 red doorples to the north and 70 red doorples to the east. Collect all doorples in the blue room.
  5. On the fifth day, release 24 black doorples to the north and 15 black doorples to the east. Collect all doorples in the blue room.
  6. On the sixth day, release 12 black doorples to the east. Collect all doorples in the blue room. All rooms are now empty.

Picture of the number of doorples in each room on each day before the multiplication step. Black is positive, red is negative.


Method of Solving

First, notice that the number of doorples in a room can be represented by a single integer, because the two types cancel out. assign the black ones to be positive and the red ones to be negative.

Next, move the multiplication step to the beginning of the cycle. Then the multiplication and migration steps combine, with the effect that the doorples in each room are copied into each of the neighboring rooms.

We can entirely control the number of doorples in the two rooms adjacent to the blue room. This leaves nine rooms. Each of these rooms will result in one constraint, so we have nine constraints. Each day gives us two degrees of freedom, so it takes five days to have enough variables to guarantee a solution. This is actually one extra, so I arbitrarily set the north room to have zero doorples on the first day.

Now to find and solve the equations to determine the amount of doorples that need to be in the rooms we control on each day. We can calculate the number of doorples that will be in each room after five days if we keep our rooms empty, and also the amount that will result from one additional doorple in each of our rooms on each day. The effects simply add together, resulting in the following equations:

$$n_2+e_1=22\\2n_2+n_4+e_1=30\\n_2+3e_1+e_3=32\\2e_1+e_3+e_5=10\\\ \\n_3+e_2=11\\n_3+n_5=4\\2e_2+e_4=5\\\ \\n_3+n_5+e_1+e_3+e_5=0\\n_2+n_4+e_2+e_4=-3$$

The solution to the equations:

$$n_2=8\\n_3=-5\\n_4=0\\n_5=9\\e_1=14\\e_2=16\\e_3=-18\\e_4=-27\\e_5=0$$

So we just have to place the right amount of doorples to leave these amounts in the north and east rooms each day. This is the strategy at the top of this answer.

$\endgroup$
  • 3
    $\begingroup$ how did you determne this strategy? $\endgroup$ – Jasen Jun 26 '16 at 10:49
  • $\begingroup$ Good show. :) But as Jasen suggests, it would help if you could provide even a rough overview of how you arrived at your solution. $\endgroup$ – COTO Jun 26 '16 at 11:57
  • $\begingroup$ It doesn't look like all the rules are being followed. Last step top right. 9 red move down one but only 3 black move to the right to cancel unless I'm missing something. $\endgroup$ – gtwebb Jun 26 '16 at 14:52
  • $\begingroup$ @gtwebb: f' indicates that the numbers in the room are pre-reproduction (pre-multiplication). Meaning that at the end of that night, the room above the blue room will have $9\cdot 3 = 27$ doorples in it. $\endgroup$ – COTO Jun 26 '16 at 14:56

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.