Farhad has made a machine. When the machine starts, it prints some special numbers. The property of this machine is that for every positive integer $n$, it prints exactly one of the numbers $n,2n,3n$. We know that the machine prints $2$. Prove that it doesn't print $13824$.
Problem
Source:
Tags: induction, combinatorics proposed, combinatorics
23.09.2010 18:16
27.09.2010 16:15
-Elixir- wrote:
I can see why you might do that in a competition if you were stuck, but why waste your time typing that out? haha Anyway, for brevity let $(i,j)$ denote $2^i\cdot 3^j$ and $S$ be the set of terms generated by the machine. Suppose all pairs $(i,j)\in S$, with $i+j\le 2k+1$, have an odd sum $i+j$. Then if there existed $(u,v)\in S$ with $u+v=2k+2$ then $(u-1,v)$ and $(u,v-1)\not \in S$ hence $(u-1,v-1)\in S$ but that contradicts out assumption. So all pairs in $S$ with sum less than $2k+3$ are odd. Now since $(1,0)\in S$ we have out base case and we conclude that all pairs in $S$ have odd sum. Since $13824 \equiv (9,3)$ and $9+3=12$ is even $13824 \not \in S$
24.02.2012 04:12
I believe 9 is in the set given that 3 and 6 are not so this contradicts your induction proof. I believe the error comes when u say (u-1,v) and (u,v-1) as it is possible that u or v is 0.
01.03.2012 18:22
It can be prove (by induction) that $(u,v) \in S$, iff $u - v \equiv 1(\bmod 3)$. As $13824 = {2^9}{3^3} \leftrightarrow (9,3)$, and $9 - 3\not \equiv 1(\bmod 3)$, so the machine doesn’t print $13824$.
04.09.2014 10:07
Any full and correct solution ?
24.01.2024 16:55
Sardor wrote: Any full and correct solution ? Hello, we use two lemmas: 1)If 6n is printed then n is printed as well. proof: since 6n is printed, 3n and 2n are not. since 2n and 3n are not printed n must be printed. 2) If 2n is printed, 8n is not printed and 16n is printed. proof: since 2n is printed, n and 3n are not. since 2n is printed, 4n and 6n are not printed. since 3n and 6n are not printed 9n is printed. since 9n is printed 18n and 27 are not. since 6n and 18n are not printed, 12n is printed. since 4n is not printed and 12n is printed, 8n is not printed. since 12n is printed 24n and 36n are not printed. since 8n and 24 are not printed 16n is printed . Now for the main question let's imagine 13284=2^9*3^3 is printed. using lemma 1 three times we get that 64 must be printed, but based on lemma two, and the fact that 2 is printed, 8*2=16 is printed therefore 4*16=64 is not printed. contradiction.