Odd Primes and Counting

Change the problem slightly, to consider the $p$ element subsets of $\{0,1,2,...,2p-1\}$ that have sum divisible by $p$ (in other words, replace $2p$ by $0$ ). This makes some of the later mathematics simpler.

Define the sets $A = \{0,1,2,...,p-1\}$ and $B = \{p,p+1,p+2,...,2p-1\}$ . Note that $A$ is an abelian group with respect to addition modulo $p$ . Let $\mathcal{S}$ be the set of all subsets of $\{0,1,2,...,2p-1\}$ with $p$ elements, noting that $|\mathcal{S}| = \binom{2p}{p}$ . Let $T(X)$ be the sum (modulo $p$ ) of the elements of $X \in \mathcal{S}$ .

We can define a group action of $A$ on $\mathcal{S}$ by setting $a \star X \; = \; \big\{ a + x \, \big| \, x \in X \cap A \big\} \cup (X \cap B) \hspace{2cm} a \in A \,,\, X \in \mathcal{S}$ so the group action is for $a$ to be added (modulo $p$ ) to the elements of $X$ that are less than $p$ , with all other elements being left alone. Note that $A,B \in \mathcal{S}$ are such that $a \star A = A$ and $a \star B = B$ for all $a \in A$ . If $X \in \mathcal{S}$ and $X \neq A,B$ , then $|X \cap A| = n$ for some $1 \le n \le p-1$ It is then clear that $T(a \star X) \equiv an + T(X) \pmod{p}$ . Thus $T(a \star X) \not\equiv T(b \star X) \pmod{p}$ if $a,b \in A$ with $a \neq b$ . Thus the orbit $\Omega(X) = \{a \star X \,|\, a \in A\}$ of $X$ will have $p$ elements in it, and exactly one element $Y$ out of that orbit with have total $T(Y) \equiv 0 \pmod{p}$ .

By the standard theory of group actions, it is possible to write $\mathcal{S}$ as a disjoint union of orbits. Two orbits are $\{A\}$ and $\{B\}$ , and all other orbits have $p$ elements in them. Since $p$ is odd we see that $T(A) \equiv \tfrac12p(p-1) \equiv 0 \pmod{p}$ and also $T(B) \equiv T(A) + p^2 \equiv 0 \pmod{p}$ Thus we see that each orbit of $\mathcal{S}$ contains exactly one set $Y \in \mathcal{S}$ such that $T(Y) \equiv 0 \pmod{p}$ .

Thus there are exactly as many subsets of $\{0,1,2,...,2p-1\}$ with $p$ elements whose elements add to a multiple of $p$ as there are orbits in $\mathcal{S}$ , namely $\frac{1}{p}\left[\binom{2p}{p}-2\right] + 2$ In the case $p=13$ , we obtain the answer $\boxed{800048}$ .

I like Mark's solution and I think it's probably the right one, but here's a maybe slightly more down-to-earth solution using generating functions.

Consider the function $F(x,y) = \prod\limits_{k=1}^{2p} (1+x^k y).$ Then the coefficient of $y^p$ is $\sum\limits_{d=1}^{\infty} a_d x^d$ where $a_d$ is the number of $p$ -element subsets of $\{1, 2, \ldots, 2p\}$ summing to $d.$ So we want the sum of the coefficients of $x^{pm} y^p$ in $F(x,y),$ as $m$ runs over all positive integers. That is, if $F(x,y) = \sum_{b,c} a_{b,c} x^b y^c,$ we want $a_{p,p} + a_{2p,p} + a_{3p,p} + \cdots.$

There is a trick for this: let $\omega$ be a primitive $13$ th root of unity, and look at $G(y) = \frac1{p} \sum\limits_{d=0}^{p-1} F(\omega^d,y).$ Then $\begin{aligned} G(y) &= \frac1{p} \sum\limits_{d=0}^{p-1} \sum_{b,c} a_{b,c} \omega^{db} y^c \\ &= \sum_{b,c} a_{b,c} y^c \left( \frac1{p} \sum\limits_{d=0}^{p-1} \left( \omega^b \right)^d \right) \\ &= \sum_{b,c} a_{b,c} y^c \left( \begin{cases} 0 & \text{if } p \nmid b \\ 1 & \text{if } p|b \end{cases} \right) \\ &= \sum_c \left( a_{p,c} + a_{2p,c}+ \cdots \right) y^c, \end{aligned}$ so the coefficient of $y^p$ in $G(y)$ is exactly the number we want.

Now $\begin{aligned} G(y) &= \frac1{p} \sum_{d=0}^{p-1} F(\omega^d,y) \\ &= \frac1{p} \sum_{d=0}^{p-1} \prod_{k=1}^{2p} (1+\omega^{dk} y) \\ &= \frac1{p} \sum_{d=0}^{p-1} \prod_{k=1}^{2p} (y+\omega^{-dk}) \end{aligned}$ (to go from the second to the third line, note that we are multiplying each product by $\prod_{k=1}^{2p} \omega^{-dk} = \omega^{-dp(2p+1)} = 1$ ), and note now that $-\omega^{-dk}$ runs--twice--over the roots of $y^p+1$ if $1 \le d \le p-1,$ and otherwise $\prod_{k=1}^{2p} (1+\omega^{dk} y) = (1+y)^{2p}$ if $d=0.$

Putting it all together, we get $G(y) = \frac1{p} \left( (1+y)^{2p} + (p-1)(y^p+1)^2 \right),$ so the coefficient of $y^p$ is just $\frac1{p} \left( \binom{2p}{p} + 2(p-1)\right).$ When $p=13$ this is $\fbox{800048}.$

Unless I'm mistaken, it seems like looking at the coefficients of other powers of $y$ gives an easy way to compute the number of $c$ -element subsets of $\{1,\ldots,2p\}$ whose sum is a multiple of $p,$ for any $c,$ namely: $\frac1{p} \binom{2p}{c}$ unless $c=0,p,2p;$ the above formula if $c=p;$ and of course $1$ if $c=0,2p.$

Not a complete solution.

There's ${26}\choose{13}$ total subsets. It makes some sense that about $\frac{1}{13}$ of them would give a remainder of $0\pmod{13}$ , so a reasonable guess at the answer would be $\frac{1}{13} {26\choose13} =800046.(153846)$ , which is already really close. As it turns out, all remainders other than $0$ have $800046$ subsets corresponding to them, and $0$ has $800048$ . It's therefore probably possible to find a one-to-one correspondence between the subsets for each nonzero remainder, although I wasn't able to find one. Help here would be appreciated.

Anyway, here's a cheating solution utilizing a python program to find the answer: $a(x,y,z,n)$ is the number of subsets of cardinality $y$ of the first $x$ integers giving a sum of $z\pmod{n}$ :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import math
mem={}

def a(x,y,z,n):
  if (x,y,z) in mem:
    return mem[(x,y,z)]
  if x<y:
    return 0
  if y==1:
    if x%n>z:
      return math.floor(x/n)+1
    return math.floor(x/n)
  mem[(x,y,z)]=a(x-1,y,z,n)+a(x-1,y-1,(z-x+1)%n,n)
  return mem[(x,y,z)]
print(a(26,13,0,13))