Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My algorithm takes an array of positive non-zero whole numbers and starts summing up the elements from left to right. When the sum goes above $50$, the sum goes back to $0$. The algorithm outputs how many times the sum goes above $50$.

Example: $\langle 30, 4, 25, 61, 17, 54\rangle$

Summation at Step $X$

  1. $30$
  2. $34$
  3. $59 \to 0$
  4. $61 \to 0$
  5. $17$
  6. $71 \to 0$

Outputs $3$

For all the cases that I've encountered so far, an array and its reflection always give the same output. Does this hold true for any array given my constraints?

share|improve this question
2  
What does "reflective" mean? You do know that the sets $\{30,4\}$ and $\{4,30\}$ are the same sets? Order does not matter for sets. Perhaps you are interested in sequences (or "vectors/dynamic arrays" in modern programming languages)? –  Asaf Karagila Apr 9 '13 at 9:29
    
Sorry, I am not very knowledged about the proper terms to use here. I am dealing with arrays, but someone suggested I would more likely get an answer from the math stackexchange than stackoverflow. –  Ying Apr 9 '13 at 9:35
1  
If you explain your terms then there's no need to worry about misusing them. –  Asaf Karagila Apr 9 '13 at 9:36

1 Answer 1

up vote 0 down vote accepted

TL; DR: Yes.

We proceed by strong mathematical induction on the length of the sequence. This means that we infer the validity of the assertion for a sequence by assuming it holds for all shorter sequences.

It is trivial that the assertion holds for sequences of length $0$ and $1$, since they are their own reverse. This is called the induction basis.

Now suppose that we have established it for all sequences of fewer than $n$ terms (the induction hypothesis) and let $s_1, \ldots, s_n$ be a sequence of length $n$.

If for some $1 \le m \le n$ we have $s_m \ge 50$, then because the counter resets at $s_{m+1}$, we have the following situation:

$$\begin{align} \underbrace{s_1 \ldots s_{m-1}}_{\text{$N$ hits}} & \underbrace{s_m}_{\text{$1$ hit}} \ \underbrace{s_{m+1} \ldots s_n}_{\text{$M$ hits}} & \underbrace{s_n \ldots s_{m+1}}_{\text{$M$ hits}} & \underbrace{s_m}_{\text{$1$ hit}} \ \underbrace{s_{m-1} \ldots s_1}_{\text{$N$ hits}} \end{align}$$

as the value of the sum at $s_{m-1}$ does not influence the hit at $s_m$ on the left, and the sum is reset before commencing the tail $s_{m+1}\ldots s_n$ of the sequence. Now we apply the induction hypothesis to deduce that the indicated parts have the same number of hits.

It remains to investigate the case where all $s_m$ satisfy $s_m < 50$. It is easy to see that $s_1, s_2\ldots s_n$ has the same number of hits as $s_1+s_2, s_3\ldots s_n$ because $s_1$ and $s_2$ are less than $50$. If we can show that also $s_1\ldots s_{n-1},s_n$ has the same number of hits as $s_1 \ldots s_{n-2}, s_{n-1}+s_n$ then we are done (applying the latter to $t_1\ldots t_n = s_n \ldots s_1$ and using the induction hypothesis).

So we have a situation $\ldots s_{n-2}, a, b$ and a situation $\ldots s_{n-2}, a+b$ with the sum at $s_{n-2}$ equal to $\sigma_{n-2}$, say.

  • If $\sigma_{n-2} + a+b< 50$ then evidently both tails give zero hits.
  • If $\sigma_{n-2}+a \ge 50$, then surely $\sigma_{n-2}+a+b\ge50$. Because $b < 50$, both tails give precisely one hit in this case.
  • The remaining case is where $\sigma_{n-2}+a+b \ge 50$ but $\sigma_{n-2}+a < 50$. It is clear that the tail $s_{n-2},a+b$ gives one hit. A moment's thought convinces us that $s_{n-2},a,b$ also gives one hit.

This case distinction establishes that $s_1\ldots s_{n-1},s_n$ has the same number of hits as $s_1 \ldots s_{n-2}, s_{n-1}+s_n$ and therefore, by the above analysis, the result follows. I hope it is readable and comprehensible.

share|improve this answer
    
Thanks for your comprehensive answer. Apart from the last paragraph , I was able to follow your logic fairly well and didn't pick up on any pot holes. I just need a bit of time to wrap my mind around that last bit. –  Ying Apr 9 '13 at 12:23
    
@Ying: I've rewritten it using an explicit case distinction. The part you struggled with also was the least appealing part to me, so I took another go at it. Hope that helps. –  Lord_Farin Apr 9 '13 at 12:35
    
That is clearer thanks. I just got a question now. Doesn't your last part with all $s_m < 50$ assume that there will only be 1 hit? I am having trouble seeing how the reasoning expands to cases with more than 1 hit. –  Ying Apr 9 '13 at 12:43
    
It does not. It takes a general sequence satisfying the condition, and then continues to show that it has as many hits as a shorter sequence. An appeal to the IH will establish the required fact. The part before reaching $\sigma_{n-2}$ is simply not interesting because it is the same for both sequences. It can, however, contain any number of hits; this is merely not relevant for the argument. –  Lord_Farin Apr 9 '13 at 12:47
    
Hm.. The problem I am seeing is.. I interpret that you are trying to collaspe/simplify the sequence from left to right by $s_1+s_2, s_3\ldots s_n$. And you reason if you can also collaspe it from the other direction, then the proof is valid. This I agree on. I just don't get why you can reduce the left side to $\sigma_{n-2}$ when proving the latter (collasping from right to left). –  Ying Apr 9 '13 at 13:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.