https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Umtympswede&feedformat=atom AoPS Wiki - User contributions [en] 2022-09-28T02:24:29Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=1983_IMO_Problems/Problem_5&diff=122416 1983 IMO Problems/Problem 5 2020-05-15T15:12:13Z <p>Umtympswede: /* Solution */</p> <hr /> <div>==Problem 5==<br /> Is it possible to choose &lt;math&gt;1983&lt;/math&gt; distinct positive integers, all less than or equal to &lt;math&gt;10^5&lt;/math&gt;, no three of which are consecutive terms of an arithmetic progression? Justify your answer.<br /> <br /> ==Solution==<br /> The answer is yes. We will construct a sequence of integers that satisfies the requirements.<br /> <br /> Take the following definition of &lt;math&gt; a_n &lt;/math&gt;: &lt;math&gt; a_n &lt;/math&gt; in base 3 has the same digits as &lt;math&gt; n &lt;/math&gt; in base 2. For example, since &lt;math&gt; 6=110_2 &lt;/math&gt;, &lt;math&gt;a_6=110_3=12&lt;/math&gt;.<br /> <br /> First, we will prove that no three &lt;math&gt;a_n&lt;/math&gt;'s are in an arithmetic progression. Assume for sake of contradiction, that &lt;math&gt; i &lt; j &lt; k&lt;/math&gt; are numbers such that &lt;math&gt; 2a_j=a_i + a_k &lt;/math&gt;. Consider the base 3 representations of both sides of the equation. Since &lt;math&gt; a_j &lt;/math&gt; consists of just 0's and 1's in base three, &lt;math&gt;2a_j&lt;/math&gt; consists of just 0's and 2's base 3. No whenever &lt;math&gt;2a_j&lt;/math&gt; has a 0, both &lt;math&gt;a_i&lt;/math&gt; and &lt;math&gt;a_k&lt;/math&gt; must have a 0, since both could only have a 0 or 1 in that place. Similarly, whenever &lt;math&gt;2a_j&lt;/math&gt; has a 2, both &lt;math&gt;a_i&lt;/math&gt; and &lt;math&gt;a_k&lt;/math&gt; must have a 1 in that place. This means that &lt;math&gt;a_i=a_k&lt;/math&gt;, which is a contradiction.<br /> <br /> Now since &lt;math&gt; 1983=11110111111_2 &lt;/math&gt;, &lt;math&gt;a_{1983} = 11110111111_3 &lt; \frac{3^{11}}{2} &lt; 10^5 &lt;/math&gt;. Hence, the set &lt;math&gt;\{a_1,a_2,...a_{1983}\}&lt;/math&gt; is a set of 1983 integers less than &lt;math&gt; 10^5 &lt;/math&gt; with no three in arithmetic progression.</div> Umtympswede https://artofproblemsolving.com/wiki/index.php?title=1983_IMO_Problems/Problem_5&diff=122415 1983 IMO Problems/Problem 5 2020-05-15T15:08:09Z <p>Umtympswede: /* Solution */</p> <hr /> <div>==Problem 5==<br /> Is it possible to choose &lt;math&gt;1983&lt;/math&gt; distinct positive integers, all less than or equal to &lt;math&gt;10^5&lt;/math&gt;, no three of which are consecutive terms of an arithmetic progression? Justify your answer.<br /> <br /> ==Solution==<br /> The answer is yes. We will construct a sequence of integers that satisfies the requirements.<br /> <br /> Take the following definition of &lt;math&gt; a_n &lt;/math&gt;, &lt;math&gt; a_n &lt;/math&gt; in base 3 has the same digits as &lt;math&gt; n &lt;/math&gt; in base 2. For example, since &lt;math&gt; 6=110_2 &lt;/math&gt;, &lt;math&gt;a_n=110_3=12&lt;/math&gt;.<br /> <br /> First, we will prove that no three &lt;math&gt;a_n&lt;/math&gt;'s are in an arithmetic progression. Assume for sake of contradiction, that &lt;math&gt; i &lt; j &lt; k&lt;/math&gt; are numbers such that &lt;math&gt; 2a_j=a_i + a_k &lt;/math&gt;. Consider the base 3 representations of both sides of the equation. Since &lt;math&gt; a_j &lt;/math&gt; consists of just 0's and 1's in base three, &lt;math&gt;2a_j&lt;/math&gt; consists of just 0's and 2's base 3. No whenever &lt;math&gt;2a_j&lt;/math&gt; has a 0, both &lt;math&gt;a_i&lt;/math&gt; and &lt;math&gt;a_k&lt;/math&gt; must have a 0, since both could only have a 0 or 1 in that place. Similarly, whenever &lt;math&gt;2a_j&lt;/math&gt; has a 2, both &lt;math&gt;a_i&lt;/math&gt; and &lt;math&gt;a_k&lt;/math&gt; must have a 1 in that place. This means that &lt;math&gt;a_i=a_k&lt;/math&gt;, which is a contradiction.<br /> <br /> Now since &lt;math&gt; 1983=11110111111_2 &lt;/math&gt;, &lt;math&gt;a_{1983} = 11110111111_3 &lt; \frac{3^{11}}{2} &lt; 10^5 &lt;/math&gt;. Hence the set &lt;math&gt;\{a_1,a_2,...a_{1983}\}&lt;/math&gt; is a set of 1983 integers with no three in arithmetic progression.</div> Umtympswede https://artofproblemsolving.com/wiki/index.php?title=1977_IMO_Problems/Problem_6&diff=121652 1977 IMO Problems/Problem 6 2020-04-25T17:25:27Z <p>Umtympswede: Created page with &quot;= Problem = Let &lt;math&gt;f(n)&lt;/math&gt; be a function &lt;math&gt;f: \mathbb{N}^{+}\to\mathbb{N}^{+}&lt;/math&gt;. Prove that if &lt;cmath&gt; f(n+1) &gt; f(f(n)) &lt;/cmath&gt; for each positive integer &lt;mat...&quot;</p> <hr /> <div>= Problem =<br /> Let &lt;math&gt;f(n)&lt;/math&gt; be a function &lt;math&gt;f: \mathbb{N}^{+}\to\mathbb{N}^{+}&lt;/math&gt;. Prove that if &lt;cmath&gt; f(n+1) &gt; f(f(n)) &lt;/cmath&gt; for each positive integer &lt;math&gt;n&lt;/math&gt;, then &lt;math&gt;f(n)=n&lt;/math&gt;.<br /> = Solution =<br /> We will prove this via induction. First we will prove there is a &lt;math&gt;t&lt;/math&gt; such that &lt;math&gt;f(t)=1&lt;/math&gt; and then that &lt;math&gt;t=1&lt;/math&gt; is the only such solution.<br /> <br /> Define the sequence &lt;math&gt;a_n&lt;/math&gt; with &lt;math&gt;a_0&gt;1&lt;/math&gt; for &lt;math&gt;a_0\in \mathbb{N} &lt;/math&gt; and &lt;math&gt;a_k=f(a_{k-1}-1)&lt;/math&gt;. By the given inequality we have that &lt;math&gt;f(a_n)&gt;f(a_{n+1})&lt;/math&gt;, this can be used to form a inequality chain of decreasing positive integers: &lt;cmath&gt; f(a_0)&gt;f(a_1)&gt;f(a_2)&gt;...&lt;/cmath&gt;<br /> By [[Infinite Descent]], this sequence must terminate, and the only way it can terminate is if we input something into &lt;math&gt;f&lt;/math&gt; that is outside of its range. This can only happen if &lt;math&gt;a_n=1&lt;/math&gt; since the range and domain of &lt;math&gt;f&lt;/math&gt; are the positive integers. Since &lt;math&gt;a_0\neq 1&lt;/math&gt;, there is a integer &lt;math&gt;t&lt;/math&gt; (&lt;math&gt;a_{n-1}-1&lt;/math&gt;) such that &lt;math&gt;f(t)=1&lt;/math&gt;.<br /> <br /> Now if &lt;math&gt;t\neq 1&lt;/math&gt;, then &lt;math&gt;f(t)=1&gt;f(f(t-1))&lt;/math&gt;, which is impossible since &lt;math&gt;f(f(t-1))\ge 1&lt;/math&gt; by the range of &lt;math&gt;f&lt;/math&gt;, so we have &lt;math&gt;t=1&lt;/math&gt; is the only time when &lt;math&gt;f(t)=1&lt;/math&gt;.<br /> <br /> Now for the inductive step.<br /> <br /> Assume that &lt;math&gt;f(n)=n&lt;/math&gt; for all &lt;math&gt;n&lt;k&lt;/math&gt; and these are the only times these values occur. We will prove that &lt;math&gt;f(k)=k&lt;/math&gt; and that this is the only time this value occurs. Define the sequence &lt;math&gt;a_n&lt;/math&gt; similarly, except that &lt;math&gt;a_0&gt;k&lt;/math&gt;, by the reasoning above, there is a &lt;math&gt;a_m&lt;/math&gt; such that &lt;math&gt;f(a_m)=1&lt;/math&gt;, by the inductive assumption, this means that &lt;math&gt;a_m=f(a_{m-1}-1)=1&lt;/math&gt;, we can repeat the inductive assumption to get that &lt;math&gt;a_{m-k+1}=k&lt;/math&gt;. This implies that &lt;math&gt;f(a_{m-k}-1)=k&lt;/math&gt;. Thus, there is a &lt;math&gt;t&lt;/math&gt; such that &lt;math&gt;f(t)=k&lt;/math&gt;.<br /> <br /> Now for that &lt;math&gt;t&lt;/math&gt;, we have &lt;math&gt;k&gt;f(f(t-1))&lt;/math&gt;, which means that &lt;math&gt;k+1&gt;t&lt;/math&gt; by the inductive assumption which implies &lt;math&gt;t=k&lt;/math&gt; since we must have &lt;math&gt;t&gt;k-1&lt;/math&gt;, otherwise &lt;math&gt;f(t)&lt;k&lt;/math&gt;. So &lt;math&gt;t=k&lt;/math&gt; is the only time when &lt;math&gt;f(t)=k&lt;/math&gt;<br /> <br /> So the inductive step is complete. Therefore, by induction &lt;math&gt;f(n)=n&lt;/math&gt; for all positive integers &lt;math&gt;n&lt;/math&gt;.</div> Umtympswede