INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A17

A GENERALIZATION OF AN IMO PROBLEM

Alex Fink^{1}

Department of Mathematics and Statistics, University of Calgary, Calgary, Alberta, Canada

                           finka@math.ucalgary.ca

Received: 8/15/05, Revised: 5/2/06, Accepted: 5/12/06, Published: 5/17/06

Abstract

Bill Sands has conjectured that for no integer n ≥ 3 does there exist a vector of n integers whose dot products with all permutations of (1, …, n) form a complete residue system mod n!. In this paper we verify this conjecture when n + 1 is not prime, n = 4, and n = 6. We also suggest a generalization of the problem.

1. Introduction

In the 2001 International Mathematical Olympiad ([4, 1], or p. 118 of [3]), the following was posed as Problem 4. We have adapted the notation slightly.

Let n be an odd integer greater than 1, and let a_{1}, a_{2}, …, a_{n} be given integers.

For each of the n! permutations b = (b_{1}, b_{2}, …, b_{n}) of 1, 2, …, n, let

T (b) = ∑_{i=1}^{n} a_{i}b_{i}.

Prove that there are two permutations b and b′, b ≠ b′, such that n! is a divisor of T (b) − T (b′).

It will be convenient for our purposes to consider permutations of 0, 1, …, n − 1 rather than 1, 2, …, n; this makes no fundamental difference to the problem.

This problem was proposed by Bill Sands, who conjectures ([3], p. 143) that the result holds for all integers n > 2. It is clearly false for n = 1 and n = 2, with a_{1} = 0 and (a_{1}, a_{2}) = (0, 1), respectively, providing counterexamples.

1The author’s work was done while holding a NSERC Undergraduate Research Fellowship in 2003 and was supported by NSERC Discovery Grant #8306.

Our main result addresses a generalization of the above problem, verifying Sands’s conjecture for many more n > 2.

Theorem 1 Let n be a positive integer such that n + 1 is not prime, and let a_{1}, a_{2}, …, a_{n} be integers. There exist distinct permutations b and b′ of 0, 1, …, n − 1 for which

∑_{i=1}^{n} a_{i}b_{i} ≡ ∑_{i=1}^{n} a_{i}b′_{i} (mod n!).

In particular, Theorem 1 applies when n > 2 is odd, and so the IMO problem follows as a special case of this theorem.

We will call a vector a = (a_{1}, …, a_{n}) of integers nice (in the sense of “showing fine discrimination”) if there do not exist such permutations b ≠ b′, i.e. if

{a · b | b a permutation of {0, …, n − 1}}

is a complete set of residues modulo n!. Thus Theorem 1 asserts that there exist no nice vectors of length n, for n + 1 not prime.

In the next section, we present some preliminaries. We then present a proof of Theorem 1, followed by independent proofs that there are no nice vectors for the cases n = 4 and n = 6, which are the two smallest cases not covered by Theorem 1. Finally we comment on some open problems.

2. Preliminaries

Any nonzero rational q can be uniquely written as

q = ±t_{1}^{a_{1}}t_{2}^{a_{2}} … t_{k}^{a_{k}},

where t_{1}, t_{2}, …, t_{k} are distinct primes and each a_{i} is a nonzero integer. For a prime t_{i}, we define ord_{t_{i}}(q), the order of t_{i} in q, to be the exponent a_{i} of t_{i} in the above expression, or 0 if t_{i} does not appear. We also set ord_{t}(0) = ∞ for any prime t, and will adopt the usual arithmetical conventions regarding ∞, in particular: ∞ + ∞ = ∞ + n = ∞ and n < ∞ for all positive integers n. Then the following lemma is easy to prove.

Lemma 1 For any prime t and rationals q and r,

(a) ord_{t}(q ± r) ≥ min(ord_{t}(q), ord_{t}(r)), and equality holds if ord_{t}(q) ≠ ord_{t}(r);

(b) ord_{t}(qr) = ord_{t}(q) + ord_{t}(r);

The Bernoulli numbers B_{0}, B_{1}, B_{2}, … (e.g., see §6.5 of [2]) are rational numbers defined by the recurrence

B_{0} = 1,  ∑_{i=0}^{k−1} \binom{k}{i}B_{i} = 0 for k ≥ 2.

So B_{1} = −1/2, B_{2} = 1/6, B_{3} = 0, B_{4} = −1/30, etc. It is known (e.g., page 301 of [2]) that for t prime,

ord_{t}(B_{t−1}) = −1,  ord_{t}(B_{i}) ≥ 0 for all i < t − 1.  (1)

