Consider the generating function $$F(x,y):=\prod_{j=1}^n (1+x^iy).$$The coefficient of $x^sy^k$ then counts the number of subsets of $[n]:=\{1,\ldots,n\}$ with $k$ elements and sum $s$. By Lucas' theorem, the condition $p \mid \tbinom{n}{k}$ is equivalent to, when both $n$ and $k$ are written out in base $p$, there is some $l \geq 1$ such that the "$p^{l-1}$ digit" of $k$ is strictly greater than the $p^{l-1}$ digit of $n$, or equivalently $n\%p^l<k\%p^l$. Now, let $\omega=e^{2\pi i/p^l}$ and plug in $x=\omega$ to our generating function. Because $\prod_{j=1}^{p^l} (t-\omega^j)=t^{p^l}-1$, we have $$F(\omega,y)=\left(1-(-y)^{p^l}\right)^{\lfloor n/p^l\rfloor}\left(\prod_{j=1}^{n\%p^l} (1+\omega^jy)\right).$$Viewed as a polynomial in $y$, it is clear that if some $y^d$ term is nonzero then $d \in [0,n\%p^l] \pmod{p^l}$ (since the second term is a degree-$n\%p^l$ polynomial), and since $k\%p^l>n\%p^l$ it follows that the $y^k$ term is not nonzero. Define $a_0,\ldots,a^{p^l-1}$ such that there are precisely $a_i$ subsets of $[n]$ with size $k$ and sum congruent to $i$ modulo $p^l$. Since the $y^k$ coefficient of the aforementioned expression vanishes, it follows that $$a_0\omega^0+a_1\omega^1+\cdots+a_{p^l-1}\omega^{p^l-1}=0.$$Consider the integer polynomial $P(x):=a_{p^l-1}x^{p^l-1}+\cdots+a_1x+a_0$, so $P$ has $\omega$ as a root. It therefore must be divisible by $\Phi_{p^l}(x)$, which is the minimal polynomial of $\omega$. $\Phi_{p^l}(x)$ has the property that the coefficient of the $x^d$ term is equal to the coefficient of the $x^{(d+p^{l-1})\%p^l}$ term (this follows by inspection, since $\Phi_{p^l}(x)=x^{(p-1)p^{l-1}}+\cdots+x^{p^{l-1}}+1$). Then every multiple of $\Phi_{p^l}(x)$ clearly also has this property, so we have \begin{align*} a_0&=a_{p^{l-1}}=\cdots=a_{(p-1)p^{l-1}}\\ a_1&=a_{p^{l-1}+1}=\cdots=a_{(p-1)p^{l-1}+1}\\ &\vdots\\ a_{p^{l-1}-1}&=a_{2p^{l-1}-1}=\cdots=a^{p^l-1}. \end{align*}Thus we may establish the $p$ classes $C_0,\ldots,C_{p-1}$ such that $C_i$ is the set of all size-$k$ subsets of $[n]$ whose sum modulo $p^l$ falls in $[ip^{l-1},(i+1)p^{l-1})$, whence by the above we have $|C_0|=\cdots=|C_{p-1}|$, as desired. $\blacksquare$

