[math-fun] Directions to a map without knowing the starting position
Hello everyone I am looking for the name and/or more information about a class of problems, which consist of providing directions to reach a specific point on a map, without knowing where one is starting from. If I remember well, it wasn't even clear whether such maps existed - but some non-trivial examples have been found. The paths were coloured red or blue and directions given "take the red path, take the blue path, etc." Searching for the suspected keywords sends me to Google Maps etc., so I turn to the wisdom and knowledge of math-fun! Thanks in advance Seb
universal traversal sequences, perhaps On Wed, May 17, 2017 at 5:22 AM Seb Perez-D <sbprzd+mathfun@gmail.com> wrote:
Hello everyone
I am looking for the name and/or more information about a class of problems, which consist of providing directions to reach a specific point on a map, without knowing where one is starting from. If I remember well, it wasn't even clear whether such maps existed - but some non-trivial examples have been found. The paths were coloured red or blue and directions given "take the red path, take the blue path, etc."
Searching for the suspected keywords sends me to Google Maps etc., so I turn to the wisdom and knowledge of math-fun!
Thanks in advance
Seb _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It's often called the road coloring problem. Jim Propp On Wednesday, May 17, 2017, Thane Plambeck <tplambeck@gmail.com> wrote:
universal traversal sequences, perhaps
On Wed, May 17, 2017 at 5:22 AM Seb Perez-D <sbprzd+mathfun@gmail.com <javascript:;>> wrote:
Hello everyone
I am looking for the name and/or more information about a class of problems, which consist of providing directions to reach a specific point on a map, without knowing where one is starting from. If I remember well, it wasn't even clear whether such maps existed - but some non-trivial examples have been found. The paths were coloured red or blue and directions given "take the red path, take the blue path, etc."
Searching for the suspected keywords sends me to Google Maps etc., so I turn to the wisdom and knowledge of math-fun!
Thanks in advance
Seb _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On May 17, 2017 9:14:11 AM EDT, James Propp <jamespropp@gmail.com> wrote:
It's often called the road coloring problem.
when i was talking a course in automata theory a similar problem was a synchronization problem - to find a sequence of inputs that would get the fsm to a known state when you don't know what state it is to start with.
On Wednesday, May 17, 2017, Thane Plambeck <tplambeck@gmail.com> wrote:
universal traversal sequences, perhaps
On Wed, May 17, 2017 at 5:22 AM Seb Perez-D <sbprzd+mathfun@gmail.com <javascript:;>> wrote:
Hello everyone
I am looking for the name and/or more information about a class of problems, which consist of providing directions to reach a specific point on a map, without knowing where one is starting from.....
-- Bernie Cosell Bernie@fantasyfarm.com
See https://en.wikipedia.org/wiki/Road_coloring_theorem . Jim Propp On Wed, May 17, 2017 at 9:20 AM, Bernie <bernie@fantasyfarm.com> wrote:
On May 17, 2017 9:14:11 AM EDT, James Propp <jamespropp@gmail.com> wrote:
It's often called the road coloring problem.
when i was talking a course in automata theory a similar problem was a synchronization problem - to find a sequence of inputs that would get the fsm to a known state when you don't know what state it is to start with.
On Wednesday, May 17, 2017, Thane Plambeck <tplambeck@gmail.com> wrote:
universal traversal sequences, perhaps
On Wed, May 17, 2017 at 5:22 AM Seb Perez-D <sbprzd+mathfun@gmail.com <javascript:;>> wrote:
Hello everyone
I am looking for the name and/or more information about a class of problems, which consist of providing directions to reach a specific point on a map, without knowing where one is starting from.....
-- Bernie Cosell Bernie@fantasyfarm.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Many thanks to all, that was it. Does anyone know of puzzles using this? Best, Sébastien On 17 May 2017 at 15:45, James Propp <jamespropp@gmail.com> wrote:
See https://en.wikipedia.org/wiki/Road_coloring_theorem .
Jim Propp
On Wed, May 17, 2017 at 9:20 AM, Bernie <bernie@fantasyfarm.com> wrote:
On May 17, 2017 9:14:11 AM EDT, James Propp <jamespropp@gmail.com> wrote:
It's often called the road coloring problem.
when i was talking a course in automata theory a similar problem was a synchronization problem - to find a sequence of inputs that would get the fsm to a known state when you don't know what state it is to start with.
On Wednesday, May 17, 2017, Thane Plambeck <tplambeck@gmail.com> wrote:
universal traversal sequences, perhaps
On Wed, May 17, 2017 at 5:22 AM Seb Perez-D <sbprzd+mathfun@gmail.com <javascript:;>> wrote:
Hello everyone
I am looking for the name and/or more information about a class of problems, which consist of providing directions to reach a specific point on a map, without knowing where one is starting from.....
-- Bernie Cosell Bernie@fantasyfarm.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Great question. One of my favorite puzzles can maybe be thought of in these terms? The "Coins on a Lazy Susan" puzzle: http://discuss.joelonsoftware.com/default.asp?interview.11.776198.2 Oh hmm, actually maybe not, in that this puzzle's version is adversarial. Oh, and the solution just guarantees that you *pass through* the goal state, not that you *end* at it. (I guess the pass-through version of the puzzle is obviously solvable for finite graphs, by just enumerating all the starting points.) OK don't mind me, evidently I have nothing to say about Seb's question after all. --Michael On Wed, May 17, 2017 at 10:50 AM, Seb Perez-D <sbprzd+mathfun@gmail.com> wrote:
Many thanks to all, that was it. Does anyone know of puzzles using this?
Best,
Sébastien
On 17 May 2017 at 15:45, James Propp <jamespropp@gmail.com> wrote:
See https://en.wikipedia.org/wiki/Road_coloring_theorem .
Jim Propp
On Wed, May 17, 2017 at 9:20 AM, Bernie <bernie@fantasyfarm.com> wrote:
On May 17, 2017 9:14:11 AM EDT, James Propp <jamespropp@gmail.com> wrote:
It's often called the road coloring problem.
when i was talking a course in automata theory a similar problem was a synchronization problem - to find a sequence of inputs that would get the fsm to a known state when you don't know what state it is to start with.
On Wednesday, May 17, 2017, Thane Plambeck <tplambeck@gmail.com> wrote:
universal traversal sequences, perhaps
On Wed, May 17, 2017 at 5:22 AM Seb Perez-D < sbprzd+mathfun@gmail.com <javascript:;>> wrote:
Hello everyone
I am looking for the name and/or more information about a class of problems, which consist of providing directions to reach a specific point on a map, without knowing where one is starting from.....
-- Bernie Cosell Bernie@fantasyfarm.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
participants (5)
-
Bernie -
James Propp -
Michael Kleber -
Seb Perez-D -
Thane Plambeck