a) Show that the set $ \mathbb{Q}^{ + }$ of all positive rationals can be partitioned into three disjoint subsets. $ A,B,C$ satisfying the following conditions: \[ BA = B; \& B^2 = C; \& BC = A; \] where $ HK$ stands for the set $ \{hk: h \in H, k \in K\}$ for any two subsets $ H, K$ of $ \mathbb{Q}^{ + }$ and $ H^2$ stands for $ HH.$ b) Show that all positive rational cubes are in $ A$ for such a partition of $ \mathbb{Q}^{ + }.$ c) Find such a partition $ \mathbb{Q}^{ + } = A \cup B \cup C$ with the property that for no positive integer $ n \leq 34,$ both $ n$ and $ n + 1$ are in $ A,$ that is, \[ \text{min} \{n \in \mathbb{N}: n \in A, n + 1 \in A \} > 34. \]
Problem
Source: IMO Shortlist 1993, India 4
Tags: modular arithmetic, number theory, relatively prime, partition, algebra, IMO Shortlist
16.03.2006 02:13
Part a) Take $p$ be a prime of the form $3k+1$ then the following mapping is a homomorphism : \[ f: \mathbb Z_p^*\rightarrow\{1,\omega,\omega^2\} \] where $\omega$ is the primitive $3$rd root of unity and the function is defined by \[ f(g^i)=\omega^i \] where $g$ is a primitive root in $\mathbb Z_p^*$. Now we can write every rational $q$ in the form $p^kq'$ where $q'$ does not have any $p$ (here $k$ can be negative too) So we define our three sets to be \[ A=\{p^kq'|(q',p)=1,f(q')=1\} \] \[ B=\{p^kq'|(q',p)=1,f(q')=\omega\} \] \[ C=\{p^kq'|(q',p)=1,f(q')=\omega^2\} \] Note that $q'$ is also a member of $\mathbb Z_p^*$ so $f(q')$ is well defined. It's easy to check by our homomorphism that the three sets have the desired property. Part b) We show that $A^3=B^3=C^3=A$ \[ BC=A\rightarrow B(B^2)=A\rightarrow B^3=A \] \[ BC=A\rightarrow (BA)C=A\rightarrow A(BC)=A\rightarrow A^2=A\rightarrow A^3=A^2=A \] \[ BC=A\rightarrow BBC=BA=B\rightarrow C^2=B\rightarrow C^3=BC=A \] Part c) We modify our construction for part (a) and the result will become obvious. First take $p=13$ now define $A,B,C$ to be \[ A=\{p^kq'|(q',p)=1,\omega^kf(q')=1\} \] \[ B=\{p^kq'|(q',p)=1,\omega^kf(q')=\omega\} \] \[ C=\{p^kq'|(q',p)=1,\omega^kf(q')=\omega^2\} \] First of all mention that cubes in $\mathbb Z_{13}^*$ are $1,5,8,12$. Suppose that $n,n+1\in A$ then both cannot be relatively prime to $13$ otherwise they should be of the form $13k+\{1,5,8,12\}$ which is impossible. So at least one of them is divisible by $13$. Also because $n\leq 34$ then none can be divisible by $13^2$. So we show that if $m=13k$ and $m\leq 35$ then $m$ is not in $A$. For it ($13k$) to be in $A$ then $k$ should be in $C$ but $k$ can be only $1,2$ and if we chose $g$ (the primitive root in $Z_p^*$ to construct $f$) to be $2$ then $1\in A$ and $2\in B$ so no one is in $C$ and we are done.
13.10.2008 23:59
Solution by seshadri it is easier to back-work our way in this case. note that if such a partition is indeed made then one must also have the following: $ CC = B$; $ AC = C$; $ AA = A$; this is seen as follows; for instance, suppose $ a\in A,c\in C$. then $ ac = ab_1b_2$ (since $ BB = C)$, $ = (ab_1)b_2 = bb_2\in C$. conversely, since $ 1\in A$(since $ 1\notin B,C$), $ C\subset AC$ and so we have the second identity. likewise, $ a_1a_2 = a_1bc = (a_1b)c = b'c\in A$ and so on. this suggests skind of modulo $ 3$ addition i.e. if we denote $ A: = 0,B: = 1,C: = 2$ then the multiplication above translates as addition modulo $ 3$. hence we have the following idea:let $ A: = \{r\in \mathbb{Q}^ + |r = \prod_i p_i^{e_i},\sum_i e_i\equiv 0\pmod 3\}$, $ B: = \{r\in \mathbb{Q}^ + |r = \prod_i p_i^{e_i},\sum_i e_i\equiv 1\pmod 3\}$, $ C: = \{r\in \mathbb{Q}^ + |r = \prod_i p_i^{e_i},\sum_i e_i\equiv 2\pmod 3\}$. everything works as desired.