Secure offline treasure hunt
There's no cryptographic way to keep users from faking their location without trusted hardware. There's also no good way to keep users from running multiple copies of whatever algorithm verifies a location guess in parallel, again without trusted hardware.

The best that can be done for an offline system is to make the is_coordinate_close() function expensive to compute. Still a user can then either bring a powerful portable computer or connect to remote computing capacity to brute force the data set you provide. Additionally, increasing the cost of the function increases the power consumption of your app. 

There are two options that get rid of this tradeoff:


cryptographic secrets at the locations (EG:QR codes)
DRM capable hardware (Phone as trusted third party)