Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Factors and Multiples - Hamiltonian Path


Date: 11/02/98 at 22:29:02
From: Joey Dawson
Subject: Factors and Multiples

We have to make a sequence of numbers, all different, each of which is 
a factor or a multiple of the one preceding it. The numbers in this 
sequence have to be from 1-100, 1 being the last number in the 
sequence. An example of this is: 3-15-30-10-5-35-7-21-3. We have to 
use as many numbers as possible. Everyone in my class has figured out 
the most number of numbers there has to be in the sequence. Can you 
help me figure out how many numbers is the most numbers there can be 
in the sequence? I would appreciate it very much if you could help me. 
Thank you very much.

Your mathematician friend,
Joey Dawson


Date: 11/04/98 at 12:01:56
From: Doctor Peterson
Subject: Re: Factors and Multiples

Hi, Joey. This is a pretty big problem. I haven't found any easy 
solution. I'll just tell you how I've been looking at it and maybe you 
will be able to finish it up.

I see this in terms of what we call graph theory, which has to do with 
things like maps that show relations between objects. To keep things 
simple, let's just work with numbers up to 12, rather than all the way 
to 100. I have drawn a diagram that shows which numbers could be 
adjacent in your sequence, by drawing a line between any pair of 
numbers one of which is a divisor of the other:

      3---12---4
     / \ /  \ / \
    9   6----2---8
             |
    7       10
             |
    11       5

This says that 2 divides 4, 6, 8, 10, and 12; 3 divides 6, 9, and 12; 
4 divides 8 and 12 and is a multiple of 2; 5 divides 10; 6 divides 12 
and is a multiple of 2 and 3; 8, 9, 10, and 12 don't divide anything 
but are multiples of other numbers. 7 and 11 divide nothing in this 
range, so they are disconnected from the rest of this "graph." Of 
course 1 could be connected to every number, but since it has to be 
the 
last number in the sequence (the answer would be a little different if 
that weren't required), we don't need to show it.

You can see that 7 and 11 won't be included in any sequence you can 
make, because there is no number other than 1 that they could be next 
to. In general, any prime bigger than half the limit (100 in your 
problem) will be neither a multiple nor a factor of any number in the 
range.

The problem now is just to draw the longest path that goes through 
each 
number only once. That's not hard. There's one path that will go 
through the whole "connected" part of the graph:

      3   12---4
     / \ /      \
    9   6    2---8
             |
    7       10
             |
    11       5

The longest sequence, then, is:

    5, 10, 2, 8, 4, 12, 6, 3, 9, 1

(or the reverse), and includes all the numbers that could possibly 
have 
been in such a sequence. (This is called a "Hamiltonian path.")

I expanded this to include the numbers 1-25, and found no Hamiltonian 
path through all the numbers. I had to leave out three numbers in 
addition to 13, 17, 19, and 23 that are not connected to the rest. But 
I'm not sure I could prove I found the longest path, without trying 
all 
possible paths. 

With 100 numbers, it would be even harder. But at least we know a 
maximum size for the path (that is, which numbers _have_ to be left 
out), although we don't know whether we can actually make a path that 
size until we try.

Keep playing with this, and let me know if anyone finds a way other 
than brute force to find the longest sequence or to prove that you can 
find a Hamiltonian path in the graph for 1-100. You may find some 
feature of these particular graphs that makes it easy to find a path.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Discrete Mathematics
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/