- Thread starter
- #1

- Mar 10, 2012

- 835

- Thread starter caffeinemachine
- Start date

- Thread starter
- #1

- Mar 10, 2012

- 835

- Jan 26, 2012

- 890

Suppose this true for some \(k\).

Now consider the case for \(k+1\), then \(n_{k+1}=2n_k\) and any set of \(2n_{k+1}-1\) positive integers. Now split the \(2n_{k+1}-1\) positive integers into three sets two of size \(2n_k-1\), and one of size \(1\).

We can select \(n_k\) integers from the first set with sum divisible by \(n_k\), and a set of \(n_k\) integers from the second set with sum divisible by \(n_k\). So we have a combined set of \(2n_k=n_{k+1}\) integers from the set of 2n_{k+1}-1 integers with sum equal to 2n_k=n_{k+1}.

The rest of the details for a proof by induction I leave to the reader.

CB

- Thread starter
- #3

- Mar 10, 2012

- 835

I think "equal to" is a typo. What you probably intended was "divisible by". But even that is not guaranteed (at least I am not convinced). Divisibility by $n_k$ is guaranteed though.Suppose this true for some \(k\).

We can select \(n_k\) integers from the first set with sum divisible by \(n_k\), and a set of \(n_k\) integers from the second set with sum divisible by \(n_k\). So we have a combined set of \(2n_k=n_{k+1}\) integers from the set of $2n_{k+1}-1$ integers with sumequalto $2n_k=n_{k+1}$.