Sunday, September 17, 2017

A problem I thought was interesting- now...

On Nate Silver's page he sometimes (might be once a week) has a column edited by Oliver Roeder of problems. Pretty much math problems though sometimes not quite.

Some are math problems that I have seen before (e.g., hat problems). I don't bother submitting since that would just be goofy. I would be  ringer.

Some are math problems that I have not seen before, I try to do, I fail, but read the answer and am enlightened. I call that a win.

But some are math problems that I have not seen before, I try to do, I fail, but when I see the solution its a computer simulation or something else that isn't quite as interesting as I had hoped.

I describe one of those now; however, I ask if it can be made more interesting.

The problems is from this column: here

I paraphrase:  Let A be the numbers {1,2,3,...,100}.  A sequence is nice if  (1) it begins with any number in A, (2) every number is from A and is either a factor of multiple of the number just before it, and (3) no number can appear more than once.  Find the LONGEST nice sequence

Example of a nice sequence: 

4, 12, 24, 6, 60, 30, 10, 100, 25, 5, 1, 97

I worked on it

1) By hand I came up with a nice sequence of length 42. This was FUN! You can either have fun trying to find a long nice sequence or you can look at mine here.

2) I tried to prove that it was optimal, hoping that either I would find its optimal or be guided to a longer sequence. Neither happened. More important is that this was NOT FUN.

3) I looked forward to the solution that would be in the next column and would be enlightening. 

4) The next column, which did have the solution, is here! The answer was a sequence of length 77 found by a program that also verified there was no longer sequence. The sequence itself was mildly enlightening in that I found some tricks I didn't know about, but the lack of a real lower bound proof was disappointing.

They mentioned that this is a longest path problem (Graph is {1,..,100} edges are between numbers that are either multiples of factors) and that such problems are NP-complete. That gave the impression that THIS problem is hard since its a case of an NP-complete problem. Thats not quite right- its possible that this type of graph has a quick solution.

But I would like YOU the readers to help me turn lemon into lemonade.

1) Is there a short proof that 77 is optimal?  Is there a short proof that (say) there is no sequence of length 83.  I picked 83 at random.  One can easily prove there is no sequence of length 100.

2) Is the following problem in P or NPC or if-NPC-then-bad-thing-happen:

Given (n,k) is there a nice sequence of {1,...,n} of length at least k. (n is in binary, k is in unary, so that the problem is in NP.)

I suspect not NPC.

3) Is the following problem in P or NPC or ...

Given a set of numbers A and a number k, is there a nice sequence of elements of A of length at least k (k in unary).

Might be NPC if one can code any graph into such a set.

Might be in P since the input has a long length.

4) Is the following solvable: given a puzzle in the Riddler, determine ahead of time if its going to be interesting? Clyde Kruskal and I have a way to solve this- every even numbered column I read the problem and the solution and tell him if its interesting, and he does the same for odd number columns.


