Let $S$ be a set, such that for every positive integer $n$, we have $|S\cap T|=1$, where $T=\{n,2n,3n\}$. Prove that if $2\in S$, then $13824\notin S$.
Problem
Source: Brazil EGMO TST 2021 #5
Tags: number theory, combinatorics, geometry, 3D geometry
04.03.2021 22:41
We know $13824=2^9\cdot 3^3$. We now claim $2^k3^{\ell}\in S$ if and only if $k-\ell\equiv 1\pmod 3$. We can induct on $k+\ell$, with $k+\ell\leq 1$ being clear (considering $T=\{1,2,3\}$ suffices). Now, assume first $k-\ell\equiv 1\pmod 3$ and $\ell\geq 2$. Then, we can let $n=2^k3^{\ell-2}\not\in S$. Note $2n\in S$, implying $n,3n\not\in S$. This also implies $6n\not\in S$, implying $9n\in S$, which is as desired. Otherwise, assume $k\geq 2$ and $k-\ell\equiv 1\pmod 3$. Then we can let $n=2^{k-2}\ell\not\in S$. Note $3n\in S$, implying $2n,6n\not\in S$. This finally implies $4n\in S$, as desired. The remaining case is $k=\ell=1$, which does not satisfy $k-\ell\equiv 1\pmod 3$. Now to finish, we can note that if $n\in S$, $\frac 23n,\frac 32n\not\in S$, proving sufficiency of the criteria.
05.03.2021 19:46
It was Iranian 2nd round https://artofproblemsolving.com/community/c6h368221p2026700
29.06.2021 21:08
mathisreal wrote: Let $S$ be a set, such that for every positive integer $n$, we have $|S\cap T|=1$, where $T=\{n,2n,3n\}$. Prove that if $2\in S$, then $13824\notin S$. Claim 1-: if for some $t>0$ $2^k\times 3^t\in S\leftrightarrow 2^{l-1}\times 3^{t-1}\in S$ and similarly if for some $t>0$ $2^k\times 3^t\not\in S\leftrightarrow 2^{k-1}\times 2^{t-1}\not\in S$ Proof-: if $2^k\times 3^t\in S$ for some $t>0$ then as $T=\{n,2n,3n\}$ we can choose $n=2^k\times 3^{t-1},n=2^{k-1}\times 3^t$ and get that $\{2^{k-1}\times 3^t,2^k\times 3^{t-1}\}\not\in S$ and then By choosing $n=2^{k-1}3^{t-1}$ we can clearly see $2^{k-1}\times 3^{t-1}\in S$. Similarly if $2^{k-1}\times 3^{t-1}\in S\implies \{2^{k}\times 3^{t-1},2^{k-1}\times 3^{t}\}\not\in S\implies 2^k\times 3^t\in S$ If $2^k\times 3^t\not\in S$ then any 1 of $\{2^{k-1}\times 3^t, 2^t\times 3^{t-1}\}$ must belong to $S$ Then clearly $2^{k-1}\times 3^{t-1}\not \in S$ and vice versa holds. Claim 2-: if $2\in S$ then $2^6\not\in S$ Proof-: Just observe $2\in S\implies 3\not\in S, 6\not\in S\implies 9\in S\implies 18\not\in S$ and as $6\not\in S\implies 12\in S\implies 8\not \in S,24\not\in S\implies 2^4\times 3^2\not\in S$ and $2^4\in S$ Combining both gives $2^5\times 3\in S\implies 2^6\not\in S$ Now assume the contrary that $13824=2^9\times 3^3\in S$ then claim 1 gives $2^6\in S$ which is a contradiction by Claim $2$ as $2\in S$ $\blacksquare$
23.09.2021 17:54
We call a number good if it belongs to $S$ and bad otherwise. Claim: If $(2^a.3^b)$,where $a$ is at least $1$, is good ,then so is $(2^{a-1}.3^{b+2})$. If $(2^a.3^b)$ is good ,then $(2^a.3^{b+1})$ and $(2^{a-1}.3^{b+1})$ are bad ,which gives the desired. Claim:$(2^{a+3}.3^a)$ and $(2^{a+2}.3^a)$ are bad for every non-negative $a$. It is true for $a=0$, thereafter if $(2^{a+3}.3^a)$ and $(2^{a+2}.3^a)$ are bad, then $(2^{a+2}.3^{a+1})$ is good,and so $(2^{a+3}.3^{a+1})$ is bad and also that now,$(2^{a+4}.3^a)$ is good which gives that $(2^{a+4}.3^{a+1})$ is bad and hence we are done by induction. Now, we assume the contrary , so $2^9.3^3$ is good, which gives that $2^8.3^5$ is good but that is a contradiction.