0
$\begingroup$

Let $n_0,n_1,n_2\in\{1,2,\dots,8\}$ and consider the sum

\begin{align*} S&=\sum_{k=0}^8n_{k\bmod3}\\&=n_0+n_1+n_2+n_0+n_1+n_2+n_0+n_1+n_2. \end{align*}

Is there an efficient way to produce all possible triples $(n_0,n_1,n_2)$ such that the following two conditions hold:

  • $\sum_{k=0}^8n_{k\bmod3}=3n_0+3n_1+3n_2\equiv0\bmod9$
  • $\sum_{k=i}^jn_{k\bmod3}\not\equiv0\bmod9$, for $0\leq i\leq j\leq8$, and if $i=0$, then $j\ne8.$

That is, I want $S$ to sum to a multiple of $9$, and every "sub-sum" of $S$ (not necessarily starting from the first term) to not be a multiple $9$.

For examples:

  • $(1,1,4)$ is a valid triple, since $1+1+4+1+1+4+1+1+4=18$ and each sub-sum does not produce a multiple of $9$.

  • $(7,6,8)$ would not be valid, even though $7+6+8+7+6+8+7+6+8=63$, we have a sub-sum $6+8+7+6=27$.

There are a few things I have taken away so far:

  • $n_0+n_1+n_2\equiv0\pmod3$
  • Either $n_0+n_1+n_2\equiv3\pmod9$ or $n_0+n_1+n_2\equiv6\pmod9$
  • If $(a,b,c)$ is a valid triple, then $(9-a,9-b,9-c)$ must also be valid.

I can trudge through the guess-and-check method, but I'm hoping there is a quicker way, as I'd like to generalize this. Thanks!

$\endgroup$
1
$\begingroup$
  • Definitely, none of $n_k$ should be divisible by $9$.
  • If $n_k$ is divisible by $3$, then one of the following sums will be divisible by $9$, (depending on the value of $n_0+n_1+n_2\bmod9$): $$n_k+(n_{k+1}+n_{k+2}+n_{k+3})\qquad n_k+(n_{k+1}+n_{k+2}+n_{k+3})+(n_{k+4}+n_{k+5}+n_{k+6})$$

Proof that these conditions are sufficient:

For an easier notation, I will use $m,n,k$ instead of $n_i$s. Let $n,m,k$ be integers that are not divisible by $3$, but, $m+n+k$ is divisible by $3$, and $m+n+k$ is not divisible by $9$. Then, as you saw $9|3(m+n+k)$.

Let's look at the sub-sums.

  • Any sub-sum with length one would not be divisible $3$ by our choice.
  • Any sub-sum with length two would be of the form $m+n,n+k,k+m$. As $m+n+k$ is a multiple of $3$ and none of $m,n,k$ are multiples of $3$, $m+n+k-m,m+n+k-n,m+n+k-k$ are not divisible by $3$.

Now let's look at the sums with more than $2$ terms. As after each $m$ there is an $n$, and after each $n$ there is a $k$, the first $3$ terms of a sub-sum consists of a combination of $m,n,k$.

In other words, a sub-sum of length $3$ is always $m+n+k$. We know that this number is not divisible by $9$.

A sub-sum of length $4$ is equal to $(m+n+k)+$ a sub-sum of length $1$. As a sub-sum of length $1$ sum is not divisible by $3$ and $m+n+k$ is divisible by $3$, a sub-sum of length $4$ is not divisible by $3$.

A sub-sum of length $5$ is equal to $(m+n+k)+$ a sub-sum of length $2$. As a sub-sum of length $2$ sum is not divisible by $3$ and $m+n+k$ is divisible by $3$, a sub-sum of length $5$ is not divisible by $3$.

Similarly, a sub-sum of length $6,7,8$ is can be decomposed as $2(m+n+k)$+ a smaller sub-sum. And by the exact same reasoning, they can't be divisible by $9$.

Finding $m,n,k$ satisfying these conditions

Observe that $3$ divides $m+n+k$ but does not divide $m,n,k$ implies $m\equiv n\equiv k\pmod3$.

As $3\not\lvert m$, we can choose $m$ from $6$ different choices. Then, for $n$ we're left with $3$ different choices, as we need $3|m-n$. At the end, we have only $2$ choices for $k$, as we want $3|m-k$ but do not want $9|m+n+k$. So, there are $36$ gvalid triplets.

$\endgroup$
  • $\begingroup$ That's great. It follows that $m,n,k\equiv1\bmod3$ or $m,n,k\equiv2\bmod3$. Perfect explanation. $\endgroup$ – Bonnaduck Jun 5 '16 at 1:56
  • $\begingroup$ Also, I accidentally downvoted, and it wont let me change it unless the answer is edited. Feel free to fix that / at the end, so I can change it to an upvote. $\endgroup$ – Bonnaduck Jun 5 '16 at 1:57
  • $\begingroup$ I added the part about finding all valid triplets to the answer $\endgroup$ – Emre Jun 5 '16 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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