For $A\subset\mathbb Z$ and $a,b\in\mathbb Z$. We define $aA+b: =\{ax+b|x\in A\}$. If $a\neq0$ then we calll $aA+b$ and $A$ to similar sets. In this question the Cantor set $C$ is the number of non-negative integers that in their base-3 representation there is no $1$ digit. You see \[C=(3C)\dot\cup(3C+2)\ \ \ \ \ \ (1)\] (i.e. $C$ is partitioned to sets $3C$ and $3C+2$). We give another example $C=(3C)\dot\cup(9C+6)\dot\cup(3C+2)$. A representation of $C$ is a partition of $C$ to some similiar sets. i.e. \[C=\bigcup_{i=1}^{n}C_{i}\ \ \ \ \ \ (2)\] and $C_{i}=a_{i}C+b_{i}$ are similar to $C$. We call a representation of $C$ a primitive representation iff union of some of $C_{i}$ is not a set similar and not equal to $C$. Consider a primitive representation of Cantor set. Prove that a) $a_{i}>1$. b) $a_{i}$ are powers of 3. c) $a_{i}>b_{i}$ d) (1) is the only primitive representation of $C$.
Problem
Source: Iranian National Math Olympiad (Final exam) 2006
Tags: geometry, geometric transformation, number theory proposed, number theory
14.09.2006 17:04
(a), (b) and (c) do not depend on the fact that the partition is primitive. Unless we're dealing with the trivial partition $C=C$ (so let's assume that $n\ge 2$), if for some $i$ one of (a), (b), (c) doesn't hold, then $a_{i}C+b_{i}$ isn't even contained in $C$: (a) If some $a_{i}=1$ then for some non-zero $b$ we must have $C+b\subset C$. This means that $b\in C$, so if $2\cdot 3^{k}$ is the largest summand in the decomposition of $b$ in base $3$, then $2\cdot 3^{k}+b\not\in C$. (b) Let $a$ be a positive integer which is not a power of $3$, and $b$ a non-negative integer. We want to prove that $aC+b\not\subset C$. First notice that $aC+b\subset C$ is in fact equivalent to $aC\subset C$, so we can forget about the $b$. Also, we can assume that $a$ is not divisible by $3$. Finally, notice that the digits of $a$ in base $3$ must be $0,1$, for otherwise $2a$ would not belong to $C$. Since we assumed $a$ is not equal to $1$, it must be of the form $1+3^{k}+t\cdot 3^{k+1}$. This, however, means that $a\cdot(2+2\cdot 3^{k})$ does not belong to $C$, so we have our contradiction. (c) Let $a=3^{k}$, and $b\ge a$. As above, we want to show that $aC+b\not\subset C$. If $aC+b\subset C$, then $b\in C$. If $2\cdot 3^{u},\ u\ge k$ is the largest summand in the decomposition of $b$ in base $3$, then $2\cdot 3^{u}+2\cdot 3^{u}\not\in C$. This contradicts the fact that $aC+b\subset C$ because $2\cdot u\in aC$. Due to (a), (b), (c), we can interpret the problem purely combinatorially. What we want is to partition the set of sequences with terms $0,2$ (with only finitely many $2$'s) into "translations" of this set, i.e. sets of the form $S_{k}(u)$ where $k$ is a positive integer and $u$ is a $0,2$-sequence of length $k$, consisting of those $0,2$-sequences whose first $k$ digits are given by $u$. Of course, we can replace $0,2$ by $0,1$ respectively. When translated back into numbers, this time using base $2$, (d) becomes: Suppose we partition the set $\mathbb N$ of non-negative integers into progressions of the form $A_{i}=\{a_{i}m+b_{i}\ |\ m\ge 0\},\ i=\overline{1,n},\ n\ge 2$, with $1<a_{i}=2^{k_{i}}$ and $b_{i}<a_{i}$. If this partiton is primitive (in the sense described above by Omid), then it must be the partition into even and odd integers. Assume first that $k_{1}=\ldots=k_{t}<k_{t+1}\le\ldots\le k_{n}$. The progressions $A_{i}, i\ge t+1$ must cover a certain fixed residue class $r<2^{k_{1}}$ modulo $2^{k_{1}}$ which does not appear among the $A_{i}, i\le t$. Since each residue class modulo $2^{k_{i}}, i\ge t+1$ is contained in a single residue class modulo $2^{k_{1}}$, we find that the union of several of the progressions $A_{i}, i\ge t+1$ is precisely the progression $\{2^{k_{1}}m+r\ |\ m\ge 0\}$. This contradicts the primitivity of the pertition, and shows that in fact all $k_{i}$ must be equal. But now we split the progressions $\{2^{k_{i}}m+b_{i}\}$ into those which have even $b_{i}$ and those which have odd $b_{i}$. The union of the first group is the set of even integers, and the union of the second group is the set of odd integers. Since the partition is primitive, it must coincide with this one, and we're done.