mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-05-13, 09:33   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default Hamiltonian path

Hi,

One of my students gave me this problem this morning. I know very little about graph theory to know if it's possible. I'm enjoying puzzling through it at the moment so any solutions of proofs of impossibility, please cover with spoiler tags!

Find a hamiltonian path* through the following network which starts at the point 'O':
Code:
x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - O - x
*must pass through every vertex ('x') exactly once.
lukerichards is offline   Reply With Quote
Old 2019-05-13, 10:06   #2
AKG
 
May 2019

22 Posts
Default

Quote:
Originally Posted by lukerichards View Post
Hi,

One of my students gave me this problem this morning. I know very little about graph theory to know if it's possible. I'm enjoying puzzling through it at the moment so any solutions of proofs of impossibility, please cover with spoiler tags!

Find a hamiltonian path* through the following network which starts at the point 'O':
Code:
x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - x - x
|   |   |   |   |
x - x - x - O - x
*must pass through every vertex ('x') exactly once.
you need parity argument.

Mark each x black and white like a a chessBoard (corner white preferably).
You have to start from a black square (total count 12), visit 13 white square and 11 black which is impossible.

Last fiddled with by henryzz on 2019-05-13 at 11:00
AKG is offline   Reply With Quote
Old 2019-05-13, 10:34   #3
AKG
 
May 2019

22 Posts
Default

Tackle by parity, 13 white / 12 black. You start from black have to visit 13 white interspersed with 11 black. Not possible,

Last fiddled with by henryzz on 2019-05-13 at 10:59
AKG is offline   Reply With Quote
Old 2019-05-13, 10:59   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3·1,951 Posts
Default

@AKG Doesn't that only apply to cycles not paths?

I have added spoilers so that others can solve.
henryzz is offline   Reply With Quote
Old 2019-05-13, 12:12   #5
AKG
 
May 2019

22 Posts
Default

That is condition, pass through 'x' only once. Answer is not concerned with which path or cycle you follow.
AKG is offline   Reply With Quote
Old 2019-05-14, 01:54   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

17×19×29 Posts
Default

This problem is similar to the Domino-Chess puzzle, which sucked tons of ink a century ago... All ladies from higher society used at a point in their life, at some party, to play placing dominoes on the chess board. Even nowadays, if you propose it as a social game at some party, plenty of people will argue for hours about placing dominoes on this or that direction. Try it! (be prepared with a chess board and a domino set hehe).

Solving such problems by backtrack (the natural way the human mind thinks) has exponential complexity. For just a little bigger board you will need thousands of years. Unless you see the parity trick. (Yeah, I read the spoilers above, but I knew the problem and the solution long before, Graph Theory was one of my strongest points in school, we - as a group of about 10 students - and our professor did few important steps in proving the infamous (at the time) Berge's conjecture (now it is known as the "strong perfect graph theorem"). Which, I believe, it is an important step in proving that P=NP. No joke, talk to you about this in about 50 years...

Last fiddled with by LaurV on 2019-05-14 at 02:04
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Fastest Path a1call Puzzles 23 2016-03-23 17:46
Path Counting henryzz Puzzles 13 2014-09-17 11:21
Best settings and upgrade path for i7-2600 emily Hardware 20 2012-03-02 08:45
Expected Path Length davar55 Puzzles 12 2008-02-26 21:53
Are you in the path of Isabel jocelynl Soap Box 14 2003-09-22 20:38

All times are UTC. The time now is 01:20.

Mon Apr 12 01:20:07 UTC 2021 up 3 days, 20:01, 1 user, load averages: 1.78, 1.56, 1.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.