0
$\begingroup$

Exercise. Determine the number of sequences $(a_1,a_2,a_3,a_4,a_5)\in \{0,1,2\}^5$, such that $\sum_{i=1}^{k}a_i\ne3,\forall k\in\{1,2,...,5\}$.

Attempt. The total number of sequences is $3^5$. If we find the set of all the solutions to the indefinite equation $$a_1+a_2+a_3+a_4+a_5=3,\forall j\in\{1,2,...,5\}:a_j\in\{0,1,2\}.$$

Then, we shall get the result by subtracting the number of solutions from the total number of sequences since each of the above restrictions is counted precisely once. There are $7 \choose 3$ solutions to the indefinite equation. But we have to eliminate $5$ of them when some $a_j=3$. Thus, the answer is:$$3^5-{7\choose3}+5=213.$$

Is my solution correct?

Any help is appreciated.

$\endgroup$
3
  • 2
    $\begingroup$ Yes, this looks good. For phrasing: it's a little confusing to use the same variables $\{a_i\}$ for both the original sequence and for the abstract sequence you used for counting. It confused me, for example, when you considered the case $a_j=3$ which, of course, is impossible for the first equation, but allowed by the second. Consider using different variables to avoid confusion. $\endgroup$
    – lulu
    Jul 22, 2022 at 8:06
  • 1
    $\begingroup$ Note my remark on notation. Doesn't change the content of your argument, but might avoid some ambiguity. $\endgroup$
    – lulu
    Jul 22, 2022 at 8:09
  • 2
    $\begingroup$ Maybe I misunderstood the question, but you need to count the number of sequences such that $a_1$, $a_1+a_2$, $a_1+a_2+a_3$, $a_1+a_2+a_3+a_4$ and $a_1+a_2+a_3+a_4+a_5$ are all different from $3$. Alternatively, you need to eliminate the cases where one of the sums is $3$, not only $a_1+a_2+a_3+a_4+a_5$. $\endgroup$
    – Taladris
    Jul 22, 2022 at 10:57

1 Answer 1

Reset to default
2
$\begingroup$

No, this is not correct.

Spelled out, $\forall k\in\{1,2,...,5\}:\sum_{i=1}^{k}a_i\ne3$ is the condition that $a_1\neq 3$, $a_1+a_2\neq 3$, $a_1+a_2+a_3\neq 3$, $a_1+a_2+a_3+a_4\neq 3$, $a_1+a_2+a_3+a_4+a_5\neq 3$.

You have only considered $a_1+a_2+a_3+a_4+a_5\neq 3$ (or, its negation).

As the possibilities are small ($3^5=243$), I'm going to argue by cases:

$a_1\in \{0,1,2\}$ so we have no issue satisfying $a_1\neq 3$.

$a_1+a_2\neq 3$ leaves us with $(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0), (2, 2)$ as options. We only care about $a_1+a_2$ for further reasoning, so we can treat the three instances of $a_1+a_2=2$ ($(1,1),(2,0),(0,2)$ identically, and the two instances of $a_1+a_2=1$ ($(0,1),(1,0)$) identically.

As $a_i\ge 0$, starting with $(2,2)$ gives $3^3=27$ valid combinations for $a_3,a_4,a_5$.

For $a_1+a_2=2$, if $a_3=2$ then we can choose any $a_4,a_5$ for $3^2=9$ valid combinations. If $a_3=0,a_4=2$ then any $a_5$ is valid, for $3$ solutions. If $a_3=0,a_4=0$ then $a_5=0$ or $a_5=2$ work, for $2$ solutions. We have $9+3+2=14$ options for $(a_3,a_4,a_5)$. And there were $3$ ways of getting $a_1+a_2=2$, so that's $42$ solutions total.

For $a_1+a_2=1$, the combinations for $(a_3,a_4,a_5)$ are: $(1, 2, a_5),(1, 0, 2),(1, 0, 0),(0, 1, 2),(0, 1, 0),(0, 0, 1),(0, 0, 0)$. This is $9$ options. There are two options for $a_1+a_2=1$ so that gives us $18$ solutions total.

For $(0,0)$, we repeat our logic from before to find that $(a_3,a_4)\in \{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (2, 0), (2, 2)\}$. We can have (for $(a_3,a_4,a_5)$) $(0,0,a_5),(0,1,0/1),(1,0,0/1),(0,2,0/2),(1,1,0/2),(2,0,0/2)(2,2,a_5)$ for $16$ solutions.

Thus, we've found $27+42+18+16=103$ solutions out of the $243$ possible combinations. Some quick and dirty Python code tells me that this is true.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .