MHB Number of p element subsets whose sum is divisible by p

AI Thread Summary
The discussion focuses on finding the number of p-element subsets of the set S={1, 2, ..., 2p} whose sum is divisible by an odd prime p. An equivalence relation R is established on the set of p-element subsets, allowing for the classification of these subsets based on their sums modulo p. A claim is made that the sizes of equivalence classes are equal under certain conditions, and a specific case involving the class [K_0] is highlighted as needing further exploration. The thread references a solution from Ross Honsberger's book, which employs generating functions to derive the size of [K_0] and notes the lack of clarity on why it contains two extra elements compared to other classes. Overall, the discussion emphasizes the complexity of the problem and the various approaches to finding a solution.
caffeinemachine
Gold Member
MHB
Messages
799
Reaction score
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.
 
Physics news on Phys.org
Unable to get anywhere with this, I did an internet search and found that this is a problem (an exceptionally difficult one) from the 1995 International Olympiad. There is a solution in a book by Ross Honsberger (Mathematical Chestnuts from Around the World, pp.220-223; if you search for the book, you will find it freely available online in DjVu format). The solution given there consists of a direct proof, using a generating function, that $|[K_0]| = \frac1p\Bigl\{{2p\choose p} + 2(p-1)\Bigr\}.$ It does not make use of your very elegant proof that all the other sets $[K_i]$ have the same size, and it gives no clue as to why $[K_0]$ should contain two extra elements.
 
Opalg said:
Unable to get anywhere with this, I did an internet search and found that this is a problem (an exceptionally difficult one) from the 1995 International Olympiad. There is a solution in a book by Ross Honsberger (Mathematical Chestnuts from Around the World, pp.220-223; if you search for the book, you will find it freely available online in DjVu format). The solution given there consists of a direct proof, using a generating function, that $|[K_0]| = \frac1p\Bigl\{{2p\choose p} + 2(p-1)\Bigr\}.$ It does not make use of your very elegant proof that all the other sets $[K_i]$ have the same size, and it gives no clue as to why $[K_0]$ should contain two extra elements.
Thank You Opalg. Although the proof given in Honsberger uses a totally different approach, I myself tried a generating function approach and failed. So I am happy to see a proof using generating functions.

Opalg said:
It does not make use of your very elegant proof that ...
*rubs eyes* Thank you so much for the compliment.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top