Challenge Math Challenge - September 2019

  • Thread starter fresh_42
  • Start date
  • Featured
11. Show that the number of ways to express a positive integer ##n## as the sum of consecutive positive integers is equal to the number of odd factors of ##n##.

I am forced to assume that @fresh_42 meant to say "number of odd factors other than (i.e. excluding) 1", because otherwise it is easy to find counter-examples. There is just one way to write 6 as a sum of consecutive natural numbers (##1+2+3##) even though it has two odd factors, 1 and 3.

I am giving below one way to prove the claim stated in the question, but the proof isn't rigorous. I will work out the finer details and post it later when I have some free time.

Observation 1: Any odd natural number ##y >= 3## can be written as a sum of 2 consecutive positive integers, ##(y -1)/2## and ##(y+1)/2##

Observation 2: If a sequence of consecutive natural numbers is an odd-length sequence "centered" at an integer ##x## (e.g. ##4, 5, 6## is centered at ##x=5## and is of length 3), then the sequence's sum is ##x * lengthOfSequence##. The length of such an odd-length sequence can be denoted by ##(2k + 1)##. ##k## will be the count of numbers to the left of ##x## and also the count of numbers to the right of ##x##. It is easy to see that every pair of numbers that are at the same offset to the left and to the right of ##x## in the sequence will add up to ##2x## and the sum is ##(2k+ 1)*x##.

Observation 3: If such an odd-length sequence is centered at an odd number and the sequence starts sufficiently away from 1 (away-ness dependent on ##k##, need to work out the exact formula), then it can be transformed or broken down to an even-length sequence of consecutive natural numbers that is double the length but adds up to the same sum as the original sequence; this even-length sequence will be centered around 2 consecutive numbers derived from the original center ##x## as per observation 1. E.g. ##(6 + 7 + 8) \equiv ((1+2)+(3+4)+(5+6)) \equiv 21##

Observation 4: If the consecutive numbers sequence is of even-length or if it centered at an even number, then there is no transformation to a longer sequence of consecutive numbers (like that in previous observation) that adds up to same sum.

Now suppose there are ##m## distinct ways to factorize ##n## as a multiple of 2 numbers and they are represented as ##a_{1} \times b_{1}, a_{2} \times b_{2}, ..., a_{m} \times b_{m}## where ##a_{i} <= b_{i}##. Also we order then such that ##a{1} < a_{2} < ... < a_{m}##. We can map each such pair to atmost two unique sequences of consecutive natural number that add up to ##n##. The mapping will be as follows:
  • If ##a_{1} = 1##, then we can map to just one sequence, ##(b{1} -1)/2 + (b{1} +1)/2##, provided ##b## is odd. No mapping if ##b_{1} = n## is even
  • If ##a_{i} and b_{i}## are even, then no mapping
  • If both ##a_{i}## and ##b_{i}## are odd, then we map to ##(b_{i} - ((a_{i}-1) \div 2)), (b_{i} - ((a_{i}-1) \div 2) +1), .., b_{i}, (b_{i} + 1), .., (b_{i} + ((a_{i}-1) \div 2))##, i.e. an odd-length sequence centered at an odd number. This sequence can be broken down to another sequence based on obsrvation 3, so we get 2 mappings
  • If only one ##a_{i}## and ##b_{i}## is odd, then only one mapping is possible
If we use the above transformations, we get as many sequences that add up to ##n## as there are odd factors of ##n## (except for the odd factor 1)
 

fresh_42

Mentor
Insights Author
2018 Award
11,425
7,849
11. Show that the number of ways to express a positive integer ##n## as the sum of consecutive positive integers is equal to the number of odd factors of ##n##.

I am forced to assume that @fresh_42 meant to say "number of odd factors other than (i.e. excluding) 1", because otherwise it is easy to find counter-examples. There is just one way to write 6 as a sum of consecutive natural numbers (##1+2+3##) even though it has two odd factors, 1 and 3.
Yes, ##1## isn't considered a factor, since you can always multiply as many units as you want and get any number of factors. Btw. ##-1## is also a unit, so you could argue that ##-1,1,3,-3## are four odd factors of ##6##. It simply makes no sense to allow units.

You're thinking way too complicated. Just calculate ##n=r+(r+1)+\ldots + (r+k)## and examine the factors.
 

StoneTemplePython

Science Advisor
Gold Member
1,085
517
I have found this problem in Tery's Newsletter to his Blog. It is the Cayley Menger Determinant. Your algebraic and his proof are along the same idea: Use ##|AB|^2=|A|^2\cdot|B|^2 -2A\cdot B## and write the matrix ##W=M+M^\tau-2G## where ##M## has the rows ##1,|A|^2,|B|^2,|C|^2,|D|^2## and is thus of rank ##1## and ##G## are all the inner products, surrounded by zeroes in the first column and row.

The coclusion then goes:
##\operatorname{rk}M = \operatorname{rk}M^\tau = 1 ## and ##G=S\cdot S^\tau## with the ##5 \times 2## matrix with rows ##0,A,B,C,D##, i.e. ##\operatorname{rk}G \leq 2##. Hence ##\operatorname{rk}\left( M+M^\tau -2G\right) \leq 1+1+2=4<5 ## and its determinant vanishes.
Yea... I woke up today not liking my finish. It seems to me a nice way might be to use a well chosen Projector with rank 4 or (m-1) and argue by contradiction that if ##\text{rank}\big(\mathbf W\big) = 5## or (= m), then

##3 ##
##= (m-1) +(m-1) -m ##
##= \text{rank}\Big(\big(\mathbf P\mathbf W\big)\Big) + \text{rank}\Big(\mathbf P\Big) - m ##
##\leq \text{rank}\Big(\big(\mathbf P\mathbf W\big)\mathbf P\Big) ##
##= \text{rank}\Big(\mathbf P\mathbf W\mathbf P\Big)##
##\leq 2##

with

##\mathbf q = \begin{bmatrix} 0 \\ \mathbf 1 \end{bmatrix} = \sum_{k=2}^m \mathbf e_k##
##\mathbf P = \mathbf I_m -\frac{1}{m-1}\mathbf {qq}^T##


I don't really prefer contradictions typically but the projection really is just sitting there... A couple more details should make this into a nice solution instead of the rather messy thing I've written.

edit:

(where for avoidance of doubt we have standard basis vectors ##\mathbf e_k##)
##\mathbf W = \begin{bmatrix} 0 &\mathbf 1^T \\\mathbf 1 & \mathbf W_p\end{bmatrix} = \begin{bmatrix} 0 &\mathbf 0^T \\\mathbf 0 & \mathbf W_p\end{bmatrix} + \mathbf e_1 \mathbf q^T + \mathbf q\mathbf e_1^T##

Then
##\mathbf P\mathbf W \mathbf P = \mathbf P\begin{bmatrix} 0 &\mathbf 0^T \\\mathbf 0 & \mathbf W_p\end{bmatrix}\mathbf P + \mathbf P\mathbf e_1 \big(\mathbf q^T\mathbf P\big) + \big(\mathbf P \mathbf q\big)\mathbf e_1^T\mathbf P = \mathbf P\begin{bmatrix} 0 &\mathbf 0^T \\\mathbf 0 & \mathbf W_p\end{bmatrix}\mathbf P##

so we need to examine
##\mathbf P\begin{bmatrix} 0 &\mathbf 0^T \\\mathbf 0 & \mathbf W_p\end{bmatrix}\mathbf P ##
##= \begin{bmatrix} 1 &\mathbf 0^T \\\mathbf 0 & \mathbf P_p\end{bmatrix}\begin{bmatrix} 0 &\mathbf 0^T \\\mathbf 0 & \mathbf W_p\end{bmatrix} \begin{bmatrix} 1 &\mathbf 0^T \\\mathbf 0 & \mathbf P_p\end{bmatrix}##
##= \begin{bmatrix} 0 &\mathbf 0^T \\\mathbf 0 & \mathbf P_p\mathbf W_p\mathbf P_p\end{bmatrix} ##

but this principal submatrix ##\mathbf P_p## is also a projector in nominal (m-1) dimensional space --a nice overlapping sub-problem
##\mathbf P_p = \mathbf I - \frac{1}{m-1} \mathbf {11}^T##

then
##\mathbf P_p\mathbf W_p\mathbf P_p= \mathbf P_p\big(\big(\sum_{k=1}^2\mathbf c_k \tilde{ \mathbf s_k}^T\big) +\mathbf 1\mathbf y^T + \mathbf y \mathbf 1^T\big)\mathbf P_p =\sum_{k=1}^2\mathbf P_p\mathbf c_k \tilde{ \mathbf s_k}^T\mathbf P_p##
because this projector annhilates the ones vector

so
##\text{rank}\big(\mathbf P\mathbf W \mathbf P\big) = \text{rank}\big(\mathbf P_p\mathbf W_p\mathbf P_p\big) \leq 2##
because we have the sum of (at most) 2 rank one updates

this gives the 'upper bound' on rank. The 'lower bound' is due to basic properties of rank with multiplication and
##3 \leq \text{rank}\Big(\mathbf P\mathbf W\mathbf P\Big)\leq 2##
is an obvious contradiction, forced on us by the assumption that ##\mathbf W## was non-singular
[\SPOILER]

the approach on Tao's blog is more succinct and direct, though I find the projector here curiously satisfying
 
Last edited:

fresh_42

Mentor
Insights Author
2018 Award
11,425
7,849
Oh man! I hit the cancel button after typing in my whole answer.
In such cases, duplicate the tab to create a test area, and update the page (F5). The PF software has probably saved most of your reply, i.e. up to the last two lines or so. Another idea is to use the backwards arrow of the browser, but I'm not sure about the result.
 

fresh_42

Mentor
Insights Author
2018 Award
11,425
7,849
the approach on Tao's blog is more succinct and direct, though I find the projector here curiously satisfying
I liked the idea to write a symmetric square matrix as a product of a rectangular matrix and its transpose to find an upper bound for the rank. I think this is a useful trick in similar situations.
 
Yes, ##1## isn't considered a factor, since you can always multiply as many units as you want and get any number of factors. Btw. ##-1## is also a unit, so you could argue that ##-1,1,3,-3## are four odd factors of ##6##. It simply makes no sense to allow units.

You're thinking way too complicated. Just calculate ##n=r+(r+1)+\ldots + (r+k)## and examine the factors.
Thanks to @fresh_42 for the hint! The answer is too obvious after that. I merely add some formalism for the sake of completeness. Before my earlier attempt, I had briefly considered working backward from the formula for sum of sequence as suggested by the hint but didn't proceed along that line as I thought I could arrive at a more "intuitive" solution that didn't need formulae, and that made giving a proof more complex that needed.

(11. Show that the number of ways to express a positive integer ##n## as the sum of consecutive positive integers is equal to the number of odd factors of ##n##.)

Any sequence of ##k## consecutive integers can be written as ##a+1, a+2, ..., a+k##. Here ##a+1## is the 1st integer in the sequence. The sum of this sequence is ##ka + \frac {k(k+1)} {2} = k(a + \frac {k+1} {2})##. We consider positive integer values for ##k##, i.e. ##k \in \{2, 3, 4, .., \}## (since ##k## is the length of a non-empty sequence, it must be a positive integer). We ignore ##k=1## as that will correspond to the degenerate case of single-element sequence ##(n)##, whereas the question apparently considers only sequences having more than 1 integer (except when ##n## itself is 1, in which case there is exactly one sequence satisfying the criteria, ##\{1\}##).

  • We inspect values of ##k \in \{2, 3, .., \}## and look for the value of ##a## such that the sum of the sequence ##a+1, a+2, .., a+k## sums to ##n##, i.e. $$k(a + \frac {k+1} {2}) = n$$.
  • If ##k## is NOT a factor of ##n##, then ##(a + \frac {k+1} {2})## would be non-integer in the above equation, implying that there is no integer ##a## such that a ##k##-length integer sequence will add up to ##n##, so we only need to consider those values of ##k## that are factors of ##n##.
  • If ##k## is even, then ##\frac {k+1} {2}## would be a non-integer, so again (even if that ##k## is a factor of ##n##), there would be no ##k##-length integer sequence that adds up to ##n##
  • If ##k## is an odd factor of ##n##, then ##\frac {k+1} {2}## is an integer and we can find an integer value for ##a## such that the ##k##-long sequence starting at ##a+1## adds up to ##n##. ##a## is given by the equation $$a = \frac {n} {k} - \frac {k+1} {2}$$
  • The value of ##a## from the above equation could be negative, whereas we want only sequences that consist of positive integers alone. It is easy to show that any integer sequence ##a+1, a+2, .. a+k## that adds up to a positive value can be reduced to a positive integer sub-sequence if the original sequence starts with zero or a negative integer
    • If the sequence starts with 0, will simply drop that as removing 0 does not alter the sum of the sequence​
    • If the sequence starts with a negative number and yet adds up to a positive number, then it must be the case that the sequence is of the form ##-x, -x+1, -x+2, ..., 0, 1, .., x, x+1, .., x+j## (for some positive integers ##x, j## satisfying the condition ##x = -(a+1)##, ##x+j = (a+k)##), i.e. for every negative integer ##-y##, the sequence should also contain the positive integer ##y## and the number of positive integers in the sequence should exceed the number of negative integers in the sequence. In effect, the negative integers get canceled out by their positive counterparts in the summation, so we can trim a left portion of original sequence and get a positive-integers-only sequence (##(x+1, x+2, ..., x+j)##) that adds up to the same value as the original sequence.​

Thus, for every odd-factor ##k## of ##n##, we can find a unique sequence of consecutive positive integers that sum to ##n## whereas no such sequence would exist for even-factors of ##n##. Therefore, the number of ways to express any positive number ##n## equals the number of odd factors of ##n##
 

fresh_42

Mentor
Insights Author
2018 Award
11,425
7,849
Thanks to @fresh_42 for the hint! The answer is too obvious after that. I merely add some formalism for the sake of completeness. Before my earlier attempt, I had briefly considered working backward from the formula for sum of sequence as suggested by the hint but didn't proceed along that line as I thought I could arrive at a more "intuitive" solution that didn't need formulae, and that made giving a proof more complex that needed.

(11. Show that the number of ways to express a positive integer ##n## as the sum of consecutive positive integers is equal to the number of odd factors of ##n##.)

Any sequence of ##k## consecutive integers can be written as ##a+1, a+2, ..., a+k##. Here ##a+1## is the 1st integer in the sequence. The sum of this sequence is ##ka + \frac {k(k+1)} {2} = k(a + \frac {k+1} {2})##. We consider positive integer values for ##k##, i.e. ##k \in \{2, 3, 4, .., \}## (since ##k## is the length of a non-empty sequence, it must be a positive integer). We ignore ##k=1## as that will correspond to the degenerate case of single-element sequence ##(n)##, whereas the question apparently considers only sequences having more than 1 integer (except when ##n## itself is 1, in which case there is exactly one sequence satisfying the criteria, ##\{1\}##).

  • We inspect values of ##k \in \{2, 3, .., \}## and look for the value of ##a## such that the sum of the sequence ##a+1, a+2, .., a+k## sums to ##n##, i.e. $$k(a + \frac {k+1} {2}) = n$$.
  • If ##k## is NOT a factor of ##n##, then ##(a + \frac {k+1} {2})## would be non-integer in the above equation, implying that there is no integer ##a## such that a ##k##-length integer sequence will add up to ##n##, so we only need to consider those values of ##k## that are factors of ##n##.
  • If ##k## is even, then ##\frac {k+1} {2}## would be a non-integer, so again (even if that ##k## is a factor of ##n##), there would be no ##k##-length integer sequence that adds up to ##n##
  • If ##k## is an odd factor of ##n##, then ##\frac {k+1} {2}## is an integer and we can find an integer value for ##a## such that the ##k##-long sequence starting at ##a+1## adds up to ##n##. ##a## is given by the equation $$a = \frac {n} {k} - \frac {k+1} {2}$$
  • The value of ##a## from the above equation could be negative, whereas we want only sequences that consist of positive integers alone. It is easy to show that any integer sequence ##a+1, a+2, .. a+k## that adds up to a positive value can be reduced to a positive integer sub-sequence if the original sequence starts with zero or a negative integer
    • If the sequence starts with 0, will simply drop that as removing 0 does not alter the sum of the sequence​
    • If the sequence starts with a negative number and yet adds up to a positive number, then it must be the case that the sequence is of the form ##-x, -x+1, -x+2, ..., 0, 1, .., x, x+1, .., x+j## (for some positive integers ##x, j## satisfying the condition ##x = -(a+1)##, ##x+j = (a+k)##), i.e. for every negative integer ##-y##, the sequence should also contain the positive integer ##y## and the number of positive integers in the sequence should exceed the number of negative integers in the sequence. In effect, the negative integers get canceled out by their positive counterparts in the summation, so we can trim a left portion of original sequence and get a positive-integers-only sequence (##(x+1, x+2, ..., x+j)##) that adds up to the same value as the original sequence.​

Thus, for every odd-factor ##k## of ##n##, we can find a unique sequence of consecutive positive integers that sum to ##n## whereas no such sequence would exist for even-factors of ##n##. Therefore, the number of ways to express any positive number ##n## equals the number of odd factors of ##n##
Thus, for every odd-factor ##k## of ##n##, we can find a unique sequence of consecutive positive integers that sum to ##n##
Where did you show uniqueness?

O.k., it's still too excessive##^*)## but shows that we get a partition from odd factors. Now couldn't it be, that two factors lead to the same partition, in which case our correspondence wouldn't be one-to-one?

##^*)## My suggestion had been ##2n=2(r+(r+1)+\ldots +(r+k))=(k+1)(2r+k)## where exactly one factor is odd. Hence an odd factor belongs to a partition. But this doesn't show uniqueness either, which requires a bit more work to do.
 
Where did you show uniqueness?

O.k., it's still too excessive##^*)## but shows that we get a partition from odd factors. Now couldn't it be, that two factors lead to the same partition, in which case our correspondence wouldn't be one-to-one?

##^*)## My suggestion had been ##2n=2(r+(r+1)+\ldots +(r+k))=(k+1)(2r+k)## where exactly one factor is odd. Hence an odd factor belongs to a partition. But this doesn't show uniqueness either, which requires a bit more work to do.
To show the uniqueness of the sequence for any given value of ##k##, we first show the uniqueness of ##a## given ##k##. Suppose 2 different values of ##k## , say ##k_1## and ##k_2## led to the same of ##a##, then it must be the case where ##\frac n {k_1} − \frac {k_1+1} {2} = \frac n {k_2} − \frac {k_2+1} {2} \implies \frac n {k_1 k_2} = - \frac 1 2 \implies k_1 k_2 = -2n##. That would require either ##k_1## or ##k_2## to be negative, but since only positive values of ##k## are to be considered, no 2 distinct valid values of ##k_1## and ##k_2## will meet that condition required to yield the same value for ##a##. And 2 distinct values of ##a## will result in 2 distinct "untrimmed" sequences, as ##a+1## is the 1st integer in the untrimmed sequences. Since trimming is no done if the original sequnce started at a positive number, 2 distinct positive values of ##a## will continue to be map to 2 distinct sequences.

The other thing to be proven is that even when ##a## is negative, the "trimmed" sequence will be distinct from other valid sequences that sum to ##n##.
  • If we consider two different negative values of ##a##, ##a_1## and ##a_2##. As shown earlier, the corresponding "trimmed" sequences should start at ##-(a_1 + 1) +1 = -a_1## and ##-(a_2 + 1) +1 = -a_2## respectively and those should be distinct from each other if ##a_1## and ##a_2## are distinct.
  • If we consider a positive value ##a_1## (corresponding to ##k = k_1##) and a negative value ##a_2## (corresponding to ##k = k_2##) o ##a##. The earlier proof already showed that only odd factors of ##k## can yield valid sequences, so any original "untrimmed" sequence must have an odd number of integers. Now trimming is done only when ##a## is negative, and when it is done, an odd number of elements are removed from the sequence (every negative number ##-x## in the original sequence is canceled out by the corresponding positive number ##x##, resulting in an even number of positive and negative values getting removed and then number 0 is also removed, so in total an odd number of values get removed). More formally, for the negative value ##a_2##, we end up removing ##-2(a_1 + 1) +1## numbers from the sequence, and that count is an odd number. When an odd number of elements are removed from an original sequence containing an odd number, the resulting sequence will have an even number of elements. Thus a sequence that originally started at a negative integer ##a_2## will be trimmed to an even-length sequence, whereas a sequence that originally started as a positive integer ##a_1## will continue to remain an odd-length sequence as it does not get trimmed. Hence the two sequences must be distinct.
 

fresh_42

Mentor
Insights Author
2018 Award
11,425
7,849
Hence the two sequences must be distinct.
You are not easy to follow. I think you should practice to strip unnecessary explanations in proofs and concentrate more on small logical steps. "should" isn't really appropriate to appear in a proof. Maybe this little article https://www.physicsforums.com/insights/how-most-proofs-are-structured-and-how-to-write-them/ can help, but I'm not sure. I have written better ones than this. So this example here is perhaps a better way to say what I meant:

We still have ##2n=(k+1)(2r+k)=2(r+\ldots +(r+k))## as partition for ##n##. The crucial part is to note, that this splits into factors with exactly one of them is odd, hence we can directly compare the factors of:

If we have two decompositions ##2n=(k+1)(2r+k)=(l+1)(2s+l)## and ##k+1=l+1## or ##2r+k=2s+l## are the same odd numbers, then ##k=l## in both cases. If we have ##k+1=2s+l## then ##l+1=k+2-2s=\dfrac{2n}{2s+l}=2r+k## and ##r=1-s## or ##r,s\in \{\,0,1\,\}##. For ##(r,s)=(0,1)## we get ##2n=(k+1)k=(l+1)(k+1)## or ##k=l+1##, and for ##(r,s)=(1,0)## we have ##2n=(l+1)l=l(2+k)## or ##l=k+1## which is again the same odd factor as ##2n=(l+2)(l+1)=(k+1)(k+2)## is the same decomposition.
 

Want to reply to this thread?

"Math Challenge - September 2019" You must log in or register to reply here.

Related Threads for: Math Challenge - September 2019

Replies
119
Views
6K
Replies
40
Views
5K
Replies
86
Views
10K
Replies
101
Views
6K
Replies
46
Views
4K
Replies
83
Views
10K
Replies
97
Views
11K
Replies
48
Views
4K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top