One of the most familiar properties of the Bernoulli numbers is that they satisfy

∑_{i=0}^{x−1} i^{t−1} = \frac{1}{t} ∑_{j=0}^{t−1} B_{j}\binom{t}{j}x^{t−j}  (2)

for all positive integers t. In particular, this demonstrates that the function

S_{t}(x) = ∑_{i=0}^{x−1} i^{t} = \frac{1}{t + 1} ∑_{j=0}^{t} B_{j}\binom{t + 1}{j}x^{t+1−j}

is a polynomial in x of degree t + 1 for each t ≥ 0.

Write [x^{j}]P (x) to denote the coefficient of x^{j} in the polynomial P (x).

Lemma 2 For any prime t and any integer j ≥ 0,

ord_{t}([x^{j}]S_{t−1}(x)) ≥ −1,

and

ord_{t}([x^{j}]S_{k−1}(x)) ≥ 0

for all integers k < t.

Proof. In case j = 0, it suffices to notice that [x^{0}]S_{t−1}(x) is the constant term of S_{t−1}(x) and is thus 0, so ord_{t}([x^{j}]S_{t−1}(x)) = ∞. So let j > 0 henceforth.

Since t is prime, t | \binom{t}{j} for 1 ≤ j ≤ t − 1. Hence, by (1) and Lemma 1(b), for any integer j ∈ [2, t − 1],

ord_{t}([x^{j}]S_{t−1}(x)) = ord_{t} (\frac{1}{t}B_{t−j}\binom{t}{t − j}) ≥ −1 + 0 + 1 = 0;

also

ord_{t}([x]S_{t−1}(x)) = ord_{t} (\frac{1}{t}B_{t−1}\binom{t}{t − 1}) = ord_{t}(B_{t−1}) = −1

and

ord_{t}([x^{t}]S_{t−1}(x)) = ord_{t} (\frac{1}{t}B_{0}\binom{t}{0}) = ord_{t}(\frac{1}{t}) = −1.

Also, for each integer k < t and each 1 ≤ j ≤ k, again by (1) and Lemma 1(b),

ord_{t}([x^{j}]S_{k−1}(x)) = ord_{t} (\frac{1}{k}B_{k−j}\binom{k}{k − j}) = ord_{t}(B_{k−j}) ≥ 0.

□

For positive integers m and t, define D_{m,t} to be the set of all t-tuples of distinct integers from 0, 1, …, m − 1. Let q = (q_{1}, q_{2}, …, q_{t}) be a t-tuple of positive integers, and define

s_{q}(m) = ∑_{b∈D_{m,t}} ∏_{i=1}^{t} b_{i}^{q_{i}},

where we write b = (b_{1}, b_{2}, …, b_{t}). Note that if m < t, then the sum is empty and s_{q}(m) = 0.

Lemma 3 For each fixed q, s_{q}(m) is a polynomial in m, with (m − k) as a factor for each k = 0, 1, …, t − 1.

We present two proofs of Lemma 3.

First proof. We will expand the sum s_{q}(m) with a general form of the inclusion-exclusion principle. Consider the statements h_{j} = h_{k} for each 1 ≤ j < k ≤ t. Call the set of all such statements P. The sum can then be written as

s_{q}(m) = ∑_{P′⊆P}(−1)^{|P′|} ∑_{h⊧P′} ∏_{i=1}^{t} h_{i}^{q_{i}},

where, for any P′ ⊆ P, h ⊧ P′ means that the sum ranges over all t-tuples h = (h_{1}, h_{2}, …, h_{t}) of integers from [0, m − 1] for which every member of P′ is true. Now, to each such subset P′ there corresponds a graph G on {1, 2, …, t} defined as follows: the edge {j, k} is in G if and only if the statement h_{j} = h_{k} is in P′. Then for any j and k, h_{j} and h_{k} are forced to be equal in the inner sum if and only if vertices j and k are in the same component of G. Let C_{G,1}, C_{G,2}, …, C_{G,s_{G}} denote the components of G, and let Q_{i} denote the sum ∑_{j∈C_{G,i}} q_{j}. Then s_{q}(m) can be rewritten

s_{q}(m) = ∑_{G}(−1)^{e(G)} ∑_{h} ∏_{i=1}^{s_{G}} h_{i}^{Q_{i}},

where, for each G, h ranges over all s_{G}-tuples of integers from [0, m − 1], and where e(G) is the number of edges of G. Now, the term inside the rightmost sum is a product of powers of independent variables, so we can switch the sum and the product, obtaining

