For each positive integer $n$, let $S_{n}$ be the set that contains the integers from 1 to $n$, inclusive; that is, $S_{n}=\{1,2,3, \ldots, n\}$.

For each positive integer $n \geq 4$, let $f(n)$ be the number of quadruples $(a, b, c, d)$ of distinct integers from $S_{n}$ for which $a-b=c-d$.

For example, $f(4)=8$ because the possibilities for $(a, b, c, d)$ are

$(1,2,3,4),(1,3,2,4),(2,1,4,3),(2,4,1,3),(3,1,4,2),(3,4,1,2),(4,2,3,1),(4,3,2,1)$

(a) Determine the value of $f(6)$.

(b) Determine the value of $f(40)$.

(c) Determine two even positive integers $n<2022$ for which 2022 is a divisor of $f(n)$.
(a) We note that if $(a, b, c, d)=(A, B, C, D)$ satisfies the equation $a-b=c-d$ (that is, if $A-B=C-D)$, then so do $(a, b, c, d)=(B, A, D, C)$ and $(a, b, c, d)=(C, D, A, B)$ and $(a, b, c, d)=(D, C, B, A)$ since

$$
B-A=D-C \quad C-D=A-B \quad D-C=B-A
$$

Let $g(n)$ be the number of quadruples $(a, b, c, d)$ of distinct integers from $S_{n}$ for which $a-b=c-d$ with $ab$ and $c>d$ (because $a-b=c-d$ and so the signs of $a-b$ and $c-d$ are the same) and has either $ac$ (because $a \neq c$ ).

Therefore, the quadruples counted by $f(n)$ can be grouped into sets of four quadruples exactly one of which satisfies $ac$.

This gives us two cases for the ordering of $a, b, c, d$ : first that $ab$ in both cases because the "gap" between $a$ and $b$ is equal to the gap between $c$ and $d$.

Case 1: $ad-c+b-a=2 t$ and $d-a \leq 2 m-1$, then $2 t \leq 2 m-1$, which means that $t \leq m-\frac{1}{2}$. Since $t$ and $m$ are integers, then $t \leq m-1$.

We count the number of quadruples $(a, b, c, d)$ with $a<b<c<d$ for each value of $t$ from 1 to $m-1$, inclusive.

Suppose that $t=1$.

Here, $b=a+1$ and the pair $(c, d)$ can be as small as $(a+2, a+3)$ and as large as $(2 m-1,2 m)$.

For the pair $(a, b)=(a, a+1)$, there are $2 m-(a+3)+1=2 m-a-2$ pairs $(c, d)$.

Since $a$ can range from $a=1$ to $a=2 m-3$ (the latter of which gives the quadruple $(2 m-3,2 m-2,2 m-1,2 m))$, there is a total of

$$
(2 m-3)+(2 m-4)+\cdots+2+1=\frac{1}{2}(2 m-3)(2 m-2)
$$

quadruples $(a, b, c, d)$ in the case $t=1$.

More generally, suppose that $1 \leq t \leq m-1$.

Here, $b=a+t$ and the pair $(c, d)$ can be as small as $(a+t+1, a+2 t+1)$ and as large as $(2 m-t, 2 m)$.

For the pair $(a, b)=(a, a+t)$, there are thus $2 m-(a+2 t+1)+1=2 m-a-2 t$ pairs $(c, d)$.

Since $a$ can range from $a=1$ to $a=2 m-2 t-1$ (the latter of which gives the quadruple $(2 m-2 t-1,2 m-t-1,2 m-t, 2 m))$, there is a total of

$$
(2 m-2 t-1)+(2 m-2 t-2)+\cdots+2+1=\frac{1}{2}(2 m-2 t-1)(2 m-2 t)
$$

quadruples $(a, b, c, d)$ for each $t$ with $1 \leq t \leq m-1$.

We note that

