From sujith@math.rutgers.edu  Tue Nov 30 00:36:50 2004
Received: from localhost (sujith@localhost)
	by math.rutgers.edu (8.11.7p1+Sun/8.8.8) with ESMTP id iAU5anJ20666
	for <zeilberg@math.rutgers.edu>; Tue, 30 Nov 2004 00:36:50 -0500 (EST)
Date: Tue, 30 Nov 2004 00:36:49 -0500 (EST)
From: Sujith Vijay <sujith@math.rutgers.edu>
To: Doron Zeilberger <zeilberg@math.rutgers.edu>
Subject: Musical Partitions
Message-ID: <Pine.GSO.4.44.0411292202060.21045-100000@math.rutgers.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Status: RO
Content-Length: 2750

Dear Professor Zeilberger,

I thought about the Tom Johnson problem and I'm inclined to believe that
S4_n = {0,1,...4n-1} can be musically partitioned into arithmetic
progressions of size four (hereafter 4APs) for sufficiently large n. In
fact, not just 4, I believe that for all k there is n sufficiently large
yielding musical partitions of size k. Here is why.

An arithmetic progression is fixed by the first two terms, and there are,
respectively, 4n+c, 4n-3+c, 4n-6+c ... c (where c is some small constant)
4APs with spacings 1,2,...,4n/3 Thus there are at least

(4n/3 \choose n) * (3n) * (3n-3) * ... * (3) ~ n^n (2.33^n)

ways of choosing n 4APs with distinct spacing. Now we have to see how many
of them avoid repeating elements.

I was hoping that the odds would be no different from (the more general
case of) randomly picking n 4-element subsets of S4_n and checking if
there are any repetitions. The probability of such a collection being good
is

(4n \choose 4) * (4n-4 \choose 4) * ... * (4 \choose 4)
-------------------------------------------------------    ~   e^(-4n)
                   (4n \choose 4)^n


Thus one should expect at least (n/23.4)^n musical partitions.

If we try the same approach for S3_n={0,1...3n-1}, we get at least

(3n/2 \choose n) * (2n) * (2n-2) * ... (2) ~ n^n (1.91^n)

ways of choosing n 3APs with distinct spacing. The probability of a random
collection being good becomes e^(-3n), so that one should expect at least
(n/10.5)^n musical partitions. As it turns out, n=5 works.

I rewrote the code replacing k by 4 (option remember seemed to make things
worse). Just finished n=18 (7'34'') and n=19 (23'50''). I expect the
computation for n=22, which is about the time I expect anything
interesting to happen, to take the better part of a day. Will resume
tomorrow. Doesn't Ekhad ever complain?

If you think there is any merit in the aforementioned assumptions, I'll be
grateful if you could check the above calculations and/or try a more
efficient implementation.

                                                          Sujith


-----

Tom4:=proc(n) local i:

    TomJc4({seq(i,i=0..3*n-1)},{}):

end:

TomJc4:=proc(S,F) local Big1,Allow1,S1,a,r,buddies,i,S2,F2,S3:

      Big1:=floor(max(op(S))-min(op(S))/3):

      if S={} then RETURN({{}}): fi:

      Allow1:={seq(i,i=1..Big1)} minus F:

      S1:={}:

      a:=min(op(S)):

      for i from 1 to nops(Allow1) do

          r:=Allow1[i]:

          buddies:={a,a+r,a+2*r,a+3*r}:

          if buddies subset S then

              S2:=S minus buddies:

              F2:=F union {r}:

              S3:=TomJc4(S2,F2):

              S1:=S1 union {seq({op(S3[j]),buddies}, j=1..nops(S3))}:

          fi:

      od:

      S1:

end:


-----