s_{q}(m) = ∑_{G}(−1)^{e(G)} ∏_{i=1}^{s_{G}} ∑_{k=0}^{m−1} k^{Q_{i}} = ∑_{G}(−1)^{e(G)} ∏_{i=1}^{s_{G}} S_{Q_{i}}(m).  (3)

But S_{Q_{i}}(m) is a polynomial in m. Furthermore, s_{G} ≤ |G| = t, and the number of graphs G is at most 2^{|P |} = 2^{\binom{t}{2}}, both bounded for fixed q. So, since s_{q}(m) is a sum of products of polynomials in m, we conclude that it can also be expressed as a polynomial in m.

Since s_{q}(m) = 0 when m < t, as a polynomial s_{q}(m) must have the factor m(m − 1) ⋯ (m − t + 1). □

Second proof. We will show inductively on t that s_{q}(m) can be expressed as a polynomial in m. When t = 1, s_{q}(m) = S_{q_{1}}(m), which is a polynomial in m.

Suppose t > 1. Let q′ = (q_{1}, q_{2}, …, q_{t−1}), and for each 1 ≤ i ≤ t − 1, let q_{i} = (q_{1}, q_{2}, …, q_{i−1}, q_{i} + q_{t}, q_{i+1}, …, q_{t−1}). Then we can write

s_{q}(m) = (∑_{i=0}^{m−1} i^{q_{t}}) s_{q′}(m) − ∑_{i=1}^{t−1} s_{q_{i}}(m) = S_{q_{t}}(m)s_{q′}(m) − ∑_{i=1}^{t−1} s_{q_{i}}(m).

This equation holds even if m < t. S_{q_{t}}(m) is a polynomial in m, and inductively s_{q′}(m) and s_{q_{i}}(m) for each i are polynomials in m. Thus so is s_{q}(m).

Again s_{q}(m) = 0 when 0 ≤ m < t, so s_{q}(m) must have the given factors. □

3. Proof of Theorem 1

Let n > 2 be an integer with n+1 not prime. Towards a contradiction, let a = (a_{1}, a_{2}, …, a_{n}) be a nice vector. Then as b = (b_{1}, …, b_{n}) ranges over all permutations of 0, 1, …, n − 1 (i.e. over the elements of D_{n,n}),

T (b) = ∑_{i=1}^{n} a_{i}b_{i}

takes on a value congruent to each of the integers 0, 1, …, n! − 1 at most once. Since |D_{n,n}| = n!, T (b) must take on a value congruent to each of 0, 1, …, n! − 1 exactly once.

Our condition on n guarantees that we may choose a prime p < n for which n ≡ −1 (mod p). Then T (b)^{p−1} is congruent to each of 0^{p−1}, 1^{p−1}, …, (n! − 1)^{p−1} mod n! as b ranges over the elements of D_{n,n}. So

L := ∑_{b∈D_{n,n}} (∑_{i=1}^{n} a_{i}b_{i})^{p−1}

must be congruent modulo n! to

R := ∑_{i=0}^{n!−1} i^{p−1} = S_{p−1}(n!).

By the multinomial theorem,

L = ∑_{b∈D_{n,n}} ∑_{q} \binom{p − 1}{q_{1} q_{2} ⋯ q_{n}} ∏_{j=1}^{n}(a_{j}b_{j})^{q_{j}}

= ∑_{b∈D_{n,n}} ∑_{q} \binom{p − 1}{q_{1} q_{2} ⋯ q_{n}} ∏_{j=1}^{n} a_{j}^{q_{j}} ∏_{j=1}^{n} b_{j}^{q_{j}}

= ∑_{q} \binom{p − 1}{q_{1} q_{2} ⋯ q_{n}} (∏_{j=1}^{n} a_{j}^{q_{j}}) ∑_{b∈D_{n,n}} ∏_{j=1}^{n} b_{j}^{q_{j}}.

as q ranges over every n-tuple of non-negative integers (q_{1}, q_{2}, …, q_{n}) satisfying ∑_{i=1}^{n} q_{i} = p − 1.

For any such q, let t_{q} be the number of its components which are nonzero. For any given permutation c = (c_{1}, c_{2}, …, c_{n}) of the integers 0, 1, …, n − 1, consider the set of all permutations b = (b_{1}, b_{2}, …, b_{n}) such that b_{i} = c_{i} for all i such that q_{i} is nonzero. There will be (n − t_{q})! such permutations b, and for each of these permutations the product ∏_{j=1}^{n} b_{j}^{q_{j}} will take the same value. Therefore, we can write

