Let $n \geq 2$ be a positive integer. Determine the number of $n$-tuples $(x_1, x_2, \ldots, x_n)$ such that $x_k \in \{0, 1, 2\}$ for $1 \leq k \leq n$ and $\sum_{k = 1}^n x_k - \prod_{k = 1}^n x_k$ is divisible by $3$.
Problem
Source: Canada RepĂȘchage 2018/6
Tags: combinatorics
09.04.2018 19:08
Any solutions? seems like nasty casework
10.04.2018 03:40
Can we replace $3$ with arbitrary prime $p$?
10.04.2018 03:52
MarkBcc168 wrote: Can we replace $3$ with arbitrary prime $p$? Yes, try to find a general solution. And then pls post it
10.04.2018 04:52
(Note that equality signs are modulo $3$.) Write $\sum_{k=1}^{n}x_k-\prod_{k=1}^{n}x_k=x_1(1-x_2\dotsm x_n)+(x_2+\dotsb+x_n)$. There are $3^{n-1}-2^{n-2}$ tuples $(x_2, \dotsc, x_n)$ satisfying $x_2\dotsm x_n\neq 1$, and for each one there is a unique value of $x_1$ which makes the expression $0$. The remaining cases are where $x_2\dotsm x_n=1$ and $x_2+\dotsb+x_n=0$, where there are $3$ possible values for $x_1$ for each tuple. Let $k$ of $x_2, \dotsc, x_n$ be equal to $2$ and the remaining are equal to $1$. Then $k$ must be even from the first condition and $n-1+k$ must be $0$ from the second condition, so $k\equiv 2n-2\pmod{6}$. The total is \[3^{n-1}-2^{n-2}+3\left(\sum_{k\equiv_6 2n-2}\binom{n-1}{k}\right).\]Expressing the binomial sum explicitly would probably involve casework on the value of $n$ mod 6 or even 12, and they wouldn't make students do something so horrible. Right?
10.04.2018 08:19
Case 1: At least one Number is 0 Case 2: All Numbers 1 Case 3: All Numbers 2 Case 4: Only 1's and 2's