# Is this algorithm reflective?

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?

-
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
If you explain your terms then there's no need to worry about misusing them. – Asaf Karagila Apr 9 '13 at 9:36

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.

-
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