A little problem.

[the_exiled_one]

You are trapped in a directed graph. At every vertex you can choose to go either left or right. You know nothing about the graph except that it is strongly connected and one of the vertices is an exit. You have no pencil or other means to mark vertices you have visited

Comments

[stagknight]

I would have thought that with no way of marking or identifying vertices, your only solution (or at least the only one I can think of) is to random-walk. At least with it being strongly connected you'll never get stuck in a cycle.

[the_exiled_one]

Random walk will allow you to exit with probability one, yes, but there are deterministic solutions as well.

[djw]

Also, how can you do a random walk without a coin?

[stagknight]

That wasn't there when I replied. :P

[djw]

Izzy xyzzy, let's get busy.