Write $n = a_ip^i + a_{i-1}p^{i-1} + \cdots + a_0$ and $k = b_jp^j + b_{j-1}p^{j-1} + \cdots + b_0$ in base $p$. By Lucas's Theorem, there exists an index $d$ such that $b_d > a_d$. We assign a subset $S$ to class $m$ if the $p^d$ coefficient in the base $p$ expansion of the sum of $S$ is $m$. Clearly any two subsets with the same sum are assigned to the same class. Consider the generating function $F(x,y) = (1+xy)(1+x^2y)\cdots (1+x^ny)$, in which the $x^sy^k$ coefficient extracts the number of size $k$ subsets of $\{1,\cdots, n\}$ with sum $s$. Let $w = e^{\frac{2i\pi}{p^{d+1}}}$. Claim: The coefficient of $y^k$ in $F(w,y)$ is $0$. Proof: Note that $(1+w^{tp^{d+1}+1}y)(1+w^{tp^{d+1}+2}y)\cdots (1+w^{(t+1)p^{d+1}}y) = y^{p^{d+1}} - (-1)^p$. Hence, if $n = q\cdot p^{d+1} + r$, we have $F(w,y) = \left(y^{p^{d+1}} - (-1)^p\right)^qR(y)$, where $R$ is a polynomial of degree at most $r$. In particular, the degree of any nonzero term has remainder at most $r$ upon division by $p^{d+1}$, and since $b_d > a_d$, the claim is proved. Now if $s_i$ for $0\le i\le p^{d+1}-1$ is the number of size $k$ subsets with sum equivalent to $i\pmod{p^{d+1}}$, we have $$0 = s_0 + ws_1 + \cdots + w^{p^{d+1}-1}s_{p^{d+1}-1}.$$ As the minimal polynomial $\Phi_{p^{d+1}}$ of $w$ over $\mathbb{Q}$ has degree $\varphi (p^{d+1}) = p^{d+1} - p^d$, the first $p^{d+1}-p^d$ powers $1, w, \cdots, w^{p^{d+1}-p^d-1}$ of $w$ are linearly independent over $\mathbb{Q}$. In particular, the general solution for the $\{s_i\}$ in $\mathbb{Q}$ should have degree at most $p^{d+1} - (p^{d+1} - p^d) = p^d$. But the set of $\{s_i\}$ with $s_i=s_j$ whenever $i\equiv j\pmod{p^d}$ is a degree $p^d$ solution (each residue class mod $p^d$ is free). Hence all solutions satisfy $s_i=s_j$ whenever $i\equiv j\pmod{p^d}$, so we have $$s_0 + s_1 + \cdots + s_{p^d-1} = s_{p^d} + s_{p^d+1} + \cdots + s_{2\cdot p^d-1} = \cdots = s_{(p-1)p^d} + s_{(p-1)p^d+1} + \cdots + s_{p^{d+1}-1}$$ which means all $p$ classes have the same size, as desired.

Thank you USA for popularizing the sophisticated method of "haha generating functions go brrrr"! This is a dream come true!

Motivation: Do case of $n = 6, k = 3$, and realize that splitting into classes mod p might work. Do the $\prod (1+x^iy)$ generating function, and locate the $y^k$ coefficient. By roots of unity filter this works whenever $k \pmod{p} > n \pmod{p}$. (I found this in about 1 hour) Proceed to clown for two hours before realizing taking mod $p^m$ works. Solution proceeds the same as post #2.

Take $i$ such that $n\mod p^i<k\mod p^i$ by Lucas's Theorem. We will show that the groups for sums $jp^{i-1}$ to $(j+1)p^{i-1}-1$ mod $p^i$ work. Consider the first $p^i$ numbers. If the subset does not contain $0$ or $p^i$ of these numbers, we can do a suitable cyclic shift to get a bijection for all $p$ groups by matching sum $m$ with sum $m+p^{i-1}$, $\ldots$. Therefore, repeating this gives that the subsets that are not in the bijections must have size between $0$ and $n\mod p^i$ mod $p^i$, which cannot happen since $n\mod p^i<k\mod p^i$.

We have $\sum_{\substack{S\subseteq\{1,\ldots,n\}\\|S|=k}}q^{\operatorname{\Sigma} S}=q^{\frac{k(k+1)}{2}}\binom{n}{k}_q=\frac{[n]!_q}{[k]!_q[n-k]!_q}$. If $P$ and $Q$ are polynomials and $P$ is non-constant and irreducible, let $\nu_P(Q)$ be the largest power of $P$ dividing $Q$. By unique factorization, $\nu_P(QR)=\nu_P(Q)+\nu_P(R)$. Lemma. $\nu_{\Phi_{p^i}(q)}([m]_q)=\begin{cases}1&\mbox{if }p^i|m\\0&\mbox{otherwise}\end{cases}$ Proof. Since $[m]_q$ has no repeated roots, the valuation is at most $1$. If $p^i|m$ then $\Phi_{p^i}(q)|[p^i]_q|[m]_q$. Otherwise, $\exp(2\pi i/p^i)$ is a root of $\Phi_{p^i}(q)$ but not $[m]_q$, so $\Phi_{p^i}(q)$ does not divide $[m]_q$. Corollary. $\nu_p(m)=\sum_i\nu_{\Phi_{p^i}(q)}([m]_q)$. Corollary of the corollary. $\nu_p\left(\binom{n}{k}\right)=\sum_i\nu_{\Phi_{p^i}(q)}\left(\binom{n}{k}_q\right)$. Since $\nu_p\left(\binom{n}{k}\right)>0$, it follows that $\nu_{\Phi_{p^i}(q)}\left(\binom{n}{k}_q\right)>0$ for some $i$. Thus, the remainder when $q^{\frac{k(k+1)}{2}}\binom{n}{k}_q$ is divided by $q^{p^i}-1$ has the form $(a_0q^{p^{i-1}-1}+\cdots)(q^{p^{i-1}(p-1)}+q^{p^{i-1}(p-2)}+\cdots+q^0)$, which implies that splitting the subsets by the value of $\left\lfloor\frac{\operatorname{\Sigma}S\mod p^i}{p^{i-1}}\right\rfloor$ produces $p$ equally sized groups.

golue3120 wrote: Since $\nu_p\left(\binom{n}{k}\right)>0$, it follows that $\nu_{\Phi_{p^i}(q)}\left(\binom{n}{k}_q\right)>0$ for some $i$. Thus, the remainder when $q^{\frac{k(k+1)}{2}}\binom{n}{k}_q$ is divided by $q^{p^i}-1$ has the form $(a_0q^{p^{i-1}-1}+\cdots)(q^{p^{i-1}(p-1)}+q^{p^{i-1}(p-2)}+\cdots+q^0)$, which implies that splitting the subsets by the value of $\left\lfloor\frac{\operatorname{\Sigma}S\mod p^i}{p^{i-1}}\right\rfloor$ produces $p$ equally sized groups. I think this should be factorization instead of remainder. Also $\nu_{\Phi_{p^i}(q)}\left(\binom{n}{k}_q\right)>0$ just follows by Lucas's theorem lmao why so much posturing.

Here is a purely combinatorial argument. Lemma. The statement of the problem holds in case $ p^{\ell}\mid n$ but $ p^{\ell}\nmid k$ for any $\ell\ge 1$. Proof. Let $ f: X:=\{1,2,\dots,n\}\to X$ be the circular mapping $ f(x):=x+1, x<n, f(n):=1.$ For any $ A\subset X, |A|=k$ let $ s(A):=\sum_{x\in A}x.$ Note that $$ \displaystyle s(f(A))\equiv s(A)+k \pmod {p^{\ell}}.$$This means that the number of all subsets $ A, A\subset S, |A|=k$ with $ s(A)\equiv r \pmod{p^{\ell}}$ is equal to the number of subsets $ A', A'\subset S, |A'|=k$ with $ s(A')\equiv r+k \pmod{p^{\ell}}$ and it holds for any residue $ r$ modulo $ p^{\ell}.$ We partition all subsets of $X$ with $k$ elements into groups $ G_j, j=0,1,\dots,p-1$ as follows $$ \displaystyle A\in G_j \text{ iff }s(A)\in \{jp^{\ell-1}+i: i=0,1,\dots,p^{\ell-1}-1\} \pmod{p^{\ell}} \qquad(1).$$It easily follows that each $ G_j, j=0,1,\dots,p-1$ contains the same number of subsets. Thus, we get $ p$ families, each of equal size. $ \square$ Let us now prove the general claim. Suppose $ \displaystyle p\mid \binom{n}{k}.$ By Lukas theorem there exist $ \ell$ such that $ n=ap^{\ell} +b, k=cp^{\ell}+d$ where $ c< a$ and $ b<d<p^{\ell}.$ We will prove by induction on $ b$ that by partitioning all subsets of $ X$ with $ k$ elements into groups $ G_j, j=0,1,\dots,p-1$ as in $ (1),$ we get groups of equal size. We just proved it for $ b=0, 0< d<p^{\ell}.$ Suppose it is proven for all $ b'< b$ and $ d, b'<d<p^{\ell}.$ Let $ n=ap^{\ell}+b, k=cp^{\ell}+d.$ All subsets of $\{1,2,\dots,n\}$ with $ k$ elements can be divided into two families \begin{align*} \mathcal{F}_1&:=\{A\cup\{n\} : A\subset \{1,\dots,n-1\}, |A|=k-1 \}\\ \mathcal{F}_2 &:=\{A : A\subset \{1,\dots,n-1\}, |A|=k \} \end{align*}We partition $ \mathcal{F}_1$ and $ \mathcal{F}_2$ into corresponding groups as in $ (1)$ using the induction hypothesis and put the groups together by their residues.

