"CRUX 2000" [1994: 286] Proposed by Marcin E. Kuczma, Warszawa, Poland.
  

  Choose 1000 (distinct) integers from {1,...,2000}.  
  The probability their sum is divisible by 5 is

  a)  1/5
  b)  less
  c)  more

-----------------------------------------------------------------------
                                              Torsten Sillke, June 1996

Solution:

  More generally let p prime, we sum m of the first n*p integers.
  The probability of the sum being a multiple of p is
 
  1/p                                                             if not p|m
 
  1/p  +  (1 - 1/p) s(p,m) binomial(n, m/p) / binomial(n*p, m)    if p|m
 
  with s(p,m) = -1 if p even and m/p odd. Otherwise s(p,m) = 1.
  Note: The solution given in (Crux2000) is correct for p odd only.


Proof:

  We will give a more general result. It is valid for every integral p.
  Then we will simplify the formular for p prime.

  Let's count the number of integer partitions into m parts,
  which are a multiple of p.


                   p*n
                  /===\ 
                   | |           k
 g(x,y)  =         | |  ( 1 + y*x  )
                   | |  
                  k = 1  

    s  m
 [ x  y  ] g(x,y)   is the number of ways of getting sum s with m numbers.


 let  w = exp(2*PI*i/p) then by multisection we get

 
             oo
            ---
            \        k*p
 f(y)  =     >    [ x   ] g(x,y) 
            /    
            ---
            k=0
 
            p-1
            ---
         1  \        k
       = -   >    g(w ,y)
         p  /    
            ---
            k=0


            ---
         1  \                      d  n*p/d
       = -   >    phi(d)*( 1 - (-y)  )
         p  /    
            ---
            d|p

 If p is prime, this is

         1          p*n                   p n
 f(y)  = - ( (1 + y)    +  (p-1)*(1 - (-y) )  )
         p


 Now we can get the m-th coefficient

                ---
   m         1  \      
 [y ] f(y) = -   >    phi(d) * s(d,m) * binomial(n*p/d,m/d)
             p  /    
                ---
              d|gcd(p,m)
    
    
 with s(d,m) = -1 if d even and m/d odd. Otherwise s(d,m) = 1.
 Or you may prefer                       d           m/d
                   s(d,m) = 1 - (1 + (-1) )*(1 - (-1)   )/2
 
References:
-----------
- CRUX 2000,
    Crux Mathematicorum, 21 (1995) 322-323, solution
    (Note: the general solution given for prime p is incorrect for p=2)

- IMO 1995 problem 6, (Proposed by Marcin E. Kuczma)
    Crux Mathematicorum, 21 (1995) 269, problems
    http://camal.math.ca/IMO/

    Let p be an odd prime number.
    Find the number of subsets A of the set {1,2,...,2p} such that
    (i) A has exactly p elements, and
    (ii) the sum of all the members in A is divisible by p.

- Titu Andreescu, Zuming Feng,
    102 Combinatorial Problems From the Training of the USA IMO Team,
    Birkhauser, Boston: 2003, ISBN 0-8176-4317-6
    Zbl 1018.00004, MR  2003g:00005
    pp 10: Find the number of subsets of {1, 2, ... 2000}, 
	   the sum of whose elements is divisible by 5.

-----------------------------------------------------------------------
Multisection of a power series:

Given a power series 
    f(x) = a_0 + a_1 x + a_2 x^2 + ... 
one can calculate 
  g_n(x) = a_0 + a_n x^n + a_{2n} x^{2n} + ... 
by the trick known as multisection. 
Let w = exp(2pi i/n) be a primitive n-th root of unity. Then
n g_n(x) = f(x) + f(w x) + f(w^2 x) + ... + f(w^{n-1} x).