Let $A$ and $B$ be disjoint nonempty sets with $A \cup B = \{1, 2,3, \ldots, 10\}$. Show that there exist elements $a \in A$ and $b \in B$ such that the number $a^3 + ab^2 + b^3$ is divisible by $11$.
Problem
Source: Middle European Mathematical Olympiad 2011 - Team Compt. T-7
Tags: modular arithmetic, number theory proposed, number theory, case view
06.09.2011 17:58
27.11.2011 07:57
if$11|a^3+ab^2+b^3$we connect a with b as $a\rightarrow b$. then they form a Hamilton circle: $1\rightarrow6\rightarrow3\rightarrow7\rightarrow9\rightarrow10\rightarrow5\rightarrow8\rightarrow4\rightarrow2\rightarrow1$.
24.09.2014 09:05
Quote: if11|a^3+ab^2+b^3we connect a with b as a\rightarrow b. then they form a Hamilton circle: 1\rightarrow6\rightarrow3\rightarrow7\rightarrow9\rightarrow10\rightarrow5\rightarrow8\rightarrow4\rightarrow2\rightarrow1. would you please make it clear: what implication does a Hamiltonian circle make in our solution?
26.09.2014 22:07
Solution: Denote the inverse of $b\pmod {11}$ as $c$. Then $a^3+ab^2+b^2\equiv 0\pmod {11}\implies (ac)^3+(ac)+1\equiv 0\pmod {11}$. Checking cases, we find that $ac\equiv 2\pmod {11}$, and so $2b\equiv a\pmod {11}$. We will try to construct the sets $A$ and $B$ with out having two $a, b$ in the same set, as that would imply the existence of a solution to $a^3+ab^2+b^2\equiv 0\pmod {11}$. We proceed by listing the values of $a, b \pmod {11}$. All calculations below will be done $\pmod {11}$. 1: $b\equiv 1\implies a\equiv 2$ 2: $b\equiv 2\implies a\equiv 4$ 3: $b\equiv 3\implies a\equiv 6$ 4: $b\equiv 4\implies a\equiv 8$ 5: $b\equiv 5\implies a\equiv 10$ 6: $b\equiv 6\implies a\equiv 1$ 7: $b\equiv 7\implies a\equiv 3$ 8: $b\equiv 8\implies a\equiv 5$ 9: $b\equiv 9\implies a\equiv 7$ 10: $b\equiv 10\implies a\equiv 9$ Let us start out with the element $1$. Assume WLOG $\{1\}\in B$. Then we have the following chain of elements that must be in $B$: $1\rightarrow 2\rightarrow 4\rightarrow 8\rightarrow 5\rightarrow 10\rightarrow 9\rightarrow 7\rightarrow 3\rightarrow 6$. But this chain includes all elements of the set $A\cup B$, implying $A$ is empty, contradiction. Hence, there exits a solution to the congruence for some $a\in A$ and $b\in B$. $\blacksquare$
17.01.2022 15:12
If $1 \in A$ $1\implies 6\implies 3\implies 7\implies 9\implies 10\implies 5\implies 8\implies 4\implies 2$ Contradiction B remains empty.
20.03.2022 14:25
Cute problem. Note that for $a=2b$ we have: $$ a^3+ab^2+b^3 = 8b^3 +2b^3+b^3 =11b^3 \equiv 0 \pmod {11} $$Suppose that set $B$ contains elements $x_1, x_2, \ldots , x_n$, where $1\le n \le 9$. If set $A$ contains one of the elements $2x_1, x_2, \ldots , 2x_n$ reduced $\pmod {11}$ problem is solved. Otherwise $2x_1, 2x_2, \ldots, 2x_n$ is permutation of $x_1, x_2, \ldots, x_n$ reduced $\pmod {11}$, meaning that: $$ 2^nx_1x_2 \ldots x_ n \equiv x_1x_2 \ldots x_n \pmod {11} \implies x_1x_2 \ldots x_n(2^n-1) \equiv 0 \pmod {11} $$But for $1 \le n \le 9$ it is easy to verify that $2^n -1$ is not divisible by $11$, thus the problem is solved.
30.03.2022 18:35
Claim: there is an $a\in A$ and $b\in B$ such that $a\equiv2b\pmod{11}$ Suppose otherwise. Then by induction, $2^na\in A$ for $1\le n\le11$. Since $a\not\equiv1\pmod{11}$ each $2^na\in A$ for $1\le n\le11$ is distinct since $\operatorname{ord}_{11}(2)=10$. But by PHP one of these must be $2b\pmod{11}$. Then for such $a$ and $b$: $$a^3+ab^2+b^2\equiv(2b)^3+2b\cdot b^2+b^3\equiv11b^3\equiv0\pmod{11}.$$