From: aderek@jagor.srce.hr (Seronja) Newsgroups: sci.math Subject: IMO 95 Problem Date: 30 Jan 1996 20:40:13 GMT Organization: Public host at University Computing Centre, Zagreb, CROATIA Hi, I wonder if someone could post complete solution of the IMO 95 6th problem. Here it is. 6. Let p be an odd prime number. Find the number of subsets of A of the set{1, 2, ..., 2p} such that (i) A has exactly p elements, and (ii) the sum of all the elements in A is divisible by p. Any help appreciated -- Ante Djerek aderek@jagor.srce.hr ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: IMO 95 Problem Date: 1 Feb 1996 22:02:55 GMT In article <4elvnd$2s9@bagan.srce.hr>, Seronja wrote: >6. Let p be an odd prime number. Find the number of subsets of A of the >set{1, 2, ..., 2p} such that >(i) A has exactly p elements, and >(ii) the sum of all the elements in A is divisible by p. For any set B of integers, let n(B) be the cardinality of B (an integer) and let s(B) be the sum, taken mod p, of the elements in B (an integer-mod-p). So you want to count the number of subsets of A with n(B)=p and s(B)=0. (It will be consistent with what we write below to assign s( { } ) = 0. ) For any set of integers B and an integer m let B+m denote the set of integers b+m with b in B. For any subset B of A write B1 and B2 for the intersections of B with {1, 2, ..., p} and {p+1, ..., 2p} respectively. Notice that there is a one to one correspondence X -> X+p between subsets of those two sets, and it preserves n and s. So if I may write f(i,j) for the number of subsets B1 of {1, 2, ..., p} with n(B1)=i and s(B1)=j, then what we have to count is the sum Sum_{i=0}^p Sum_{j=0}^{p-1} f(i,j)*f(p-i,p-j) (that is, we look for pairs of subsets (B1, B2) of {1, 2, ..., p} of cardinalities i and p-i respectively, and sums j and p-j.) Now, I claim f(i,j) is really independent of j if 0 < i < p. Indeed, if i is not zero (mod p), let k be its inverse (mod p). Then observe that X -> X+k mod p gives a one-to-one correspondence between the subsets with n(X)=i and s(X)=j, and those with n(Y)=i, s(Y)=j+1. Since there are (p choose i) subsets of cardinality i, there must be (1/p) of this number with each possible sum. That is, f(i,j) = (1/p)*(p choose i) if 0 < i < p. Of course, f(0,j) = 0 unless j=0, and f(0,0)=1 (the empty set is the unique subset of cardinality zero and has sum zero). Also, f(p,j)=0 for all j except f(p,p)=1 (the whole set is the unique subset of cardinality p and it has sum p(p+1)/2 = 0 mod p, assuming p > 2, as was given.) So the sum we need to evaluate has the cases i=0, i=generic, and i=p; we get Sum_{i=0}^p Sum_{j=0}^{p-1} f(i,j)*f(p-i,p-j) = 1 + Sum_{i=1}^{p-1} p*[(1/p)*(p choose i)]*[(1/p)*(p choose p-i)] + 1 = 2 + Sum_{i=1}^{p-1} (1/p)*(p choose i)^2 which we can write as (1/p)[2p-2+ Sum (p choose i)^2 ]. This sum is known to be (2p)!/(p!)^2, so my answer is (1/p)[ 2p - 2 + (2p)!/(p!)^2 ] dave ============================================================================== Newsgroups: sci.math From: rjchapma@exeter.ac.uk (R.J.Chapman) Subject: Re: IMO 95 Problem Date: Fri, 2 Feb 1996 08:38:25 GMT In article: <4elvnd$2s9@bagan.srce.hr> aderek@jagor.srce.hr (Seronja) writes: > > Hi, > I wonder if someone could post complete solution of the > IMO 95 6th problem. > Here it is. > > 6. Let p be an odd prime number. Find the number of > subsets of A of the > set{1, 2, ..., 2p} such that > (i) A has exactly p elements, and > (ii) the sum of all the elements in A is divisible by p. > > > Any help appreciated > > -- > Ante Djerek > aderek@jagor.srce.hr > Let f(X,Y) = (1+XY)(1+XY^2)(1+XY^3) .... (1+XY^(2p)). Expanding out f(X,Y) we get a sum of 2^(2p) terms, namely X^|A|Y^s(A) where A runs through the subsets of {1,2,...,2p}, |A| is the size of A and s(A) is the sum of its elements. Let z = exp(2pi i/p), a primitive p-th root of unity. We evaluate the sum f(X,1) + f(X,z) + f(X,z^2) + ... + f(X,z^(p-1)) in two differnent ways. First of all f(X,1) = (1+X)^(2p). For each r with 0 < r < p we have f(X,z^r) = f(X, z) = (1+X^p)^2. This comes from the factorization of the polynomial X^p+1 (and the fact that p is odd). On the other hand a term such as X^|A|Y^s(A) contributes a total of X^|A| (1 + z^s(A) + z^(2s(A)) + ... + z^((p-1)s(A)) ) to the sum. This vanishes unless s(A) is divisible by p, in which case it equals p X^|A|. Hence the coefficient of X^k in f(X,1) + f(X,z) + ... + f(X,z^(p-1)) = (1+X)^(2p) + (p-1)(1+X^p)^2 is p times the number of k-element subsets of {1,2,...,2p} whose sum is divisible by p. If k = p the coefficient of X^p is 2(p-1) + (2p)!/p!^2. The desired number is 1/p of this. Robin Chapman -- Robin J. Chapman Department of Mathematics "... But there are full professors University of Exeter, EX4 4QE, UK in this place who read nothing rjc@maths.exeter.ac.uk but cereal boxes." http://www.maths.ex.ac.uk/~rjc/rjc.html Don Delillo--White Noise ============================================================================== From: Einar Andreas Rodland Newsgroups: sci.math Subject: Re: IMO 95 Problem Date: 2 Feb 1996 12:45:57 GMT aderek@jagor.srce.hr (Seronja) wrote: >Hi, >I wonder if someone could post complete solution of the IMO 95 6th problem. >Here it is. > >6. Let p be an odd prime number. Find the number of subsets of A of the >set{1, 2, ..., 2p} such that >(i) A has exactly p elements, and >(ii) the sum of all the elements in A is divisible by p. > >Any help appreciated > >-- >Ante Djerek >aderek@jagor.srce.hr Let A be a p-subset of {1,2,...,2p}. Change 1 to 2, 2 to 3, ..., p-1 to p, and p to 1. This will add k to Sum_A modulo p, where k is the number of elements in A less than or equal to p. Using this operation will give an identification between sets A with Sum_A=0 mod p and sets A with Sum_A=k mod p. Repeated use will give identifications between sets A with Sum_A=0 mod p and sets A with Sum_A=m for all m. Hence all sums are equally frequent when 0