Initially, a natural number $n$ is written on the blackboard. Then, at each minute, Neymar chooses a divisor $d>1$ of $n$, erases $n$, and writes $n+d$. If the initial number on the board is $2022$, what is the largest composite number that Neymar will never be able to write on the blackboard?
Problem
Source: 2022 Brazilian National Mathematical Olympiad - Problem 4
Tags: number theory, combinatorics, Cool problem
22.11.2022 07:06
we have to find largest number over all possible $d$?... or first value is fixed nd we find the ans in terms of d????
22.11.2022 07:09
........
22.11.2022 07:13
i think u misread the problem like me at beginnin the problem says number which $cannot$ be written
22.11.2022 08:09
If $n>2022$ is the largest composite number that cannot be written on the board, notice that $n$ is odd and not a multiple of $2, 3$ or $5$ since $6|2022$ and $5|2022+3$ . Note that $n=2j+1=2(j-i)+2i+1$ for all $i$, let $2i+1\leq \sqrt{n}$ be a divisor of $n$ we have $2i+1|2j +1-2i-1=2(j-i)$, so if $j-i\geq 1011$ then $n$ can be written on the board as every pair greater than $2020$ appears. So $$n=2i+1+2(j-1)<2022+2i+1<2022+\sqrt{n}\Rightarrow n²-4045n+2022²<0 \Rightarrow \dfrac{4045-\sqrt{8089} }{2}<n< \dfrac{4045+\sqrt{8089}}{2}\Rightarrow$$ $2022<n\leq 2067$ But $2, 3, 5$ doesn't divide $n$ so $n\in \{2063, 2057, 2053, 2057, 2047, 2041, 2039, 2033, 2029, 2027, 2023 \}$. We have that $2063, 2053, 2039$ are prime and $2057=2\cdot 1023+11, 2051=2\cdot 1022+7, 2047=2\cdot 1012+23, 2041=2\cdot 1014+13$ so $n \leq 2033$, but $2033=2(1016-i)+2i+1$ with $2i+1|2033\Rightarrow 2i+1\geq 19 \Rightarrow i\geq 9 \Rightarrow 1016-i\leq 1011$, absurd, so $n=2033$.
22.11.2022 23:14
sol at contest: this number is $2033$. check that every composite number between $2033$ and $2066$ can be written (good luck). Suppose that exists $n > 2065$ that is composite and can't be written on the board. Let $p$ be a prime dividing $n$. Clearly $n$ and $p$ are odd, so $n-p$ is even $\Rightarrow n-p < 2022$, once if $n-p$ were greater than $2022$, $n$ could be written. Hence, $2065 < n < 2022 + p \Rightarrow p > 43 \Rightarrow p \geq 47$. Let $q$ be another prime dividing $n$ (if $n$ is a power of a prime, there's no problem in have $p = q$). Similarly, $q \geq 47$. Note that $pq-p \geq 47^2-47 \geq 2022$ and $pq - p$ it's an even number, so it can be written $\Rightarrow$ $pq$ can be written $\Rightarrow$ every multiple of $pq$ can be written $\Rightarrow$ $n$ can be written (contradiction) and we are done.
30.05.2023 13:00
levifb wrote: sol at contest: this number is $2033$. check that every composite number between $2033$ and $2066$ can be written (good luck). Suppose that exists $n > 2065$ that is composite and can't be written on the board. Let $p$ be a prime dividing $n$. Clearly $n$ and $p$ are odd, so $n-p$ is even $\Rightarrow n-p < 2022$, once if $n-p$ were greater than $2022$, $n$ could be written. Hence, $2065 < n < 2022 + p \Rightarrow p > 43 \Rightarrow p \geq 47$. Let $q$ be another prime dividing $n$ (if $n$ is a power of a prime, there's no problem in have $p = q$). Similarly, $q \geq 47$. Note that $pq-p \geq 47^2-47 \geq 2022$ and $pq - p$ it's an even number, so it can be written $\Rightarrow$ $pq$ can be written $\Rightarrow$ every multiple of $pq$ can be written $\Rightarrow$ $n$ can be written (contradiction) and we are done. What if $n-p=2033?$ or $n-p=2023?$
23.06.2023 03:05
lian_the_noob12 wrote: levifb wrote: sol at contest: this number is $2033$. check that every composite number between $2033$ and $2066$ can be written (good luck). Suppose that exists $n > 2065$ that is composite and can't be written on the board. Let $p$ be a prime dividing $n$. Clearly $n$ and $p$ are odd, so $n-p$ is even $\Rightarrow n-p < 2022$, once if $n-p$ were greater than $2022$, $n$ could be written. Hence, $2065 < n < 2022 + p \Rightarrow p > 43 \Rightarrow p \geq 47$. Let $q$ be another prime dividing $n$ (if $n$ is a power of a prime, there's no problem in have $p = q$). Similarly, $q \geq 47$. Note that $pq-p \geq 47^2-47 \geq 2022$ and $pq - p$ it's an even number, so it can be written $\Rightarrow$ $pq$ can be written $\Rightarrow$ every multiple of $pq$ can be written $\Rightarrow$ $n$ can be written (contradiction) and we are done. What if $n-p=2033?$ or $n-p=2023?$ if $n-p$ is odd, $p$ or $n$ is even. in both cases, $2 \mid n$ and $n > 2022$, so $n$ could be written.