$$
\begin{aligned}
\frac{1}{2}(2 m-2 t-1)(2 m-2 t) & =(2 m-2 t-1)(m-t) \\
& =2 m^{2}-2 m t-2 m t+2 t^{2}-m+t \\
& =2 t^{2}+t(-4 m+1)+\left(2 m^{2}-m\right)
\end{aligned}
$$

From the Useful Fact, when we add $2 t^{2}$ for each $t$ from 1 to $m-1$, we obtain $2 \cdot \frac{(m-1) m(2 m-1)}{6}$.

Adding $t(-4 m+1)$ for each $t$ from 1 to $m-1$ is equivalent to multiplying $(-4 m+1)$ by the sum of the integers from 1 to $m-1$, which gives $(-4 m+1) \cdot \frac{1}{2}(m-1) m$.

Adding $\left(2 m^{2}-m\right)$ for each $t$ from 1 to $m-1$ gives $(m-1)\left(2 m^{2}-m\right)$.

Adding these partial sums together, we obtain the total number of triples in this case, which is

$$
\begin{aligned}
& 2 \cdot \frac{(m-1)}{} \frac{m(2 m-1)}{6}+(-4 m+1) \cdot \frac{1}{2}(m-1) m+(m-1)\left(2 m^{2}-m\right) \\
&=m(m-1)\left(\frac{2 m-1}{3}+\frac{-4 m+1}{2}+(2 m-1)\right) \\
&\left.=m(m-1)\left(\frac{4 m-2}{6}+\frac{-12 m+3}{6}+\frac{12 m-6}{6}\right)\right) \\
&=m(m-1) \cdot \frac{4 m-5}{6}
\end{aligned}
$$

Case 2: $a<c<b<d$

Suppose that $b-a=d-c=t$ for some positive integer $t$.

Since $2 m \geq d \geq b+1$, then $t=b-a \leq 2 m-1-1=2 m-2$. Since $a<c<b$, then $b \geq a+2$, which means that $t \geq 2$.

Thus, the range of values for $t$ is $2 \leq t \leq 2 m-1$.

For each pair of values $(a, b)$, the value of $c$ can, in theory, move between $a+1$ and $b-1$ with the restriction that $d=c+t$ must still be at most $2 m$.

Our strategy is to work through the possible values of $t$, in each case starting with $a=1$ to establish the possible quadruples in this case when $a=1$, and then count the number of ways these relative positions for $(a, b, c, d)$ can be slid until $d$ reaches $2 m$.

Suppose that $t=2$ and $a=1$. Here, $b=a+t=3$. Since $a<c<b$, then $c=2$ which gives $d=4$.

The base quadruple $(a, b, c, d)=(1,3,2,4)$ can have each component increased by 1 until we obtain the largest possible quadruple with this relative positioning, which is $(a, b, c, d)=(2 m-3,2 m-1,2 m-2,2 m)$.

There are $2 m-4+1=2 m-3$ quadruples in this case.

Suppose that $t=3$ and $a=1$. Here, $b=4$ and so $c=2$ or $c=3$.

This gives the base quadruples $(a, b, c, d)=(1,4,2,5)$ and $(a, b, c, d)=(1,4,3,6)$.

There are $2 m-4$ and $2 m-5$ possible quadruples of these two forms.

Next, consider a general value of $t$ with $2 \leq t \leq m$, along with $a=1$.

Here, $b=t+1$ and so $2 \leq c \leq t$.

This gives the base quadruples $(a, b, c, d)=(1, t+1, c, c+t)$ for $2 \leq c \leq m$.

For each of these values of $c$, the corresponding value of $d$ satisfies $d \leq 2 m$, since $d=c+t \leq m+m=2 m$.

For a given value of $c$, there are $2 m-(c+t)+1=2 m-c-t+1$ such quadruples.

As $c$ increases from 2 to $t$, we see that there are

$$
(2 m-t-1)+(2 m-t-2)+\cdots+(2 m-2 t+2)+(2 m-2 t+1)
$$

