On 29/03/2015 02:22, Fred Lunnon wrote:
While pootling around the arcane labyrinth of multi-dimensional sodalite, I encountered a combinatorial puzzle which seems of independent interest, and reasonably straightforward --- more than can be said for numerous other heffalump-traps lately encountered over the course of that tortuous expedition!
Given n > 0 integer, evaluate the number f(n) of integer vectors P of length n such that 0 < P_(i+1) - P_i < n for all i , and (P_i - P_j) mod n /= 0 for all i /= j , and sum_i P_i = n(n-1)/2 .
For example when n = 4 there are f(4) = 6 such vectors: [ 0, 1, 2, 3 ], [ -1, 1, 2, 4 ], [ -2, 1, 3, 4 ], [ -1, 0, 2, 5 ], [ -2, 0, 3, 5 ], [ -3, 0, 3, 6 ].
The explicit function f(n) is surprisingly simple; but the proof is not immediately obvious.
I have one, obtained pretty much by doing the "most obvious" thing at each stage. I suspect that the following may not be easy to follow, for which I apologize. (It all seems very obvious to me, but this is the kind of thing where obviousness is not easily communicated.) The second condition says that P mod n is a permutation of {0,...,n-1} mod n. Let Q be the unique permutation of {0,...,n-1} all of whose entries agree mod n with P. Then the third condition says that the entries of R := P-Q (which are of course all multiples of n) add up to 0. The first condition says: consider adjacent entries a,b in Q and their corresponding entries u,v in R; then if a<b then u=v; otherwise v=u+n. Given Q, this nails down P completely *except* that we may change all its entries by the same multiple of n, changing the sum of R by an arbitrary multiple of n^2. There is clearly at most one such that makes the sum of R equal to 0; so f(n) is the number of Q for which there is in fact one such; equivalently, the number of Q for which a choice of P (*any* choice of P) has sum(R) a multiple of n^2. So, suppose we begin by taking P(n-1) = Q(n-1) and then working backwards according to the previous paragraph. It's easy to see that the resulting sum of R equals n times the sum of all the "decreasing positions" in Q; that is, the i such that Q(i) < Q(i-1). Hence, f(n) is the number of Q for which the sum of decreasing positions is a multiple of n. This is a simple enough condition that it's painless to compute f(n) for small n, and the result strongly suggests f(n) = (n-1)! when n>0. In other words, 1/n of all possible Q are acceptable. So maybe there's a simple operation that always increases the sum of decreasing positions by 1 mod n. And yes, there is. The operation in question is: decrease each entry in Q by 1 (mod n, so that 0 becomes n-1). To see that this does the trick, first of all consider the permutations to "wrap around", noting that the extra transition introduced between the first and last entries has index 0 (mod n) so that our "sum of decreasing positions" is unchanged mod n when we include it. And now note that when we decrease every entry in Q by 1 (mod n), the "decreasing positions" don't change *except* that where we previously had (say) a,0,b we now have a-1,n-1,b-1 and we have moved a "decreasing position" one place to the right and therefore changed the "sum of decreasing positions" by +1 mod n. And we're done. -- g