Waste less time on Facebook — follow Brilliant.

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

No vote yet
8 votes


Sort by:

Top Newest

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.

Jimmy Kariznov - 4 years, 2 months ago

Log in to reply

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.

Jimmy Kariznov - 4 years, 2 months ago

Log in to reply

Seems about right to me

Diego Roque - 4 years, 2 months ago

Log in to reply

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

Daniel Leong - 4 years, 2 months ago

Log in to reply

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.

Jimmy Kariznov - 4 years, 2 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...