14
$\begingroup$

A hotel is in the form of a grid that extends infinitely to the right and above, and a strange alien lives in the corner room. The proprietor wishes to vacate the six rooms closest to the corner, but every time he tries to push the alien out of a room, the alien splits into two copies. One copy goes into the room to the right, and one copy goes into the room above. Each room can contain at most one copy of the alien (this means that a clone cannot be vacated from his current room if one of the rooms to his right or top is occupied by another clone). Can the proprietor vacate the six rooms in the corner in finite time?

https://latex.artofproblemsolving.com/c/d/7/cd7d663d1735be017c3ed4e3bc28904039539ca3.png

$\endgroup$
13
$\begingroup$

The puzzle is

impossible.


Proof

Split the infinite grid up into NW-SE diagonals of length 1, 2, 3, 4, ... Assign each cell a value

of $2^{-n}$ if it lies in the $n$th diagonal: so we have one cell of value $1$, two of value $\frac{1}{2}$, three of value $\frac{1}{4}$, four of value $\frac{1}{8}$, and so on.

Then the total value of all occupied cells is an invariant, because each move replaces

a cell of value $2^{-n}$ by two cells of value $2^{-n-1}$ for some $n$.

Initially this total value is

$1$.

If the first three diagonals are empty, then

the maximum possible total value is $$4\cdot2^{-3}+5\cdot2^{-4}+6\cdot2^{-5}+7\cdot2^{-6}+\dots=\frac{d}{dx}(x^4+x^5+x^6+\dots)\big|_{x=1/2}=\frac{4x^3-3x^4}{(1-x)^2}\Big|_{x=1/2}=\frac{5}{4}.$$

Note also that - as @xnor points out in the comments -

the first row and the first column can only have at most one cell filled at any time. So from that total value of $\frac{5}{4}$, we must subtract at least $2(2^{-4}+2^{-5}+2^{-6}+\dots)=\frac{1}{4}$ to get an absolute theoretical maximum of $1$. Of course, this theoretical maximum involves filling an infinite number of cells, so it cannot be achieved in finite time. Thus, the problem is impossible.

$\endgroup$
  • 5
    $\begingroup$ I think you can complete your argument by noting that since the first row and first column each only ever contain 1 filled cell, at least 1/4 total value of the 5/4 is wasted. $\endgroup$ – xnor Feb 20 '18 at 2:11
  • $\begingroup$ @xnor Very nice! (I got as far as Rand did and was stuck in the exact same way, but I agree that your observation cracks it.) $\endgroup$ – Gareth McCaughan Feb 20 '18 at 2:26
  • $\begingroup$ @xnor Thanks! :-D Excellent observation. $\endgroup$ – Rand al'Thor Feb 20 '18 at 12:07
  • $\begingroup$ @Displayname Solution completed, thanks to help from xnor. $\endgroup$ – Rand al'Thor Feb 20 '18 at 12:07
  • $\begingroup$ Except that those four cell of value 1/8 are actually value 0 since they're outside the zone the person is trying to vacate. Same with every cell after that. The proprietor is only trying to vacate 6 rooms. $\endgroup$ – PopularIsn'tRight Feb 20 '18 at 15:19
7
$\begingroup$

Answer:

It's not possible to clear the rooms in finite time.

To see why, lets count the minimum number of times an alien needs to be evicted from each room.

First, lets define a function $C(x,y)$ that tells us if we're outside the corner area we're trying to clear. If $(0,0)$ is the corner room, then:

$C(x, y) = \begin{cases} 0 & \text{if } x + y < 3 \\ 1 & \text{otherwise} \end{cases}$

Now we can begin to define a function $E(x,y)$, which is the number of times we need to evict an alien from room $(x,y)$ to clear the corner area. Since we need to evict the alien from the starting room in the corner:

$E(0, 0) = 1$

$E(x, 0)$ (for $x>0$) and $E(0, y)$ (for $y>0$) are also very easy to compute, since each eviction happens if we got an alien from the square next to us, towards the corner:

$E(x, 0) = E(x-1) - C(x, 0)$

and

$E(0,y) = E(0, y-1) - C(0, y)$.

This leads to the general formula, of $E(x,y)$ where both $x>0$ and $y>0$:

$E(x,y) = \begin{cases} E(x-1, y) + E(x, y-1) - C(x, y) & \text{if } E(x-1, y) + E(x, y-1) > 0 \\ 0 & \text{otherwise}\end{cases}$

We can do an interesting thing with this formula if we apply it recursively once (ignoring the $0$ case):

$\begin{split} E(x, y) & = & E(x-1, y) + E(x, y-1) - C(x, y) \\ & = & E(x-2, y) + E(x-1, y-1) - C(x-1, y) \\ && + E(x, y-2) + E(x-1, y-1) - C(x, y-1) - C(x, y) \\ & = & 2\cdot E(x-1, y-1) + E(x-2, y) + E(x, y-2) \\ && + C(x,y) + C(x-1,y)+C(x,y-1)\end{split}$

We can figure out a lower bounds for $E(x,y)$ in terms of $E(x-1, y-1)$, just by dropping some terms from that equation and assuming the $C$ results are all $1$:

$E(x,y) \geq 2 \cdot E(x-1, y-1) - 3$

Now, lets compute a few values along the diagonal by hand. $E(0, 0)$ is defined to be $1$. $E(1, 1)$ is pretty clearly $2$, since $E(1, 0)$ and $E(0, 1)$ are both $1$ and $C(1, 1)$ is still $0$.

$E(2,2)$ is a little less obvious, but not hard to work out. $E(1, 2)$ and $E(2, 1)$ are both $2$, since they're outside the corner area and $C(1, 2)$ and $C(2, 1)$ are $1$. $C(2, 2)$ is also $1$. That gives us $E(2, 2) = 2+2-1 = 3$. That's as far as we need to go by hand.

Based on the minimum bound formula we calculated above, $E(3,3) \geq 2 \cdot E(2, 2) - 3$. So $E(3, 3) \geq 3$ (it's actually $5$, but the exact value isn't needed).

We can keep going! As long as we know $E(n, n) \geq 3$, then we know that $E(n+1, n+1)$ will also be greater than or equal to $3$.

Conclusion:

Since all values of $E(n, n)$ are positive, the total number of evictions must be infinite, so the alien cannot be removed from the corner area in finite time.

$\endgroup$

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.