# Can anyone help with this combinatorial number theory problem involving complex numbers? (From Problems from the Book Ch. 7)

Let $$a_k,b_k,c_k$$ be integers, for $$k=1,2,3...,n$$ and let $$f(x)$$ be the number of ordered triples $$(A,B,C)$$ of subsets (not necessarily non-empty) of $$S$$ with $$A \cup B \cup C=S=\{1,2,3...,n\}$$ such that $$\sum_{i \in S\backslash A}a_i+\sum_{i \in S\backslash B}b_i+\sum_{i \in S\backslash C}c_i \equiv x \pmod{3}$$ Given that $$f(0)=f(1)=f(2)$$, prove there exists $$i\in S$$ such that $$3 \vert a_i+b_i+c_i$$.

My approach was to first consider $$\sum_{k=0}^{2}f(k)\varepsilon^k=\sum_{\\ A \cup B \cup C=S}\varepsilon^{\sum_{i \in S\backslash A}a_i+\sum_{i \in S\backslash B}b_i+\sum_{i \in S\backslash C}c_i}=0$$ where $$\varepsilon=e^{\frac{2\pi i}{3}}$$.

I tried to come up with a product formula for the right-hand side and got

$$\sum_{\\ A \cup B \cup C=S}\varepsilon^{\sum_{i \in S\backslash A}a_i+\sum_{i \in S\backslash B}b_i+\sum_{i \in S\backslash C}c_i}= \prod_{i=1}^{n}(\varepsilon^{a_i}+\varepsilon^{b_i}+\varepsilon^{c_i}+\varepsilon^{a_i+b_i}+\varepsilon^{a_i+c_i}+\varepsilon^{b_i+c_i}+1)$$

Here each term in the product counts the exponent in the different cases as $$i$$ is in at least one of $$A,B,C$$.

$$1$$. The $$\varepsilon^{a_i+b_i}$$ term is in the case where $$i \in C$$ but $$i \notin A,B$$

$$2$$. The $$\varepsilon^{a_i}$$ term is in the case where $$i\in B,C$$ but $$i\notin A$$.

$$3$$. The $$1$$ term is when $$i\in A,B,C$$.

Rest of the terms being symmetric.

I'm unsure where to proceed from here as there is no $$\varepsilon^{a_i+b_i+c_i}$$ term in the product and I'm not even certain if the formula is correct. Any help would be much appreciated.

Since there are $$7^n$$ ordered triples $$(A, B, C)$$, which means that it is impossible to get $$f(0) = f(1) = f(2)$$, and thus we can draw any conclusions that we want

In particular, we can show that for any set of integers

$$\varepsilon^{a_i}+\varepsilon^{b_i}+\varepsilon^{c_i}+\varepsilon^{a_i+b_i}+\varepsilon^{a_i+c_i}+\varepsilon^{b_i+c_i} + 1 \neq 0,$$ and hence their product cannot be 0.

Perhaps, what the authors intended was also that $$A \cap B \cap C = \emptyset$$, in which case there are $$6^n$$ ordered triples and it is not (yet) impossible to get $$f(0) = f(1) = f(2)$$. In this scenario, we have

$$0 = \prod_{i=1}^n (\varepsilon^{a_i}+\varepsilon^{b_i}+\varepsilon^{c_i}+\varepsilon^{a_i+b_i}+\varepsilon^{a_i+c_i}+\varepsilon^{b_i+c_i}),$$

so one of the terms must be equal to 0.

Can you complete the proof from there?

• Yeah, I was thinking that the original question looked a bit strange too! In the new version, I believe you can proceed by contradiction and consider (WLOG) $(a_i,b_i,c_i)$ mod $3$ to get a contradiction. Commented May 14, 2023 at 16:51
• @Indianimperialist123 We can proceed directly. The idea is that the expression is 0 iff $3 \mid a_i + b_i + c_i$. We show that is by case-checking (no other obvious thing to try, and since case checking worked, I didn't bother trying much more). Commented May 14, 2023 at 18:08
• I have essentially the same argument but by discounting all the cases where $a_i+b_i+c_i \not \equiv 0 \pmod3$ Commented May 14, 2023 at 22:43