Every positive integer can be represented as a sum of one or more consecutive positive integers. For each $n$ , find the number of such represententation of $n$.
Problem
Source: 1-st Taiwanese Mathematical Olympiad 1992
Tags: combinatorics, combinatorics solved
24.01.2007 08:07
n=1 is easy. n=2k+1 then n=k+(k+1) If n is even number then n must has odd factor(why?) if can express I let $n=2^{i}.(2k+1)$ - If $2^{i}>k$then I write $n=(2^{i}-k)+(2^{i}-k+1)+...+(2^{i}+k)$ - If $2^{i}<k$ the I write$n=(k-2^{i}+1)+..+(k+2^{i})$
24.01.2007 10:26
cuopbientcd wrote: n=1 is easy. n=2k+1 then n=k+(k+1) If n is even number then n must has odd factor(why?) if can express I let $n=2^{i}.(2k+1)$ - If $2^{i}>k$then I write $n=(2^{i}-k)+(2^{i}-k+1)+...+(2^{i}+k)$ - If $2^{i}<k$ the I write$n=(k-2^{i}+1)+..+(k+2^{i})$ You NOT understand problem
25.01.2007 06:30
NO I DON'T THINK THIS . IF n=1 or n odd or n=2^i(2k+1) then n only express as sum of two or more consecutive positive integers . and orther situation then can't express. ARE YOU OK?
25.01.2007 07:00
Are you sure? N.T.TUAN wrote: Every positive integer can be represented as a sum of one or more consecutive positive integers. For each $n$ , find the number of such represententation of $n$.
25.01.2007 19:20
04.06.2018 18:55
Bump!!!!!Bump!!!!!Bump!!!!!Bump!!!!!Bump!!!!!Bump!!!!!Bump!!!!!Bump!!!!!Bump!!!!!Bump!!!!!Bump!!!!!
08.06.2018 19:49
My Solution Let us call a set of consecutive integers which sum to $n$ a Sum. Let us call a sum a Positive Sum, if all of the integers in the sum are positive, and let us call a sum a Negative Sum if at least one of the integers of the sum are non-positive. For example, the sum $(1+2+3+4)$ is a Positive Sum and the sums $(0+1+2), (-2+-1+0+1+2+3)$ are Negative Sums. Now we show that for a fixed positive value of $n$, the number of Negative Sums equals the number of Positive Sums. First we show that given a Positive Sum, we can construct a unique Negative Sum from it. Let $n = a+1~+~a+2~+~a+3~+~a+4~\dots +~ a+k$, where $a$ is a whole number. Now consider the Negative sum $n = -a~+~-(a-1)~+~-(a-2)~+~\dots +~0~+~1~+~2~+~\dots a~+~a+1~+~a+2~+~\dots +~a+k$. This Negative sum can be constructed from the Positive Sum. For instance, the Negative Sum corresponding to $2+3+4$ is $-1 + 0 + 1 + 2 + 3 + 4$, and the negative sum corresponding to $1+2+3$ is $0+1+2+3$. Thus, the number of Positive Sums $\le$ number of Negative Sums. Now we see that we can construct a unique positive sum from a negative sum, in the exact reverse of the proof of our previous claim. So, we conclude that the number of Negative Sums $\le$ number of Positive Sums. Hence, number of Positive Sums equals the number of Negative Sums. We claim that the number of sums is twice the number of divisors of the odd part of $n$. Let $n = a+1~+~a+2~+~a+3~+~a+4~\dots +~ a+k$, where $a$ is an integer. We know that $a+1~+~a+2~+~a+3~+~a+4~\dots +~ a+k = \frac{k}2 \cdot (2a + k + 1)$. So, we have $n = \frac{k}2 \cdot (2a + k + 1)$. So, we conclude that $k\mid 2n$. Now we have $2a + k + 1 = \frac{2n}{k}$, and so, $2a = \frac{2n}{k} -k -1$. As $a$ is an integer, we conclude that $\frac{2n}{k}, k$ have different parity. Note that at least one of $\frac{2n}{k}, k$ is even. Both cannot be even for integral value of $a$. So, either $k$ is odd or $\upsilon_2(k)=\upsilon_2(2n)$. Now assume that $n = 2^t (2l+1)$, where $t,l$ are non negative integers. So, $2n = 2^{t+1} (2l+1)$. When $k$ is odd, from $k\mid 2n$, $k\mid 2l+1$. If $k$ is even, we have $2^{t+1}\mid k$ and $\mid 2^{t+1}(2l+1)$. So, the number of even $k$ equals the number of odd $k$. As the number of odd $k$ is equal to $\tau (2l+1)$ from $k\mid 2l+1$, we have the total number of Sums is $2\cdot \tau (2l+1)$. We need the number of positive sums, which is $\tau (2l+1)$, the number of divisors of the odd part of $n$. Q E D