In 2N-1 integers set exist N with sum dividable to N
ELI
I could not solve it with elementary methods in general case.
Any help is appriciated.
Eli
Robin Chapman
eli...@ecitele.com (ELI) wrote:
> This problem looks well known, but
> I could not solve it with elementary methods in general case.
(i) N = p is prime.
Consider the polynomial f(x_1,...,x_{2p-1}) defined as the
sum of the (2p-1 choose p) terms (x_{k_1} + ... + x_{k_p})^{p-1}
where 0 < k_1 < k_2 < ... < k_p < 2p. Show that each coeeficient
in f is divisible by p. (Each monomial comes from a multiple of p
terms of the above form). Substituting integers a_j gives
f(a_1, ..., a_{2p-1}) = 0 (mod p).
But if no p of the a_j sum to zero mod p then
(a_{k_1} + ... + a_{k_{2p-1}})^{p-1} = 1 (mod p) and so
f(a_1, ..., a_{2p-1}) = (2p-1 choose p) (mod p) contradiction,
as (2p-1 choose p) is not a multiple of p.
(ii) general N. Write N = rs where we know the corresponding statements
for r and s is true. Use the r statement to extract "disjoint"
r-element subsets A_1, ..., A_{2s-1} sets of integers from
the 2rs - 1 given such that each sums to a multiple of r. Let the
sum of A_j be r b_j. Apply the s statement to find s of the b_j
adding to a multiple of s. The corresponding A_j have rs numbers
summing to a multiple of rs.
--
Robin Chapman, http://www.maths.ex.ac.uk/~rjc/rjc.html
"`The twenty-first century didn't begin until a minute
past midnight January first 2001.'"
John Brunner, _Stand on Zanzibar_ (1968)
Sent via Deja.com http://www.deja.com/
Before you buy.
Panh
"Robin Chapman" <rjch...@my-deja.com> a écrit dans le message news:
8up67h$36e$1...@nnrp1.deja.com...
> In article <hauj58...@forum.mathforum.com>,
> eli...@ecitele.com (ELI) wrote:
> > This problem looks well known, but
> > I could not solve it with elementary methods in general case.
>
> (i) N = p is prime.
>
> Consider the polynomial f(x_1,...,x_{2p-1}) defined as the
> sum of the (2p-1 choose p) terms (x_{k_1} + ... + x_{k_p})^{p-1}
> where 0 < k_1 < k_2 < ... < k_p < 2p. Show that each coeeficient
> in f is divisible by p. (Each monomial comes from a multiple of p
> terms of the above form). Substituting integers a_j gives
> f(a_1, ..., a_{2p-1}) = 0 (mod p).
> But if no p of the a_j sum to zero mod p then
> (a_{k_1} + ... + a_{k_{2p-1}})^{p-1} = 1 (mod p)
May be (a_{k_1} + ... + a_{k_p})^{p-1} = 1 (mod p)?
Confirm me, please.
Thanks