L = ∑_{q} \binom{p − 1}{q_{1} q_{2} ⋯ q_{n}} (∏_{j=1}^{n} a_{j}^{q_{j}}) (n − t_{q})! ∑_{b∈D_{n,tq}} ∏_{j=1}^{t_{q}} b_{j}^{q′_{j}}

= ∑_{q} \binom{p − 1}{q_{1} q_{2} ⋯ q_{n}} (∏_{j=1}^{n} a_{j}^{q_{j}}) (n − t_{q})!s_{q′}(n).

where q′ = (q′_{1}, q′_{2}, …, q′_{t_{q}}) is obtained from q by deleting all of the zero components. Note that ∑_{i=1}^{t_{q}} q′_{i} = ∑_{i=1}^{n} q_{i} = p − 1.

By (3), for any integer m, s_{q′}(m) can be expressed as a sum of products of the form S_{i_{1}}(m) … S_{i_{k}}(m), with ∑_{j=1}^{k} i_{j} = p − 1. In each such product, no i_{j} > p − 1, and at most one i_{j} = p−1. Thus, by Lemma 2, the order of p in the coefficients of each S_{i} is at least 0, with one possible exception, where it may be −1. So if S(x) is any of these products above, then for any integer a, ord_{p}([x^{a}]S(x)) ≥ −1 by Lemma 1(b), and consequently ord_{p}([x^{a}]s_{q′}(x)) ≥ −1 by Lemma 1(a). Since this holds for any q′, we can choose a positive integer h such that for any q′, hs_{q′}(x) has integer coefficients, and that p^{2} ∤ h; we can further require that p! | h, so that in particular ord_{p}(h) = 1.

By Lemma 3, we may define the polynomial

s′_{q′}(m) = \frac{s_{q′}(m)}{m(m − 1) ⋯ (m − t_{q} + 1)}

for any t_{q}-tuple q′ of positive integers. We then set

σ = ∑_{q} \binom{p − 1}{q_{1} q_{2} ⋯ q_{n}} (∏_{j=1}^{n} a_{j}^{q_{j}}) hs′_{q′}(n), ,  (4)

where the sum ranges over all n-tuples q = (q_{1}, …, q_{n}) with sum p − 1, so that L = σ · n!/h. Now,

hs′_{q′}(p − 1) = \frac{hs_{q′}(p − 1)}{(p − 1)(p − 2) … (p − t_{q})}
= p · s_{q′}(p − 1) · (\frac{h}{p(p − 1)(p − 2) … (p − t_{q})}) .

Since the second and third factors of the last expression are both integers (in the latter case, by choice of h), we see that p | hs′_{q′}(p − 1). But hs_{q′} is a polynomial with integer coefficients by our choice of h, so recalling the definition of s′_{q′}, hs′_{q′} must also be a polynomial with integer coefficients. Consequently, the congruence class of hs′_{q′}(m) modulo p depends only on the congruence class of m mod p. In particular, since p | hs′_{q′}(p − 1) and n ≡ −1 (mod p), p | hs′_{q′}(n). This holds for arbitrary q′, which means that p divides each term under the summation in (4), so p | σ, that is, there is an integer f for which σ = pf. Then L = n!pf/h.

We now turn our attention to R. From (2), x is a factor of S_{t}(x) and S_{t}(x)/x is a polynomial. Letting S′_{p−1}(m) = S_{p−1}(m)/m, we have by (2) that

S′_{p−1}(n!) = \frac{S_{p−1}(n!)}{n!} = \frac{1}{n!p} ∑_{j=0}^{p−1} B_{j}\binom{p}{j}(n!)^{p−j}

= \frac{(n!)^{p−1}}{p} + ∑_{j=1}^{p−2} \frac{1}{p}\binom{p}{j}B_{j}(n!)^{p−1−j} + B_{p−1}.

But note that p | n! (since p < n), and by (1) ord_{p}(B_{j}) ≥ 0 for j < p − 1, ord_{p}(B_{p−1}) = −1, thus ord_{p}(S′_{p−1}(n!)) = −1 by Lemma 1(a). Because ord_{p}(h) = 1 we then have that ord_{p}(hS′_{p−1}(n!)) = 0 by Lemma 1(b). Therefore we can write

R = S_{p−1}(n!) = \frac{n!}{h} · hS′_{p−1}(n!) = \frac{n!}{h} · k

for rational k such that ord_{p}(k) = 0.

