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
-Elixir-
23.09.2010 18:16
The printer prints 2, so it does not print 1 or 3.
Also, it does not print 4 or 6.
Hence, it prints 9.
It does not print 18 or 27, so it prints 12.
From that it does not print 8.
It prints 12, so it does not print 24 or 36.
Thus, it prints 16.
From that, it does not print 32 or 48.
Thus, it prints 72.
It does not print 144 or 216.
Thus, it prints 96.
It does not print 64.
It does not print 192.
Hence it prints 128.
It does not print 256 or 384.
It prints 576.
It does not print 288 or 864.
It prints 432.
It does not print 1152.
It does not print 216 or 648.
It does not print 864 or 1296.
It prints 1944.
It does not print 3888 or 5832.
It does not print 1728.
It prints 2592.
It does not print 5184 or 7776.
It prints 768.
It does not print 1536 or 2304.
It prints 3456.
It does not print 6912 or 10368.
It prints 4608.
It does not print 9216 or 13824.
ocha
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$
peregrinefalcon88
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.
yunxiu
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$.
Sardor
04.09.2014 10:07
Any full and correct solution ?
AgentC
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.