[math-fun] more challenge sequences needed
To Seqfans, Mathfun: the people who are planning the contest (I should probably not have described them as French, although my contact has a French email address - they could be anywhere in the world) replied that none of the sequences that I gave them were suitable. Either they failed to meet some of the requirements for a good challenge, or else they were too close to problems that had been used in previous challenges. So they are still looking for a good sequence to extend. Something like the Hadamard determinant problem or the Golomb ruler problem would be perfect, but these have already been used. Here are the constraints on the problem: 1) It must be NP-complete 2) It must be simple to describe 3) It should not have been widely explored 4) A solution must be easy to check (= it doesn't require a lot of computation to check) 5) It has to be computed from N=8 to at most 64 Further suggestions would be welcomed! Neil
1) It must be NP-complete 2) It must be simple to describe 3) It should not have been widely explored 4) A solution must be easy to check (= it doesn't require a lot of computation to check) 5) It has to be computed from N=8 to at most 64
this isn't in the database yet, but how about: a(n) = minimum value of k so that k copies each of cubes of sides 1 through n can be used to exactly fill some rectangular box. a(1) = 1 a(2) = 4 a(3) <= 8 a(4) <= 24 a(5) <= 32 and nothing else is known. if they use this, i want to know the answers! the pictures for the same problem for squares in 2 dimensions are nicer, but the values for n=1-17, 19, and 24 are already known. erich
I guess ( reading message http://groups.yahoo.com/group/AlZimmermannsProgrammingContests/message/1313 ) this contest is supposed to continue a series of Al Zimmermann's Programming Contests. If so, I suggest to look at the older contest problem at http://members.aol.com/bitzenbeitz/Contests/ to an impression on what type of problems the participants are expecting. Max N. J. A. Sloane wrote:
To Seqfans, Mathfun: the people who are planning the contest (I should probably not have described them as French, although my contact has a French email address - they could be anywhere in the world) replied that none of the sequences that I gave them were suitable. Either they failed to meet some of the requirements for a good challenge, or else they were too close to problems that had been used in previous challenges.
So they are still looking for a good sequence to extend. Something like the Hadamard determinant problem or the Golomb ruler problem would be perfect, but these have already been used.
Here are the constraints on the problem:
1) It must be NP-complete 2) It must be simple to describe 3) It should not have been widely explored 4) A solution must be easy to check (= it doesn't require a lot of computation to check) 5) It has to be computed from N=8 to at most 64
Further suggestions would be welcomed!
Neil
... 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@web.de
participants (4)
-
Erich Friedman -
Max -
N. J. A. Sloane -
Rainer Rosenthal