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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.