A slip on an integer $n\geq 2$ is an operation that consists in choosing a prime divisor $p$ of $n$ and replacing $n$ by $\frac{n+p^2}{p}.$ Starting with an arbitrary integer $n\geq 5$, we successively apply the slip operation on it. Show that one eventually reaches $5$, no matter the slips applied.
Problem
Source: Centroamerican 2011, Problem 3
Tags: inequalities, number theory proposed, number theory
22.06.2011 04:52
Let $n=mp$, so $\dfrac {n+p^2} {p} = m+p$. Notice that $m+p \geq 1+2 = 3$; it can only be equal to $3$ when $m=1$, $p=2$, but then $n=2$; it can only be equal to $4$ when $m=1$, $p=3$, but then $n=3$, or else when $m=2$, $p=2$, but then $n=4$. Therefore, for as long as we apply the slip on an integer $n\geq5$, the result of the slip is also at least $5$. Now, the result $m+p$ of the slip obeys $m+p \leq n + 1$, since this is equivalent to $m+p \leq mp + 1$, or $(m-1)(p-1) \geq 0$. Equality only occurs for $m=1$, i.e. when $n$ is a prime; moreover, the equality $m+p = n$ cannot occur, since that would imply $(m-1)(p-1) =1$, thus $m=p=2$, therefore $n=4$, impossible, by the above paragraph. Let us finally notice that when $n$ is a prime larger than $5$, the slip produces $n+1$, and then a number strictly less than $n$, so the sequence of the iterated slips is decreasing, with the exception of an increase by one when hitting a prime, but then never hitting back that prime. Therefore, by the infinite descent principle, we must hit the value $5$, and thereafter the sequence alternates between the values $5$ and $6$.
01.07.2012 08:08
For $n=5$ it slips into $6$ and back into $5$.Let's assume that for any $n$ with $5<n \le k$ it eventually slips into $5$. For $n=k+1$ if $k + 1$ is composite then $k+1=ab$ with $a, b > 1$ then $k+1$ slips into $a+b$. We can say with full confidence $(a-1)(b-1) \ge 2$ because if one of them is $2$ the other one must be at least 3 since $ab \ge 6$. So multiplying the last expression we get $a+b \le ab-1=k$ so $6 \le a+b \le k$ so it slips into $5$. What if $k+1$ is prime, in that case it will slip into $k+2$ which is composite, let $k+2=cd$ doing the same that before $c, d>1$ we can say with confidence that $(c-1)(d-1) \ge 3$ because $cd-1$ is prime, so $dc>7$ if $d=2$ then $c$ is at least $4$ so solving the inequality we get $c+d \le cd-2=k$ so$6 \le c+d \le k$ so it slips into $5$
31.05.2013 01:29
Consider a number n = mp, where p is the prime used in the slip. Evidently, for every n, we can use a slip to turn it into n + 1 (we use 1 as p to get this result). Also, lets note that a slip is equivalent to just m + p. This can be verified solving a slip in terms of m and p. With the first result (n = n + 1, after applying a slip where p = 1), we conclude that for every n < 5 It´s posible to reach 5. Now, we need to prove that for n > 5, we can lower the number down to one number smaller than five, and then use the strategy of n + 1. For this, we use the second result (slip = m + p). Since, obviously, the product of m and p = n, and the sum of two positive integers is always smaller than the product of them (except when 1 is either m or p), m + p > n. Therefore, we can keep applying this strategy to lower down the number (n, n<5), and, eventually, reach an n, n < 5. Then we use the n = n + 1 strategy, and make the number reach 5. So, like that, we know every number can be turned into 5 using slips.