Finally, because we have assumed L and R to be congruent modulo n!, we must have L − R = n!d for some integer d. However, hd = h(L − R)/n! = pf − k, so k = pf − hd. In particular, k is integral. But p | h, while p ∤ k, a contradiction. This completes the proof. □

4. Two other cases

The following lemmas will be convenient to reduce the number of cases in the treatment of other values of n.

Lemma 4 Suppose that a = (a_{1}, …, a_{n}) is nice. Then:

(a) any rearrangement of a is nice;

(b) for any integer k, a + k = (a_{1} + k, …, a_{n} + k) is nice; and

(c) for any integer k with (k, n!) = 1, ka = (ka_{1}, …, ka_{n}) is nice.

Proof. Part (a) is easy to prove. For part (b), we have

∑_{i=1}^{n}(a_{i} + k)b_{i} = ∑_{i=1}^{n} a_{i}b_{i} + ∑_{i=1}^{n} kb_{i} = ∑_{i=1}^{n} a_{i}b_{i} + \frac{1}{2}n(n + 1)k.

The map ϕ(x) = x + \frac{1}{2}n(n + 1)k is a bijection on the integers mod n!, so this expression takes each value mod n! exactly once. This proves part (b). Similarly, when (k, n!) = 1,

∑_{i=1}^{n}(ka_{i})b_{i} = k ∑_{i=1}^{n} a_{i}b_{i}.

As ϕ′(x) = kx is a bijection on the integers mod n!, this takes on every value mod n! exactly once, proving part (c). □

Recall that in the last section, we defined

T (b) = ∑_{i=1}^{n} a_{i}b_{i}

where b = (b_{1}, …, b_{n}) is a permutation of 0, …, n − 1.

Lemma 5 Let a = (a_{1}, …, a_{n}) be nice.

(a) Let m | n!. As b varies over all permutations of 0, …, n − 1, T (b) takes a value in each congruence class mod m exactly n!/m times.

(b) If n is even, then ∑ a_{i} is odd.

Proof. Part (a) follows easily from the observations that, modulo n!, T (a) will be congruent to each integer [0, n! − 1] exactly once, and that each congruence class mod m is a union of n!/m classes mod n!.

As for part (b), let S_{a} = ∑ T (b) as b ranges over all permutations of 0, …, n − 1. Then, modulo n!,

S_{a} ≡ ∑_{i=0}^{n!−1} i = \frac{n!(n! − 1)}{2} ≡ \frac{n!}{2}.

However, for any given integer 0 ≤ k ≤ n − 1 and any index 1 ≤ i ≤ n, b_{i} = k holds of just (n−1)! different permutations b. So if we consider the expansions of the n! summands T (b), we see that a_{i} occurs multiplied by k in exactly (n − 1)! of the summands, corresponding to those permutations b such that b_{i} = k. Hence, S_{a} can also be written (mod n!) as

S_{a} = ∑_{i=1}^{n} a_{i} · (n − 1)! ∑_{k=0}^{n−1} k = \frac{(n − 1)!n(n − 1)}{2} ∑_{i=1}^{n} a_{i} = \frac{n!(n − 1)}{2} ∑_{i=1}^{n} a_{i}.

So n!/2 ≡ n!/2 ∑ a_{i} (mod n!), and thus ∑ a_{i} must be odd. □

In the upcoming proofs, congruence of vectors is to be interpreted componentwise. That is,

(a_{1}, …, a_{n}) ≡ (b_{1}, …, b_{n}) (mod t)

if and only if a_{i} ≡ b_{i} (mod t) for all i.

We now handle the case n = 4, for which Sands also had a proof ([3], p. 143).

Theorem 2 There exist no nice vectors of length n = 4.

Proof. Suppose that a = (a_{1}, a_{2}, a_{3}, a_{4}) were nice. By Lemma 5(b), the sum of the components of a is odd, so the number of odd components of a is either 1 or 3. If it is 1, then (a_{1} + 1, …, a_{4} + 1) is a solution with three odd components by Lemma 4(b). So we may assume that a has three odd components. By Lemma 4(a), we can assume without loss of generality that a ≡ (0, 1, 1, 1) mod 2.

Go on to consider a mod 8. Of the three odd components of a, either two are congruent mod 8 or not. Suppose two of the components of a are congruent mod 8, and, without loss of generality, that these are a_{2} and a_{3}. Then the permutations b = (1, 0, 3, 2) and b′ = (1, 3, 0, 2) achieve

T (b) − T (b′) = ∑_{i=1}^{4} a_{i}b_{i} − ∑_{i=1}^{4} a_{i}b′_{i} = 3(a_{3} − a_{2}).

