MHB Among 2n-1 integers summation of some n of these is divisible by n.

  • Thread starter Thread starter caffeinemachine
  • Start date Start date
  • Tags Tags
    Integers Summation
AI Thread Summary
The discussion centers on proving that from a set of \(2n-1\) positive integers, where \(n=2^{k-1}\), one can select \(n\) integers such that their sum is divisible by \(n\). The proof uses induction, starting with a base case for \(k\) and extending it to \(k+1\). By dividing the \(2n_{k+1}-1\) integers into two sets of size \(2n_k-1\) and one singleton, it demonstrates that \(n_k\) integers can be selected from each of the two larger sets, ensuring their sums are divisible by \(n_k\). This leads to a combined selection of \(2n_k\) integers, which is equal to \(n_{k+1}\). The discussion concludes with a note on the potential typo regarding the term "equal to," emphasizing that the focus should remain on divisibility.
caffeinemachine
Gold Member
MHB
Messages
799
Reaction score
15
Let $k$ be a positive integer. Let $n=2^{k-1}$. Prove that, from $2n-1$ positive integers, one can select $n$ integers, such that their sum is divisible by $n$.
 
Mathematics news on Phys.org
caffeinemachine said:
Let $k$ be a positive integer. Let $n=2^{k-1}$. Prove that, from $2n-1$ positive integers, one can select $n$ integers, such that their sum is divisible by $n$.
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
 
CaptainBlack said:
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 sum equal to $2n_k=n_{k+1}$.
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.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top