[math-fun] Superexponential haystacks
What are people's favorite examples of problems in which one is looking for needles in a superexponential haystack that we suspect contains exponentially many needles but can't prove contains any at all? Here I am adopting Richard Guy's nice way of describing such problems, which he used last summer when he taught me about a beautiful example of this phenomenon (which I hope I am remembering correctly): It is almost certainly true that for all n sufficiently large, you can arrange the integers from 1 to n in a circle in such a fashion that any two consecutive numbers add up to a perfect square. But no one can prove it. I just learned about another nice example from Barry Cipra. His Bricklayer's Challenge ( http://www.pavelspuzzles.com/2012/11/the_bricklayers_challenge.html) appears to be solvable for every n, but nobody knows how to prove it for infinitely many n. I hereby rule out answers to my question in which the "needle-ness" of the needle takes a long time to verify. This is the case for some Ramsey theory problems that are shown to be solvable by the probabilistic method. It is also the case for codes that come close to the Shannon bound (which again are proved to exist by the probabilistic method). Jim Propp
On Jan 8, 2016, at 6:22 PM, James Propp <jamespropp@gmail.com> wrote: . . . . . . I just learned about another nice example from Barry Cipra. His Bricklayer's Challenge ( http://www.pavelspuzzles.com/2012/11/the_bricklayers_challenge.html) appears to be solvable for every n, but nobody knows how to prove it for infinitely many n.
At that URL I see three challenges mentioned, none of them depending on an integer n. Feel free to clarify. —Dan . . . . . .
The general problem is to find n+1 permutations of the sequence 1,2,3,...,2n such that all (n+1)(2n-1) partial sums are distinct, or equivalently, such that every integer strictly between 0 and 1+2+3+...+2n occurs exactly once as a partial sum. (Here a partial sum of a sequence is neither allowed to be empty nor allowed to coincide with the original sequence.) E.g., for n=2, we can use 1,2,3,4 (with partial sums 1,3,6) and 4,3,1,2 (with partial sums 4,7,8) and 2,3,4,1 (with partial sums 2,5,9). It seems that this can be done for all n, but nobody knows how to prove it. Jim On Friday, January 8, 2016, Dan Asimov <asimov@msri.org> wrote:
On Jan 8, 2016, at 6:22 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote: . . . . . . I just learned about another nice example from Barry Cipra. His Bricklayer's Challenge ( http://www.pavelspuzzles.com/2012/11/the_bricklayers_challenge.html) appears to be solvable for every n, but nobody knows how to prove it for infinitely many n.
At that URL I see three challenges mentioned, none of them depending on an integer n.
Feel free to clarify.
—Dan
. . . . . . _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Aha. Very interesting. —Dan
On Jan 8, 2016, at 9:41 PM, James Propp <jamespropp@gmail.com> wrote:
The general problem is to find n+1 permutations of the sequence 1,2,3,...,2n such that all (n+1)(2n-1) partial sums are distinct, or equivalently, such that every integer strictly between 0 and 1+2+3+...+2n occurs exactly once as a partial sum. (Here a partial sum of a sequence is neither allowed to be empty nor allowed to coincide with the original sequence.)
E.g., for n=2, we can use 1,2,3,4 (with partial sums 1,3,6) and 4,3,1,2 (with partial sums 4,7,8) and 2,3,4,1 (with partial sums 2,5,9).
It seems that this can be done for all n, but nobody knows how to prove it.
participants (2)
-
Dan Asimov -
James Propp