Since 8 | (a_{3} − a_{2}), it follows that T (b) ≡ T (b′) (mod 24), which contradicts that a is nice.

So we can assume that all of the odd components of a are distinct mod 8. Using Lemma 4 to multiply by an odd integer, and rearranging if necessary, it suffices to consider a congruent to (0, 1, 5, 3) mod 8.

So assume a ≡ (0, 1, 5, 3) (mod 8). In this case, we count the permutations b of 0, 1, 2, 3 for which T (b) ≡ 2 (mod 8). Examining the 24 cases, we find that the only such permutations are (2, 0, 3, 1) and (2, 1, 0, 3); since there are fewer than three of these, this case is impossible, by Lemma 5(a). This completes the proof. □

Finally, we examine the case n = 6.

Theorem 3 There exist no nice vectors of length n = 6.

Proof. Suppose that a = (a_{1}, ⋯, a_{6}) were nice. By Lemma 5(b), we know that ∑ a_{i} is odd. By Lemma 4, we may assume without loss of generality that a is congruent to either (0, 1, 1, 1, 1, 1) or (0, 0, 0, 1, 1, 1) mod 2 (analogously to the case n = 4).

Now, consider a mod 4. If a is congruent to (0, 1, 1, 1, 1, 1) mod 2, then by Lemma 4, we can assume that the even element of a is congruent to 0 mod 4 by adding 2 to a if necessary; also, by possibly multiplying by −1 we can assume that a has more elements congruent to 1 than to 3 mod 4. We then need to consider only the cases in which a is congruent to

(0, 1, 1, 1, 1, 1), (0, 1, 1, 1, 1, 3), and (0, 1, 1, 1, 3, 3) mod 4.

If a is congruent to (0, 0, 0, 1, 1, 1) mod 2, then we can assume that there there are more elements of a congruent to 0 mod 4 than to 2, and more congruent to 1 mod 4 than to 3. Furthermore, if a = (0, 0, 2, 1, 1, 1), the nice vector −a+1 will be congruent to (0, 0, 0, 1, 1, 3) mod 4. So we must also consider the cases in which a is congruent to

(0, 0, 0, 1, 1, 1), (0, 0, 0, 1, 1, 3), and (0, 0, 2, 1, 1, 3) mod 4.

Altogether, we have six cases to consider. For most of the cases, we will need the fact, from Lemma 5(a), that we must have 6!/4 = 180 values of T (b) in each congruence class mod 4.

Case (i): a ≡ (0, 1, 1, 1, 1, 1)

For any permutation b, there are 5! = 120 permutations (including b) with the same first component, and the values of T (b) for each of these values of b are congruent mod 4. Therefore, 120 divides the number of values of T (b) in any congruence class mod 4. But 120 ∤ 180, so there cannot be equally many values in each congruence class, and we can reject this case.

Case (ii): a ≡ (0, 1, 1, 1, 1, 3)

Similarly to case (i), we obtain sets of 4! = 24 permutations b for which the values of T (b) are congruent mod 4, and 24 ∤ 180, so we can reject this case as well.

Case (iii): a ≡ (0, 1, 1, 1, 3, 3)

Consider the equivalence relation ∼ under which two permutations b = (b_{1}, …, b_{6}) and b′ = (b′_{1}, …, b′_{6}) satisfy b ∼ b′ iff {b_{2}, b_{3}, b_{4}} = {b′_{2}, b′_{3}, b′_{4}} and {b_{5}, b_{6}} = {b′_{5}, b′_{6}}. Note that when b ∼ b′, we will obtain T (b) ≡ T (b′). Each equivalence class of ∼ has size 3!2! = 12. Thus, it suffices to consider one representative of each equivalence class and ascertain whether we obtain 180/12 = 15 values of T (b) in each congruence class mod 4.

We will count the vectors b for which T (b) ≡ −1 (mod 4). Observe that

T (b) ≡ ∑_{i=1}^{6} b_{i} + 2(b_{5} + b_{6}) − b_{1} ≡ −1 + 2(b_{5} + b_{6}) − b_{1}.

