The board has a natural number greater than $1$. At each step, Igor writes the number $n +\frac{n}{p}$ instead of the number $n$ on the board , where $p$ is some prime divisor of $n$. Prove that if Igor continues to rewrite the number infinite times, then he will choose infinitely times the number $3$ as a prime divisor of $p$.
HIDE: original wording На доске записано какое-то натуральное число, большее 1. На каждом шагу Игорь переписывает имеющееся на доске число n на число n +n/p, где p - это какой-нибудь простой делитель числа n. Доказать, что если Игорь будет продолжать переписывать число бесконечно долго, то он бесконечно много раз выберет в качестве простого делителя p число 3.Problem
Source: 2021 Estonia TST 2.1
Tags: combinatorics, number theory
Jalil_Huseynov
03.01.2022 12:37
It should be $n+\frac{n}{p}$ instead of $n+\frac{p}{n}$. Also at the end divisor of $n$ instead of $p$
gghx
03.01.2022 12:58
parmenides51 wrote: The board has a natural number greater than $1$. At each step, Igor writes the number $n +\frac{n}{p}$ instead of the number $n$ on the board , where $p$ is some prime divisor of $n$. Prove that if Igor continues to rewrite the number infinite times, then he will choose infinitely times the number $3$ as a prime divisor of $p$.
На доске записано какое-то натуральное число, большее 1. На каждом шагу Игорь переписывает имеющееся на доске число n на число n +n/p, где p - это какой-нибудь простой делитель числа n. Доказать, что если Игорь будет продолжать переписывать число бесконечно долго, то он
бесконечно много раз выберет в качестве простого делителя p число 3.
I think this is correct, but I may be hallucinating...
Suppose for some $n$, Igor never has to use 3. (This is equivalent to the original problem).
Consider all the prime divisors of $n$ stored in a list.
1. If we take $p=2$, we remove 2 from the list and add in 3. (in particular, Igor cannot at some point only use 2s, and will have to use some other prime infinitely more times).
2. If we take any $p>3$, we remove $p$ from the list and add in all the prime divisors of $p+1$, which are strictly less than $p$.
Note that we never touch $3$ by assumption.
1 and 2 lead to a contradiction.
@below thanks for confirming . My brain is not working very well today.
Jalil_Huseynov
03.01.2022 13:04
gghx wrote: parmenides51 wrote: The board has a natural number greater than $1$. At each step, Igor writes the number $n +\frac{n}{p}$ instead of the number $n$ on the board , where $p$ is some prime divisor of $n$. Prove that if Igor continues to rewrite the number infinite times, then he will choose infinitely times the number $3$ as a prime divisor of $p$.
На доске записано какое-то натуральное число, большее 1. На каждом шагу Игорь переписывает имеющееся на доске число n на число n +n/p, где p - это какой-нибудь простой делитель числа n. Доказать, что если Игорь будет продолжать переписывать число бесконечно долго, то он
бесконечно много раз выберет в качестве простого делителя p число 3.
I think this is correct, but I may be hallucinating...
Suppose for some $n$, Igor never has to use 3. (This is equivalent to the original problem).
Consider all the prime divisors of $n$ stored in a list.
1. If we take $p=2$, we remove 2 from the list and add in 3. (in particular, Igor cannot at some point only use 2s, and will have to use some other prime infinitely more times).
2. If we take any $p>3$, we remove $p$ from the list and add in all the prime divisors of $p+1$, which are strictly less than $p$.
Note that we never touch $3$ by assumption.
1 and 2 lead to a contradiction.
You are right, it's not hallucinating
IAmTheHazard
25.04.2022 22:02
This is Ukraine TST 2021/4 not Estonia TST (the original wording is certainly not in Estonian) maybe wrong? It suffices to show that for any $n$, we have to pick $3$ at least once. Suppose we never pick $3$ for some $n$, so we have to pick some prime $p$ infinitely many times. If $p=2$, then we strictly decrease the $\nu_2$ of the written number every time, and we only increase it when we pick a $p>3$. Further, we can only ever decrease the largest prime divisor by picking $p>3$, so we have to pick some $p>3$ infinitely many times. Doing this decreases the $\nu_p$ of the written number, and the only way we can increase the $\nu_p$ of the written number is by picking a prime greater than $p$. Hence if we pick some $p>3$ infinitely many times, we also have to pick some prime $q>p$ infinitely many times, but this is impossible as there are finitely many primes which we can ever pick. Hence $3$ must be picked at least once, done. $\blacksquare$
parmenides51
26.04.2022 00:37
IAmTheHazard wrote: This is Ukraine TST 2021/4 not Estonia TST (the original wording is certainly not in Estonian) as you may see in my source here, it is indeed 2021 Estonia TST 2.4 and not 2.1