Pokemon scanner maths puzzle

[jack]

As best as I can tell, the pokemon go scanner reports whether a pokemon is within 200m or not. It updates about every 15s (?) When a pokemon is within about 50m (?) it appears.

My current strategy is, when I see a pokemon appear, continue in the same direction, assuming it's more likely I've walked into its radius than that it just spawned, and that it's more likely I've entered its radius closer to head on that obliquely. Mathmos, does that sound true?

If I walk about 200m and it isn't there, I try to curve round sideways. If it disappears again, I backtrack, and knowing two points approx 200m away from it, head for one of the points of those triangles.

But I'm wondering, would it be better that when I see it appear, I immediately turn sideways in the hope of finding two nearby points on the edge of its radius, and then extrapolate a point perpendicular to a line between them? That's harder, because it means I deliberately walk away from it. But maybe it would be quicker to narrow down where it is?

If there weren't a noisy gps and periodic updates, and those numbers were all precise, what would be the best strategy? It reminds me a little of Dr Leader's "you are trapped in a gladiatorial arena with someone who runs at exactly the same speed as you" puzzles, but hopefully simpler :)

Comments

[simont]

I have a nasty feeling this is going to turn out to be one of those problems in which some environmental consideration you aren't modelling turns out to massively affect the prior probability distribution and inform the strategy.

In particular: along what shape of path were you (hypothetically) walking in the first place when you encountered the first indication of this Pokémon's existence?

I think the following extreme case demonstrates that it can in principle make a difference. Suppose you start from the origin, and follow an Archimedean spiral (the one maintaining constant distance between the path on two consecutive turns) with spacing x. Now, when you encounter the outside of the Pokémon's 200m-radius circle of detection, how might that circle be oriented relative to you?

The answer, surely, is that the smaller x is, the closer to almost certain it is that you have barely grazed the very edge of the circle of detection. Because if x = 1 metre, for example, then there's no way your path could be aimed at the very centre of the circle on iteration n, unless it had encountered the edge of the circle 199 turns of the spiral before that.

So if you're following a path of that form, then surely it's pretty much guaranteed that as soon as you catch the first inkling of a Pokémon's existence, you are moving more or less tangent to the edge of its circle, so to get close to the centre of the circle as efficiently as possible you should immediately turn 90° and head directly outwards from the origin.

But if instead you were following some totally different path, say a randomly chosen doubly infinite straight line in the plane (that is, with angle uniformly chosen and perpendicular distance to the origin chosen according to some concrete probability distribution which is uniform enough over the range in question), the answer will be very different and you'll have at least some chance of happening to be aimed somewhere near the centre of the circle.

In between those two extremes, following a path of the form ‘walk around town along whatever collection of well-worn routes make up your normal daily routine, plus a few specifically Pokémon-oriented excursions as and when you feel like it’, it's surely anybody's guess.

[jack]

Huh. That's an interesting point. I hadn't even thought about it, I assumed you could basically solve the "I walk in a straight line" case, and assume that corners were the exception.

There are other environmental considerations, like the pokemon are much more often on a street than down an alley, so if you look on the most obvious routes first, you have an advantage. It's easiest following the river, where there's lots of river-type pokemon, but they're always "ahead", or occasionally "behind" :)

But I was happy to ignore that for a maths solution.

[jack]

Although even if you assume, "I'm somewhere in the plane in a straight line, so is the circle", I don't know if you have difficulty assigning a probability distribution.

[khoth.livejournal.com]

In the "everything is totally precise" version of the problem, walk in an arbitrarily small circle around the point where you were first alerted. That'll give you three points on the 200m circle, and you can then go straight to the middle of it.

[jack]

Oh yes, excellent point.

What if you are somewhere in the circle, though? You can do, "walk in a straight line, if you get to the edge, as above". I don't know if there's anything better (if you still allow a 50m spotting radius, not needing to be on zero).