Consequently 2(b_{5} + b_{6}) − b_{1} ≡ 0 (mod 4) and b_{1} ≡ 0 (mod 2). In the case that b_{1} is either 0 or 4, we then have 2(b_{5} + b_{6}) ≡ 0 (mod 4), so b_{5} + b_{6} ≡ 0 (mod 2), implying b_{5} and b_{6} have the same parity. Of the components b_{2}, …, b_{6}, two are even and three are odd, so there are four choices of b_{5} and b_{6}. If b_{1} is 2, we have 2(b_{5} + b_{6}) ≡ 2 (mod 4), so b_{5} + b_{6} ≡ 1 (mod 2), so b_{5} and b_{6} are of opposite parity. Since there remain two even and three odd bs, this can be done in 6 ways. Altogether, we have 4 + 4 + 6 = 14 vectors, not the 15 we needed, ruling out the case a ≡ (0, 1, 1, 1, 3, 3).

Case (iv): a ≡ (0, 0, 0, 1, 1, 3)

The permutations b can be placed in classes of size 3!2! = 12 analogous to the classes of the last case. We count vectors b, disregarding the order of b_{1}, b_{2}, b_{3} and of b_{4}, b_{5}, for which T (b) ≡ b_{4} + b_{5} − b_{6} ≡ 0 (mod 4). This requires that b_{4} + b_{5} − b_{6} ≡ 0 (mod 2), so b_{4}, b_{5}, and b_{6} either are all even or else consist of one even and two odd integers. If they are all even, they must be 0, 2, and 4, and it can be seen that this yields no solution to b_{4} + b_{5} − b_{6} ≡ 0 (mod 4). Suppose now that b_{4} and b_{5} are odd, and wlog b_{4} < b_{5}. Then we get 5 solutions, as tabulated here:

Number of

b_{4} b_{5} b_{6} solutions
1 3 0, 4  2
1 5 2  1
3 5 0, 4  2

Otherwise, exactly one of b_{4} and b_{5}, say b_{4}, is odd, as is b_{6}. This yields 8 solutions:

Number of

b_{4} b_{6} b_{5} solutions
1 5 0, 4  2
5 1 0, 4  2
1 3 2  1
3 1 2  1
3 5 2  1
5 3 2  1

We obtain 13 solutions in total, not 15, so we have shown it impossible that a ≡ (0, 0, 0, 1, 1, 3).

Case (v): a ≡ (0, 0, 2, 1, 1, 3)

For this value of a our equivalence classes of bs have size 2!2! = 4, and for each congruence class of T (b) mod 4 we will require 180/4 = 45 vectors b. We want T (b) ≡ 2b_{3}+b_{4}+b_{5}−b_{6} ≡ 0 (mod 4). First, note that when b_{3} is even, this reduces to the case b_{4} +b_{5} −b_{6} ≡ 0 (mod 4), whose solutions we counted in the discussion of case (iv). Since we found 13 solutions then, and each of them had two even numbers among b_{1}, b_{2}, and b_{3}, we obtain 26 solutions in this case. Now suppose b_{3} is odd. We then require b_{4} + b_{5} − b_{6} ≡ 2 (mod 4). We will again tabulate the possible solutions. If b_{4}, b_{5}, and b_{6} are all even, we assume that b_{4} < b_{5}; then we have 9 solutions:

Number of

b_{4} b_{5} b_{6} b_{3}  solutions
0 2 4 1,3,5  3
0 4 2 1,3,5  3
2 4 0 1,3,5  3

If two of b_{4}, b_{5}, and b_{6} are odd, still assuming that b_{4} < b_{5} we have 14 solutions:

Number of

b_{4} b_{5} (b_{6}, b_{3})  solutions
0 1 (3,5) 1
0 3 (1,5), (5,1)  2
0 5  (3,1)  1
1 2  (5,3)  1
1 3  (2,5)  1
1 4  (3,5)  1
1 5 (0,3), (4,3)  2
2 3  0
2 5 (1,3) 1
3 4 (1,5), (5,1)  2
3 5  (2,1)  1
4 5  (3,1)  1

Altogether we have 26 + 9 + 14 = 49 possible vectors, and not 45, showing that a ≡ (0, 0, 2, 1, 1, 3) is impossible.

Case (vi): a ≡ (0, 0, 0, 1, 1, 1)

We will examine this case mod 8. Of the three components congruent to 0 mod 4 in a, at least two must be congruent mod 8, and of the three components congruent to 1 mod 4, at least two must also be congruent mod 8. Suppose without loss of generality that a_{1} ≡ a_{2} and a_{4} ≡ a_{5} mod 8. Then, we can place the permutations b into classes of size 2!2! = 4, such that two vectors within one class differ only in a possible exchange of b_{1} and b_{2}, or of b_{4} and b_{5}, or both. Two vectors b in the same class yield congruent values of T (b) mod 8. Thus the number of values of T (b) in any given congruence class mod 8 is divisible by 4. Yet there should be 6!/8 = 90 values in each congruence class by Lemma 5(a), and 4 ∤ 90. Thus, this case as well is impossible.