quadruples. There are $t-1$ terms in this sum.

This sum can be re-written as

$$
\begin{aligned}
&(2 m-t-1)+(2 m-t-2)+\cdots+(2 m-2 t+2)+(2 m-2 t+1) \\
&=((2 m-2 t)+(t-1))+((2 m-2 t)+(t-2))+\cdots+((2 m-2 t)+2)+((2 m-2 t)+1) \\
& \quad=(t-1)(2 m-2 t)+(1+2+\cdots+(t-2)+(t-1)) \\
& \quad=(t-1)(2 m-2 t)+\frac{1}{2} t(t-1) \\
& \quad=2 m t-2 t^{2}-2 m+2 t+\frac{1}{2} t^{2}-\frac{1}{2} t \\
& \quad=-\frac{3}{2} t^{2}+t\left(2 m+\frac{3}{2}\right)-2 m
\end{aligned}
$$

When $t=1$, this expression is equal to 0 .

Thus, we can add these expressions for $t=1$ to $t=m$ and obtain the same sum as adding from $t=2$ to $t=m$.

This sum is thus

$$
\begin{aligned}
-\frac{3}{2}\left(1^{2}\right. & \left.+2^{2}+\cdots+m^{2}\right)+(1+2+\cdots+m)\left(2 m+\frac{3}{2}\right)-2 m \cdot m \\
& =-\frac{3}{2} \cdot \frac{m(m+1)(2 m+1)}{6}+\frac{4 m+3}{2} \cdot \frac{m(m+1)}{2}-2 m^{2} \\
& =-\frac{m(m+1)(2 m+1)}{4}+\frac{m(m+1)(4 m+3)}{4}-2 m^{2} \\
& =\frac{m(m+1)(2 m+2)}{4}-2 m^{2} \\
& =\frac{m}{2}\left((m+1)^{2}-4 m\right) \\
& =\frac{m}{2}\left(m^{2}-2 m+1\right) \\
& =\frac{m(m-1)^{2}}{2}
\end{aligned}
$$

Finally, consider a general value of $t$ with $m+1 \leq t \leq 2 m-2$.

Again, $(a, b, c, d)=(1, t+1, c, c+t)$ and $2 \leq c \leq t$, but $c+t \leq 2 m$ means that $c \leq 2 m-t \leq 2(t-1)-t=t-2$ which is strictly less than the upper bound coming from the value of $b$.

In other words, when $t$ is large enough, not all of the values of $c$ between 2 and $t$ actually produce admissible values of $d$.

As above, there are $2 m-c-t+1$ triples that work for a given value of $c$, but the upper bound for $c$ is different.

As $c$ increases from 2 to $2 m-t$, we see that there are

$$
(2 m-t-1)+(2 m-t-2)+\cdots+2+1
$$

quadruples, which equals $\frac{1}{2}(2 m-t-1)(2 m-t)$.

We need to add these expressions for $t=m+1$ to $t=2 m-2$.

We substitute $s=2 m-1-t$, which means that we need to add $\frac{1}{2} s(s+1)=\frac{1}{2} s^{2}+\frac{1}{2} s$ for $s=1$ to $s=m-2$.

This gives

$$
\begin{aligned}
\frac{1}{2}\left(1^{2}+\right. & \left.2^{2}+\cdots(m-2)^{2}\right)+\frac{1}{2}(1+2+\cdots+(m-2)) \\
& =\frac{1}{2} \cdot \frac{(m-2)(m-1)(2 m-3)}{6}+\frac{1}{2} \frac{(m-2)(m-1)}{2} \\
& =\frac{(m-2)(m-1)}{4}\left(\frac{2 m-3}{3}+1\right) \\
& =\frac{(m-2)(m-1)}{4} \cdot \frac{2 m}{3} \\
& =\frac{(m-2)(m-1) m}{6}
\end{aligned}
$$

This means that

