Let $ m, n \geq 1$ be two coprime integers and let also $ s$ an arbitrary integer. Determine the number of subsets $ A$ of $ \{1, 2, ..., m + n - 1\}$ such that $ |A| = m$ and $ \sum_{x \in A} x \equiv s \pmod{n}$.
Problem
Source: Romanian TST 4 2008, Problem 2
Tags: modular arithmetic, number theory proposed, number theory
13.06.2008 23:05
If $ (m,n) = 1$, then $ \frac 1n \binom{m + n - 1}{m}$. For any chose $ (x_1,...,x_m)$ we can find $ 0\le y<n$, suth that $ \sum_i y_i \equiv s$, were $ y_i=x_i+y \mod m+n-1$.
07.02.2009 06:03
I think this is a really tough problem and i can't solve it I found a solution at http://mateforum.ro/viewtopic.php?t=2048 but it was written in romanian language (or some language else, I don't know) so I couldn't understand it Can someone translate this solution into english? thanks
11.02.2009 07:02
i think i got a solution for a integer s, denote $ A_s$ as the set of m-tuples (X1,X2,…,Xm) ($ 1\le X1<X2<...<Xm\le m+n-1$) such that $ \ X1+X2+...+Xm \equiv s \pmod n$ now we construct a bijection between $ A_s$ and $ A_(s+m)$ : for $ (X1,X2,...,Xm) \in A_s$, let (Y1,Y2,…,Ym) = (X1+1,X2+1,…,Xm+1) if Xm<m+n-1 (1,2,…,t,X1+t+1,X2+t+1,…,X(m-t)+t+1) if Xm=m+n-1 and m-t is the greatest positive integer t $ (1\le t \le m)$ such that X(m-t)<m-t+n-1 (1,2,…,m) if Xm=m+n-1 and there doesn't exist a positive integer t such that Xt<t+n-1 it is trivial that $ (Y1,Y2,...,Ym) \in A_(s+m)$ and the map from (X1,X2,...,Xm) to (Y1,Y2,…,Ym) is a bijection so we deduce that $ A_s$ and $ A_(s+m)$ have same number of elements since (m,n)=1, we get all $ A_s$ have the same number of elements and the number is $ \frac 1n \binom {m+n-1} {m}$