×

# Yet another question about locating things!

This reminded me of yet another problem, but a more discreet one. It goes a bit like this.

A pair of lovers married yesterday, but in the craziness of the after party, they wake up in different houses (A house would be a point in the lattice grid Z*Z). The groom knows well that the wife is an anxious person, and will walk A streets North, B streets East and sleep there (A and B can be negative, and -4 north is 4 south for example), each day with constant A and B. "Woe is me!" He exclaims because he does not know where is she, and he does not know A nor B.

The groom is very fast so he can move from any house to another in a matter of seconds, but he can only check a house per day because he is a slow searcher. (That means, you can ask each day one house "Is the bride here?"). Can the groom, with complete certainty, catch the bride?

Note by Diego Roque
4 years, 2 months ago

Sort by:

Is there any time limit on how long the groom can take to catch the bride (other than being finite)? If not:

Let $$(x,y)$$ be the initial house the bride is at, Then, on the $$n$$-th day, she is at $$(x+An,y+Bn)$$.

We know that $$\mathbb{N}_0$$ and $$\mathbb{Z}^4$$ have the same cardinality. So, let $$f : \mathbb{N}_0 \to \mathbb{Z}^4$$ be any bijection.

On the $$n$$-th day, compute $$(x',y',A',B') = f(n)$$. Then, have the groom search $$(x'+A'n,y',B'n)$$.

In other words, on the $$n$$-th day, the groom guesses that the bride started at the point $$(x',y')$$ and moves $$(A',B')$$ each day, and then searches the house the bride would be in based on that guess.

On the $$f^{-1}(x,y,A,B)$$-th day, the groom guessed correctly, and therefore found the bride.

Note that this could take an arbitrarily long, but finite time.

- 4 years, 2 months ago

This problem as well as the pirate ship problem have the following general strategy:

1. Find a formula for the position of the target at any time in terms of some set of initial parameters.

2. At each time, make a different guess for the values of those parameters, and go to the corresponding location.

3. Make sure that you will guess correctly after a finite amount of time.

- 4 years, 2 months ago

- 4 years, 2 months ago

Simple! Once the bride reaches a corner, she cannot go any further. So the groom waits Z days and searches all the corners

- 4 years, 2 months ago

When Diego wrote "Z*Z", I think he meant $$\mathbb{Z} \times \mathbb{Z}$$, i.e. the set of ordered pairs of integers.

This set extends infinitely in all directions and doesn't have "corners" for the bride to get stuck in.

- 4 years, 2 months ago