"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).