$$
\begin{aligned}
g(2 m) & =m(m-1) \cdot \frac{4 m-5}{6}+\frac{m(m-1)^{2}}{2}+\frac{(m-2)(m-1) m}{6} \\
& =\frac{m(m-1)}{6} \cdot((4 m-5)+3(m-1)+m-2) \\
& =\frac{m(m-1)}{6} \cdot(8 m-10) \\
& =\frac{m(m-1)(4 m-5)}{3}
\end{aligned}
$$

and so $f(2 m)=4 g(2 m)=\frac{4 m(m-1)(4 m-5)}{3}$.

Using this formula,

- when $m=1$, we obtain $f(2)=0$,
- when $m=2$, we obtain $f(4)=\frac{4 \cdot 2 \cdot 1 \cdot 3}{3}=8$, and
- when $m=3$, we obtain $f(6)=\frac{4 \cdot 3 \cdot 2 \cdot 7}{3}=56$,

which agrees with the specific results that we found earlier.

Thus, $f(40)=\frac{4 \cdot 20 \cdot 19 \cdot 75}{3}=38000$, which is the answer to (b).

(Note that we could have found this value by calculating the value of $g(40)$ specifically and directly.)

Lastly, we find two even positive integers $n=2 m$ with $n<2022$ (that is, with $m<1011$ ) for which 2022 is a divisor of $f(n)=f(2 m)$.

To do this, we note first that $2022=2 \cdot 1011=2 \cdot 3 \cdot 337$ and 337 is a prime number. (How could you verify that 337 is prime?)

Therefore, we need to find two positive integers $m<1011$ for which $\frac{4 m(m-1)(4 m-5)}{3}$ is a multiple of 2 , of 3 , and of 337 .

We can assume that $m \geq 3$, and so we can write $m$ as one of $m=3 q$ or $m=3 q+1$ or $m=3 q+2$ for some positive integer $q$.

When $m=3 q$, we have

$$
\frac{4 m(m-1)(4 m-5)}{3}=\frac{4(3 q)(3 q-1)(12 q-5)}{3}=4 q(3 q-1)(12 q-5)
$$

When $m=3 q+1$, we have

$$
\frac{4 m(m-1)(4 m-5)}{3}=\frac{4(3 q+1)(3 q)(12 q-1)}{3}=4 q(3 q+1)(12 q-1)
$$

When $m=3 q+2$, we have

$$
\frac{4 m(m-1)(4 m-5)}{3}=\frac{4(3 q+2)(3 q+1)(12 q+3)}{3}=4(3 q+1)(3 q+2)(4 q+1)
$$

Each of these expressions is a positive integer since it is the product of positive integers. Each of these expressions is even, since each has a factor of 4 in it.

Therefore, we need to determine 2 small enough values of $q$ for which one of these expressions are divisible by 3 and by 337 .

Since 337 is a larger prime, we work by looking for factors of 337 first and then checking for factors of 3 .

The first two positive multiples of 337 are 337 and 674 .

We can check by working through the factors of these three expressions that it is impossible for one of the factors to equal 337 and for another factor in the same expression to be a multiple of 3 .

When $q=224$, we obtain $3 q+2=674$ (which is a multiple of 337 ) and $4 q+1=897$ (which is a multiple of 3 ).

Therefore, when $q=224$, the expression $4(3 q+1)(3 q+2)(4 q+1)$ is a multiple of 2022 , and so setting $m=3 \cdot 224+2=674$ tells us that $f(1348)$ is a multiple of 2022 .

When $q=225$, we obtain $3 q-1=674$ (which is a multiple of 337) and $q=225$ (which is a multiple of 3 ).

Therefore, when $q=225$, the expression $4 q(3 q-1)(12 q-5)$ is a multiple of 2022 , and so setting $m=3 \cdot 225=675$ tells us that $f(1350)$ is a multiple of 2022 .

This gives us the answer to (c): two even integers $n$ with $n<2022$ for which $f(n)$ is a multiple of 2022 are $n=1348$ and $n=1350$.