| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Let p be an odd prime. How many different subsets A of the set
{1,2,...,2p} are there which satisfy:
(i) |A| = p
(ii) sum(a in A) == 0 mod p
cheers,
Andrew.
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1991.1 | HANNAH::OSMAN | see HANNAH::IGLOO$:[OSMAN]ERIC.VT240 | Wed Aug 30 1995 15:16 | 2 | |
What does |A| mean in this context | |||||
| 1991.2 | WRKSYS::ROTH | Geometry is the real life! | Wed Aug 30 1995 15:59 | 3 | |
I'd exepct that |A| means the cardinality of the set A - Jim | |||||
| 1991.3 | RUSURE::EDP | Always mount a scratch monkey. | Thu Aug 31 1995 09:44 | 8 | |
See also topic 1930.
-- edp
Public key fingerprint: 8e ad 63 61 ba 0c 26 86 32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.
| |||||
| 1991.4 | DECADA::YODER | MFY | Thu Aug 31 1995 12:26 | 17 | |
Consider the permutation u which rotates P={1,2,...,p} forward by 1 and rotates
Q={p+1,p+2,...,2p} backward by 1. If a set A has k elements in P and p-k in Q,
and its sum mod p is c, call (k,p-k,c) the signature of A. Then Au will have
the signature (k,p-k,c+2k); and conversely, if Au has this signature, A has
signature (k,p-k,c). For k=0 or p this isn't too interesting, but otherwise,
since p is an odd prime, adding 2k repeatedly will cycle through all the values
mod p; so u, iterated if necessary, provides a 1-1 map between sets of signature
(k,p-k,a) and (k,p-k,b) for any a and b.
There is one set with signature (0,p,0) and one with signature (p,0,0): the
set's sum in both cases is == p(p+1)/2 == 0 (mod p). All other sets of
cardinality p divide according to their sum mod p, by using the above argument,
into equinumerous classes of size (C(2p,p) - 2)/p. So the answer is
2 + (C(2p,p) - 2)/p = (C(2p,p)+2p-2)/p
where C(a,b) = a!/(b!(a-b)!) is the combinations function.
| |||||