We have now reached a contradiction in every case, and the proof is finished. □

5. Open problems

The least values of n for which the result of Theorem 1 is unknown are n = 10 and n = 12. It is likely that a proof for any particular one of the unknown cases, along the lines of that for n = 6 above, could be found, but a general technique is still lacking.

Here is another open problem. Instead of requiring the vectors b, b′ as in Theorem 1 to be permutations of 0, …, n − 1, let them be permutations of any fixed multiset S of n integers.

Problem. Characterise the multisets S such that for every vector a of length n = |S|, there do not exist distinct permutations b, b′ of S such that

a · b ≡ a · b′ (mod n!).

We will present some basic observations on this problem, including its solution for n ≤ 3.

We shall say that a vector a is nice for S if {a · b|b a permutation of S} is a complete set of residues modulo n!; we shall also say that a multiset S of size n allows nice vectors if there exists some a that is nice for S. Then the above problem asks for all multisets S which allow nice vectors.

There is a sort of symmetry in this problem between a and S. Given a and S, let S′ be the multiset of all components of a and a′ the vector of all elements of S. Let S = {s_{1}, …, s_{n}}, and S′ = {s′_{1}, …, s′_{n}}. Any permutation b of S can be written (s_{σ(1)}, …, s_{σ(n)}), where σ is a permutation of {1, …, n}; if we then let b′ = (s′_{σ^{−1}(1)}, …, s′_{σ^{−1}(n)}), it is easy to confirm that a · b = a′ · b′. This establishes a bijection between the permutations of S and those of S′. In particular, if a is nice for S, then a′ is nice for S′.

As this symmetry might suggest, an analogue of Lemma 4 holds in this new problem in which a is replaced by S. The more direct analogue of Lemma 4 continues to hold as well. We won’t prove this statement here.

We will now consider particular values of n, starting with n = 1. Any multiset S of size 1 allows nice vectors. Indeed, if |S| = 1, there is only one possible permutation of S, so any vector a is vacuously nice.

For |S| = 2, if S has two elements of the same parity, it is clear that a · b has the same parity for either permutation b of S, so that S does not allow nice vectors. Otherwise, the multiset S has one even and one odd element. Then S must be congruent mod 2 to {0, 1}, and this problem reduces to our main problem. In particular, S allows nice vectors.

However, we claim that no multiset S with |S| = 3 allows nice vectors. Let S = {s_{1}, s_{2}, s_{3}}. We consider two cases, according as whether S contains two elements congruent modulo 3.

Suppose, without loss of generality, that s_{1} ≡ s_{2} (mod 3). There must exist two components of a = (a_{1}, a_{2}, a_{3}), say a_{1} and a_{2}, which are congruent mod 2. Then it is easily seen that for b = (s_{1}, s_{2}, s_{3}) and b′ = (s_{2}, s_{1}, s_{3}), T (b) ≡ T (b′) (mod 3!). So S does not allow nice vectors.

Now assume S has no two elements congruent modulo 3. S is congruent mod 6 to either {k, k + 1, k + 2} or {k, k + 2, k + 4} for some integer k, as we can see by examining all eight possibilities for S mod 6. Assume that a is nice for S. By the analogue of Lemma 4 for S that we mentioned above, a is then also nice for either {0, 1, 2} or {0, 2, 4}. But the first of these cases is our main problem, and we have seen that {0, 1, 2} does not allow nice vectors. As for S = {0, 2, 4}, a · b must be even for any permutation b of S, so {0, 2, 4} does not allow nice vectors either. This verifies our claim.

Thus it remains to be resolved: Are there any multisets S of size at least 4 which allow nice vectors?

Acknowledgements

I would like to thank Bill Sands, my supervisor for the NSERC USRA Fellowship, under which this work was done, for his support, and in particular his many helpful suggestions regarding this paper. I also thank Richard Guy for suggesting the terminology “nice”.

References

[1] Titu Andreescu and Zuming Feng, USA and International Mathematical Olympiads 2001, Mathematical Association of America, 2002.

[2] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 1989.

[3] A. M. Storozhev, J. B. Henry, and A. Di Pasquale. Mathematics Contests 2001: The Australian Scene, Australian Mathematics Trust, 2001.

[4] The Official Scoring Site of the International Mathematical Olympiad 2001. http://imo.wolfram.com/. Retrieved July 25, 2004.