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'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top