Here is the official solution. Let $\sigma(S)$ denote the sum of the elements of $S$, so that \[ P(x) \coloneqq \sum_{\substack{S\subseteq \{1, \dots, n\} \\ |S|=k}} x^{\sigma(S)} \]is the generating function for the sums of $k$-element subsets of $\{1, \dots, n\}$. By Legendre's formula, \[ \nu_p\left(\binom{n}{k}\right) = \sum_{r=1}^{\infty} \left(\left\lfloor\frac{n}{p^r}\right\rfloor - \left\lfloor\frac{k}{p^r}\right\rfloor - \left\lfloor\frac{n-k}{p^r}\right\rfloor\right) \]so there exists a positive integer $r$ with \[ \left\lfloor\frac{n}{p^r}\right\rfloor - \left\lfloor\frac{k}{p^r}\right\rfloor - \left\lfloor\frac{n-k}{p^r}\right\rfloor > 0. \]The main claim is the following: Claim: $P(x)$ is divisible by \[ \Phi_{p^r}(x) = x^{(p-1)p^{r-1}} + \dots + x^{p^{r-1}} + 1. \]Before proving this claim, we will show how it solves the problem. It implies that there exists a polynomial $Q$ with integer coefficients satisfying \begin{align*} P(x) & = \Phi_{p^r}(x) Q(x)\\ & = (x^{(p-1)p^{r-1}} + \dots + x^{p^{r-1}} + 1) Q(x). \end{align*}Let $c_0,\ c_1,\ \dots$ denote the coefficients of $P$, and define \[ s_i = \sum_{j \equiv i \pmod{p^r}} c_j. \]Then it's easy to see that \begin{alignat*}{4} & s_0 && = s_{p^{r-1}} && = \cdots && = s_{(p-1)p^{r-1}} & s_1 && = s_{p^{r-1}+1} && = \cdots && = s_{(p-1)p^{r-1}+1} & && && \vdots && & s_{p^{r-1}-1} && = s_{2p^{r-1}-1} && = \cdots && = s_{p^r-1}. \end{alignat*} This means we can construct the $p$ classes by placing a set with sum $z$ in class $\left\lfloor\frac{z\mod{p^r}}{p^{r-1}}\right\rfloor$. Now we present two ways to prove the claim. First proof. There's a natural bijection between $k$-element subsets of $\{1, \dots, n\}$ and binary strings consisting of $k$ zeroes and $\ell$ ones: the set $\{a_1, \dots, a_k\}$ corresponds to the string which has zeroes at positions $a_1,\ \dots,\ a_k$. Moreover, the inversion count of this string is simply $(a_1 + \dots + a_k) - \tfrac12k(k+1)$, so we only deal with these inversion counts (equivalently, we are factoring $x^{\frac{k(k+1)}{2}}$ out of $P$). Recall that the generating function for these inversion counts is given by the $q$-binomial coefficient \[ P(x) = \frac{(x-1) \cdots (x^{k+\ell}-1)} {\big[(x-1)\cdots(x^k-1)\big] \times \big[(x-1)\cdots(x^\ell-1)\big]}. \]By choice of $r$, the numerator of $P(x)$ has more factors of $\Phi_{p^r}(x)$ than the denominator, so $\Phi_{p^r}(x)$ divides $P(x)$. Remark: Here is a proof that $P(x)$ is divisible by $\Phi_{p^r}(x)$ for some $r$ using the $q$-binomial formula, without explicitly identifying $r$. We know that $P(x)$ is the product of several cyclotomic polynomials, and that $P(1)$ is a multiple of $p$. Thus there is a factor $\Phi_q(x)$ for which $\Phi_q(1)$ is a multiple of $p$, which is equivalent to $q$ being a power of $p$. Second proof. Note that $P(x)$ is the coefficient of $y^k$ in the polynomial \[ Q(x, y) = (1+xy)(1+x^2y)\dots (1+x^ny). \]Let $a$ be the remainder when $n$ is divided by $p^r$, and let $b$ be the remainder when $k$ is divided by $p^r$; then we have $a<b$ by the choice of $r$. Let $q = \lfloor n/p^r\rfloor$ so $n=p^rq+a$. Consider taking $x$ to be a primitive $p^r$th root of unity. Then \[ Q(x, y) = \left[(1+xy)(1+x^2y)\cdots (1+x^{p^r}y)\right]^q (1+xy)(1+x^2y)\dots (1+x^ay). \]Now $x, x^2, \dots , x^{p^r}$ are all the $p^r$th roots of unity, each exactly once; then we can see that \begin{align*} & (1+xy)(1+x^2y)\cdots (1+x^{p^r}y) \\ &= (1-x(-y))(1-x^2(-y))\cdots (1-x^{p^r}(-y)) \\ &= 1-(-y)^{p^r}, \end{align*}so \[ Q(x,y) = (1-(-y)^{p^r})^q (1+xy)(1+x^2y)\dots (1+x^ay). \]In particular, for any $m$, if the coefficient of $y^m$ in $Q(w,x)$ is nonzero, then $m$ must be congruent to one of $0,1, \dots, a \pmod{p^r}$. Therefore the coefficient of $y^k$ in $Q(x, y)$ is zero. This means that $P(x)=0$ whenever $x$ is a primitive $p^r$th root of unity, which proves the claim.

I hate myself. Cite Lucas to get there is some $p^e$ such that $n \% p^e < k \% p^e$. Take the whole set modulo $p^e$. Let $d$ be the remainder of $n$ upon division by $p^e$. Then our elements are going to look like a bunch of groups of $\{1,\ldots, p^e\}$ together with one group of $\{1,\ldots d\}$. Call this bundle of elements $A$. Then our Lucas condition from earlier implies that the $k$ element subsets cannot contain a number of elements not in $A$ divisible by $p^e$, otherwise we would have $k \equiv d$ modulo $p^e$. I now claim that for any $x \neq 0, p^e$ the subsets of $\{1,\ldots p^e\}$ with $x$ elements and a given sum $r$ mod $p^e$ repeat every $p^{e-1}$ with respect to $r$. To see this just consider cyclically shifting the elements in the subset by $p^{e-v_p(x)-1}$ and see that our subset counts are incremented by the same for each mod $p^e$ residue in a given modulo $p^{e-1}$ residue class. Now since $k > d$, it must be the case that some element not in $A$ is in our subset. Enumerate our subsets with the two step process: 1. Choose how many elements of each group we will include in the final subset. 2. Choose which elements of each group to pick. Since we must have at least one group of the form $\{1, \ldots, p^e\}$ with between $1$ and $p^e-1$ elements, these must contribute the same to all $p$ elements mod $p^e$ which are conguent modulo $p^{e-1}$ by our claim from earlier. This gives us a natural partition into $p$ classes of subsets.

But Ankan said that he had retired from problem making.