Prove that the set of positive integers cannot be partitioned into three nonempty subsets such that, for any two integers $x$, $y$ taken from two different subsets, the number $x^{2}-xy+y^{2}$ belongs to the third subset.
Problem
Source:
Tags:
SimonM
30.03.2008 21:35
Proof By Contradiction Assume the existence of 3 such sets. Call them $ A, B, C$. Assume that we have a number $ y \in A$. Consider two integers $ x,z < y$ in different sets, $ B$ and $ C$ respectively. $ \begin{cases} x \in B \\ y \in A \\ \end{cases} \Rightarrow x^2-xy+y^2 \in C$ However, also $ \begin{cases} z \in C \\ y \in A \\ \end{cases} \Rightarrow z^2-zy+y^2 \in B$ We consider the case for contradiction. $ z^2-zy+y^2=x^2-xy+y^2 \Rightarrow (z-x)(y-(x+z)) = 0 \Rightarrow y=z+x$ Therefore each pair $ x,z$ whose sum is $ y$ will be in the same set. Now consider $ y+1$ Clearly $ 1$ has been fixed to a set from the previous line. But this set is distinct from $ y$. However, from early, they must be in the same set. Contradiction
darij grinberg
02.07.2012 17:26
SimonM, your proof is far from complete. What you have shown is step 1 from olorin's solution. (This is also Lemma 1 from the official solution.) You can't prove that $1$ and $y$ lie in different parts of the partition than $y+1$.