Projects on Puzzles or Mazes
Date: 11/13/2002 at 23:39:35 From: Song Yee LeBaron Subject:High school science projects Hi, I'm in the 10th grade and in my high school's science club, and I would like to do a mathematics project. I need a project soon, and I am having trouble finding a good project idea to use. My knowledge level: I'm taking calculus this year. I would like to do a project that involves applying mathematics to areas like puzzles or mazes. I would appreciate it VERY MUCH if you would send me some information on some project ideas! Thanks so much, Song Yee L.
Date: 11/15/2002 at 08:05:18 From: Doctor Ian Subject: Re: High school science projects Hi Song Yee, Do you have a favorite kind of puzzle? An analysis of why it works, along with a method of generating other puzzles, might be interesting. For example, you're probably familiar with puzzles like this: Who Owns the Fish? (Einstein's Problem) http://mathforum.org/library/drmath/view/60971.html Would it be possible to come up with an _algorithm_ for making up puzzles like this? Or, if you're given one that someone has made up, is there a way to tell, without working out the answer, whether the clues in a puzzle are sufficient to come up with a solution? Whether the solution is unique? The point would be to come up with a 'theory of logic puzzles' that would apply to _all_ puzzles of this sort. You could do a similar thing with mazes - is there a way to tell, without actually finding a solution to a maze, whether a solution exists, and is unique? Does this sound interesting? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/
Date: 11/16/2002 at 14:19:29 From: Song Yee LeBaron Subject: High school science projects Hi Ian, I like those ideas you mentioned, that's the kind of thing I was looking for. I have a question about how you said you could do a similar thing with mazes. What type of mazes are you talking about... or does it matter? Could you use the simple line mazes? And if so, where would be a good place to start, or to get information on this project idea? Thanks again, Song Yee L.
Date: 11/17/2002 at 09:25:17 From: Doctor Ian Subject: Re: High school science projects Hi Song Yee, A big part of doing the project would be defining what _you_ mean by a maze, and finding a way to represent it that makes it accessible to mathematical analysis. In the general sense, a 'maze' is anything that forces you to make a sequence of decisions in order to get from some initial state to a 'goal state'. In artificial intelligence, this is referred to as a 'search space', and a maze is just one particular way of visualizing a search space. In fact, the choice of representation can make a huge difference. For example, choose any maze, and let the start point be represented by the root of a tree: Start At the start point, you might be able to move in two possible directions, say east or north. Each decision would take you to a point that you could assign a unique label: #1 / n / Start \ e \ #2 At point #2, you might be able to go east or south: #1 / n / Start #3 \ / e s \ / #2 \ e \ #4 And so on. Any time you find yourself returning to a place you've already been, you can stop expanding from there, since you're guaranteed to be exploring the consequences of being there in some other part of the tree. When you get to the point where no further expansion is possible, you have a tree that isomorphic to the maze - that is, the maze and the tree are two different ways of looking at the same thing. But the new representation allows you to answer some questions about the maze that aren't obvious from the original representation, e.g., how many paths (if any) lead to the goal state? What is the shortest path? What is the longest (non-repeating) path, and so on? Which kind of search - 'depth first' or 'breadth first' - would find a solution more quickly? Similarly, you might transform the maze into a connected bidirectional graph, and use graph theory to reason about it. Is this enough to get started? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.