more challenge sequences needed

[Rob Pratt]

I have participated in all of the previous contests, and requirement 4 refers only to the feasibility of a solution--not the optimality.  It's okay if optimality is hard to prove.  But feasibility should be easy to check so that the contest administrator can quickly give scores for solutions submitted by the contestants.  There is a leaderboard posted throughout the contest, and it is updated each time a new entry is submitted.

Rob

-----Original Message-----
From: r.rosenthal at web.de [mailto:r.rosenthal at web.de] 
Sent: Wednesday, May 25, 2005 12:56 PM
To: math-fun at mailman.xmission.com; seqfan at ext.jussieu.fr
Cc: njas at research.att.com
Subject: Re: more challenge sequences needed


> ... or the Golomb ruler problem would be perfect, but these have 
> already been used.

Hello Neil,

this is far too great a chance for extending my favourite A004137 to let it go without fight :-)

The rulers considered here are *not* the Golomb rulers, for which there is indeed a vast literature and extensive search by globally connected people.

There is just ONE really clever type of rulers, which probably will be optimal for the next may be 10 or 15 arguments: the type invented by Wich- mann in the 1960's.

Computational evidence was quite poor before Peter Luschny did focus on this sequence. 

We weren't able to prove the validity of any method for reducing the search tree. It would be of great value to have solid knowledge about further members of this sequence, so that theoretical considerations could be proved or disproved more easily.

> Here are the constraints on the problem:
> 
> 1) It must be NP-complete

Nobody has proved the opposite.

> 2) It must be simple to describe

Find 1 = x_1 < x_2 < ... < x_n = L  such that the differences x_i - x_j don't have holes and such that L is maximal.

> 3) It should not have been widely explored

I think they should try something, which people are interested in. Otherwise their effort will make nobody happy. And *if* they try something interesting, then surely there *must* have been some exploration done before. The term "widely explored" is widely flexible ;-)

> 4) A solution must be easy to check (= it doesn't require a lot of 
> computation to check)

This may be the killer argument: a solution is proved to be one, if there is no solution for
L+1. And to prove that, you will need very much
time :-(
(While on the other hand it is easy to show that such a set {x1,...x_m} doesn't have holes in its
differences.)

> 5) It has to be computed from N=8 to at most 64

Hmmm... no comment.

Still hoping for the election, and thank you very much for your first friendly welcome to that suggestion of mine,

best regards,
Rainer Rosenthal
r.rosenthal at web.de