10 comments:

  1. I suspect prime numbers larger than 50 can be used to show basic lower bounds on the length of the sequence.

    Consider any sequence - the interior of the sequence cannot contain any prime number larger than 50 since it has to be both preceded and followed by a factor or multiple. This doesn't get us close to 77 though.

    ReplyDelete
  2. Here is a not too difficult argument for an upper bound of 83.

    Let A be the set of primes greater than 25, and their multiples. There are 24 such numbers (16 primes, 6 twice a prime, and 2 three times a prime).

    Note that everytime we "exit" A, it must be through {1,2,3}. Let B be the complement of (S3 U {1,2,3}).
    So, removing {1,2,3} from our path we get at most four "segments", each of which is solely in A or solely in B.
    Now, if we only have A-segments, then the whole path has size at most 27, so we exclude this case.
    So there are at most three A-segments.
    By considering the graph induced on A, we see that an A-segment can have at most 3 vertices in it, and this can only happen by taking something of the form 2p-p-3p, for p a prime between 25 and 33. In particular, such a segment must end with both 2 and 3, so we can only have one A-segment of length 3.
    The other 2 A-segments can have length at most 2, so we can use at most 7 vertices from A.

    This gives an upper bound of 100-(24-7)=83.

    The same argument with {1,2} istead of {1,2,3} gives a bound of 86. I'm guessing going to {1,2,3,4} will improve it further still, and with a bit of case-work, one might be able to get 77 by hand.

    ReplyDelete
    Replies
    1. Here is a slight improvement on the previous argument, to get an upper bound of 80.

      Say that a prime is "large" if it is at least 17. Let A be the set of numbers divisible by a large prime, let B={1,2,3,4,5}, and let C be the complement of A U B.
      Consider what happens to the graph when we remove B. First, note that A and C become disconnected from each other.
      Next, note that A itself becomes disconnected, with one component for each large prime. (For example, one component is {17,34,51,68,85}.)

      Let us now count these components and their sizes.
      There are 10 components of size 1. (Corresponding to primes larger than 50.)
      There are 4 components of size 2. (Corresponding to primes between 33 and 50.)
      There are 2 components of size 3. (Corresponding to 29 and 31.)
      There is one component of size 4. (Corresponding to 23.)
      There are two components of size 5. (Corresponding to 17 and 19.)

      In particular, we have |A|=38.
      Finally, note that, in the components of size 5, the longest paths have length 4. (This is easy to check by hand, but, in fact, is equivalent to solving the original problem for n=5 instead of n=100.)

      We are now ready for the main argument. Since |B|=5, removing B from our path leaves at most 6 "segments", each of which is solely in A or solely in C. If we only have A-segments, then the path has size at most |A|+|B|=43, and we are done.
      We may thus assume that there are at most 5 A-segments. Now, by the consideration above, each of these segments can be of size 4 at most and, in fact, only three of them can have size 4, and the other two must have size 3 at most. So the total length of the A-segments is at most 18.

      This gives an upper bound of 100-(38-18)=80.


      (Note that the situation described above is exactly what happens in James' and Anders answer. So in a sense, it seems it now boils down to finding some long paths in C.)

      Delete
    2. Please email me at gasarch@cs.umd.edu about your
      bound

      Delete
    3. OH- I meant for BOTH of you, Unknown and Gab to email me.

      Delete
  3. Isn't the answer for (2) always yes (for large enough values) for the trivial reason that one can always find a poly(n) length sequence and k<<poly(n) since it's given in unary?

    A typo: Twice "factor of multiple" instead of "factor or multiple"

    ReplyDelete
  4. Perhaps the second problem is NPC: given a cubic graph G with n nodes; mark each edge e_i with a prime number p_i and add it to the set A; and then for each node u that has incident edges e_i, e_j, e_k add the "node number": p_i*p_j*p_k to A. G has an Hamiltonian cycle if and only if there is a nice sequence of length 2n. Informally: the nice sequence must be built with a sequence of p_i (edge) -> p_i * p_j * p_k (node number) -> p_j (edge); a "node number" can only be used once and it can connect only incident edges; once an edge is used, it cannot be reused.

    ReplyDelete
  5. I think by "lower bound" you actually mean "upper bound". But, I guess, this is the TCS jargon for this kind of problems.

    ReplyDelete
  6. Besides the NP completeness of the second problem (given a set A does there exist a nice sequence of it elements having length >= k ); we can also convert Riddler into a 2-players game in which, starting from a given number, each player multiplies or divides it to get another element of A; the first player unabel to "move" loses. But I think that this game is in P and not PSPACE-complete; indeed it can be reduced to Undirected Vertex Geography (each number represents a node and if n1 = a*n2 then there is an undirected edge between them).

    ReplyDelete
  7. If anyone wants to generate the graph (uglier presentation than in the 538 article), it is two lines in Mathematica:

    EdgesQ[a_, b_] := (GCD[a, b] == a || Divisible[a, b]) && a != b;
    g = RelationGraph[EdgesQ, Range[1, n]];

    ReplyDelete