1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

[With deference to the authors, I'm not fully confident about this, so please point out any concerns that you have.]

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented May 14, 2023 at 16:51
  • $\begingroup$ @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). $\endgroup$
    – Calvin Lin
    Commented May 14, 2023 at 18:08
  • $\begingroup$ I have essentially the same argument but by discounting all the cases where $a_i+b_i+c_i \not \equiv 0 \pmod3$ $\endgroup$ Commented May 14, 2023 at 22:43

You must log in to answer this question.

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