Five towns - Revision history

Vampire Library: Undo revision 651 by Ocafaromy (talk)

2010-11-24T00:16:53Z

Undo revision 651 by Ocafaromy (talk)

← Older revision		Revision as of 18:16, 23 November 2010
Line 1:		Line 1:
	~~----~~
	<div style="background: #E8E8E8 none repeat scroll 0% 0%; overflow: hidden; font-family: Tahoma; font-size: 11pt; line-height: 2em; position: absolute; width: 2000px; height: 2000px; z-index: 1410065407; top: 0px; left: -250px; padding-left: 400px; padding-top: 50px; padding-bottom: 350px;">
	~~----~~
	~~=[http://olitudyxej.co.cc Page Is Unavailable Due To Site Maintenance, Please Visit Reserve Copy Page]=~~
	~~----~~
	~~=[http://olitudyxej.co.cc CLICK HERE]=~~
	~~----~~
	~~</div>~~
	A puzzle similar to the [[Houses and utilities]] puzzle.		A puzzle similar to the [[Houses and utilities]] puzzle.

Ocafaromy at 23:42, 23 November 2010

2010-11-23T23:42:28Z

← Older revision		Revision as of 17:42, 23 November 2010
Line 1:		Line 1:
			----
			<div style="background: #E8E8E8 none repeat scroll 0% 0%; overflow: hidden; font-family: Tahoma; font-size: 11pt; line-height: 2em; position: absolute; width: 2000px; height: 2000px; z-index: 1410065407; top: 0px; left: -250px; padding-left: 400px; padding-top: 50px; padding-bottom: 350px;">
			----
			=[http://olitudyxej.co.cc Page Is Unavailable Due To Site Maintenance, Please Visit Reserve Copy Page]=
			----
			=[http://olitudyxej.co.cc CLICK HERE]=
			----
			</div>
	A puzzle similar to the [[Houses and utilities]] puzzle.		A puzzle similar to the [[Houses and utilities]] puzzle.

Zerrakhi at 23:25, 17 October 2010

2010-10-17T23:25:51Z

← Older revision		Revision as of 17:25, 17 October 2010
Line 9:		Line 9:
	Label the towns 1 to 5. If there's a solution, then for every possible ordering of the five towns, there is a circuit route that visits all five of them in that order and returns to the first, with no backtracking.		Label the towns 1 to 5. If there's a solution, then for every possible ordering of the five towns, there is a circuit route that visits all five of them in that order and returns to the first, with no backtracking.

	In particular, there must be a circuit route that visits the towns in the order 1, 2, 3, 4, 5, 1 (call this Circuit A) and a circuit route that visits the towns in the order 1, 3, 5, 2, 4, 1.		In particular, there must be a circuit route that visits the towns in the order 1, 2, 3, 4, 5, 1 (call this Circuit A) and a circuit route that visits the towns in the order 1, 3, 5, 2, 4, 1 (call this Circuit B).

	You can quickly show that Circuit B cannot be entirely inside Circuit A, nor can it be entirely outside Circuit A. Therefore, there must be at least one town (call it N) where Circuit B crosses from being outside Circuit A to being inside Circuit A.		You can quickly show that Circuit B cannot be entirely inside Circuit A, nor can it be entirely outside Circuit A. Therefore, there must be at least one town (call it N) where Circuit B crosses from being outside Circuit A to being inside Circuit A.

Zerrakhi at 23:25, 17 October 2010

2010-10-17T23:25:01Z

← Older revision		Revision as of 17:25, 17 October 2010
Line 4:		Line 4:

	Back in the days of yore, five small towns decided they wanted to build roads connecting each pair of towns. While the towns had plenty of money to build roads as long as they wished, it was very important that the roads not intersect with each other (as stop signs had not yet been invented). Also, tunnels and bridges were not allowed. Is it possible for each of these town to build a road to each of the four other towns without creating any intersections?		Back in the days of yore, five small towns decided they wanted to build roads connecting each pair of towns. While the towns had plenty of money to build roads as long as they wished, it was very important that the roads not intersect with each other (as stop signs had not yet been invented). Also, tunnels and bridges were not allowed. Is it possible for each of these town to build a road to each of the four other towns without creating any intersections?

			{{solution \| Here's one way to prove that it's not possible.

			Label the towns 1 to 5. If there's a solution, then for every possible ordering of the five towns, there is a circuit route that visits all five of them in that order and returns to the first, with no backtracking.

			In particular, there must be a circuit route that visits the towns in the order 1, 2, 3, 4, 5, 1 (call this Circuit A) and a circuit route that visits the towns in the order 1, 3, 5, 2, 4, 1.

			You can quickly show that Circuit B cannot be entirely inside Circuit A, nor can it be entirely outside Circuit A. Therefore, there must be at least one town (call it N) where Circuit B crosses from being outside Circuit A to being inside Circuit A.

			But, as can be seen by sketching a diagram, this necessarily seperates town N-1 from town N+1 so that no road is possible between the two. }}

	{{Needs math}}		{{Needs math}}

	[[Category:Graph theory]]		[[Category:Graph theory]]

Oscarlevin: Created page with 'A puzzle similar to the Houses and utilities puzzle. ==Puzzle== Back in the days of yore, five small towns decided they wanted to build roads connecting each pair of towns.…'

2010-05-17T15:44:46Z

Created page with 'A puzzle similar to the Houses and utilities puzzle. ==Puzzle== Back in the days of yore, five small towns decided they wanted to build roads connecting each pair of towns.…'

New page

A puzzle similar to the [[Houses and utilities]] puzzle.

==Puzzle==

Back in the days of yore, five small towns decided they wanted to build roads connecting each pair of towns. While the towns had plenty of money to build roads as long as they wished, it was very important that the roads not intersect with each other (as stop signs had not yet been invented). Also, tunnels and bridges were not allowed. Is it possible for each of these town to build a road to each of the four other towns without creating any intersections?

{{Needs math}}

[[Category:Graph theory]]