Social Question

LostInParadise's avatar

Brain Teaser: Can you solve the loopy Treasure Hunt problem?

Asked by LostInParadise (28993points) December 30th, 2009

I saw this problem in more abstract form and have tried to make a story out of it.

A friend of yours designs what is to be the world’s most elaborate treasure hunt. This is one of those events where people are given a clue about a certain location and then at each location there is a clue to the next one. The winner is the one who first reaches the final location.

But there is a problem. It becomes apparent that one of the locations points back to a previous one, which will lead people through an interminable loop. The locations and clues are so similar that it is not immediately apparent which location is repeated.

You have been called in to help find which location is repeated. In order to avoid the appearance that something is amiss your friend refuses the simple approach of laying down markers for each visited location. However, if you work with a partner and coordinate your movement through the locations by using a cell phone, it is possible to find the repeated location. How can this be done?

Observing members: 0 Composing members: 0

3 Answers

mattbrowne's avatar

Is it NP complete?

LostInParadise's avatar

matt, The problem has linear complexity. I estimate that the number of locations visited by the two people is bounded by 6 times the total.

Following a suggestion by phynix for a previous brain teaser, I am providing an encrypted version of the answer so you can work on the problem on your own if you want, without inadvertently seeing the answer. The encryption is a simple rotate 13 code and you can decrypt it by going to http://www.retards.org/projects/rot13/

Hint:
Gur gernfher uhag ebbg pna or qvivqrq vagb gjb cnegf: na vavgvny frpgvba bs ybpngvbaf ivfvgrq whfg bapr sbyybjrq ol n ybbc. Gur ceboyrz pna or fbyirq va gjb cunfrf. Svefg svaq n jnl bs qrgrezvavat gur yratgu bs gur ybbc be n zhygvcyr bs gur yratgu. Gura hfvat gung inyhr, svaq gur ercrngrq ybpngvba.

Solution, first part:
Lbh naq lbhe cnegare fgneg ng gur ortvaavat gbtrgure, ohg sbe rnpu ybpngvba gung lbh tb gb, lbhe cnegare tbrf gb gjb ybpngvbaf. Xrrc n ehaavat pbhag bs gur ahzore bs ybpngvbaf ivfvgrq. Lbhe cnegare jvyy riraghnyyl pngpu hc gb lbh ntnva. Vs lbh unir tbar gb a ybpngvbaf, lbhe cnegare jvyy unir ivfvgrq 2a ybpngvbaf be a zber guna lbh. Gurfr nqqvgvbany ybpngvbaf zhfg or fbzr zhygvcyr bs gur yratgu bs gur ybbc.

Solution, second part:
Fgnegvat ng gur ortvaavat, unir lbhe cnegare ivfvg gur svefg a ybpngvbaf, jurer a vf gur zhygvcyr bs gur ybbc yratgu qrgrezvarq sebz gur svefg cneg. Sebz gung cbvag rnpu bs lbh zbirf bar ybpngvba ng n gvzr. Jura lbh ragre gur ybbc ng gur ercrngrq ybpngvba, lbhe cnegare jvyy or gurer nyfb.

mattbrowne's avatar

I need to get back to you on that.

Answer this question

Login

or

Join

to answer.
Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther