- #1
caffeinemachine
Gold Member
MHB
- 799
- 15
Let $S=\{ 1, 2, \ldots , 2p\}$, where $p$ is an odd prime. Find the number of $p$-element subsets of $S$ the sum of whose elements is divisible by $p$.Attempt.
Let $\mathcal{K}$ be the set of all the $p$ element subsets of $S$. Let $\sigma(K)$ denote the sum of the elements of a member $K$ of $\mathcal{K}$. Define a relation $R$ on $\mathcal{K}$ as: $ARB$ if $\sigma(A) \equiv \sigma(B) (\mod p)$, for $A,B \in \mathcal{K}$. Its clear that $R$ is an equivalence relation. Choose $K_0,K_1, \ldots , K_{p-1} \in \mathcal{K}$ such that $\sigma(K_i) \equiv i (\mod p)$. Let $[K_i]$ denote the equivalence class of $K_i$ under $R$.
Claim: $|[K_i]|=|[K_j]|$ whenever $2p>i,j>0$
Proof. Let $x \in \{ 1, \ldots , p-1\}$ be such that $ix \equiv j (\mod p)$ (Such an $x$ exists). If $x$ is odd put $y=x$ else put $y=p+x$. So in any case $y$ is odd and $0<y<2p$.
Now let $K_i = \{ a_1, \ldots , a_p \}$. Consider a set $K^{*}=\{ ya_1, \ldots , ya_p\}$, where each element of $K^{*}$ is reduced mod $2p$ if necessary. One can easily show that $ya_i$'s are all distinct, thus $K^{*} \in \mathcal{K}$. Also $\sigma(K^{*}) \equiv iy \equiv ix \equiv j (\mod p))$, thus $K^{*} \in [K_j]$. SO from each element of $[K_i]$ we can produce one element of $[K_j]$. Also, since $gcd(y,2p)=1$, it follows that two distinct elements of $[K_i]$ don't match to a same element of $[K_j]$. The claim follows.
To arrive at the required answer I just need to show that $|[K_0]|=|[K_1]|+2$. But here I am stuck.
Let $\mathcal{K}$ be the set of all the $p$ element subsets of $S$. Let $\sigma(K)$ denote the sum of the elements of a member $K$ of $\mathcal{K}$. Define a relation $R$ on $\mathcal{K}$ as: $ARB$ if $\sigma(A) \equiv \sigma(B) (\mod p)$, for $A,B \in \mathcal{K}$. Its clear that $R$ is an equivalence relation. Choose $K_0,K_1, \ldots , K_{p-1} \in \mathcal{K}$ such that $\sigma(K_i) \equiv i (\mod p)$. Let $[K_i]$ denote the equivalence class of $K_i$ under $R$.
Claim: $|[K_i]|=|[K_j]|$ whenever $2p>i,j>0$
Proof. Let $x \in \{ 1, \ldots , p-1\}$ be such that $ix \equiv j (\mod p)$ (Such an $x$ exists). If $x$ is odd put $y=x$ else put $y=p+x$. So in any case $y$ is odd and $0<y<2p$.
Now let $K_i = \{ a_1, \ldots , a_p \}$. Consider a set $K^{*}=\{ ya_1, \ldots , ya_p\}$, where each element of $K^{*}$ is reduced mod $2p$ if necessary. One can easily show that $ya_i$'s are all distinct, thus $K^{*} \in \mathcal{K}$. Also $\sigma(K^{*}) \equiv iy \equiv ix \equiv j (\mod p))$, thus $K^{*} \in [K_j]$. SO from each element of $[K_i]$ we can produce one element of $[K_j]$. Also, since $gcd(y,2p)=1$, it follows that two distinct elements of $[K_i]$ don't match to a same element of $[K_j]$. The claim follows.
To arrive at the required answer I just need to show that $|[K_0]|=|[K_1]|+2$. But here I am stuck.