We say a natural number is good if it has an even number of different prime divisors. Prove there's infinitely many numbers $n$ such that ${n,n+1,n+2,n+3}$ contains exactly $2$ good numbers.
Hi guys, I found this question in an Olympiad problem set. It doesn't say what contest it's from, but I'm pretty sure it's somewhere near state level. Here's my work so far.
We can prove there's infinitely many numbers with an even number of different prime divisors by assuming the opposite. Let's assume there's a finite number of numbers with an even number of different prime divisors. Lets take the maximum of those numbers and say it's $x$. We can take primes $p,q$ such that they're bigger than $x$ and the number $x\cdot p\cdot q$ will also have an even number of prime divisors and be bigger than $x$, therefore we have a contradiction.
After this, I looked at assuming that $n$ is a good number and looking at what that means for the other three numbers. If we assume $n$ is even (which we can using a similiar proof like the one above, but for even numbers exclusively) and the other $3$ aren't good we know that numbers $2\cdot n$ and $2\cdot (n+1)$ will be good. So the group ${2\cdot n, 2\cdot n + 1, 2\cdot n + 2,2\cdot n + 3}$ will have atleast $2$ good numbers. I'm not sure where to go from here, any help is appreciated, thanks!
Best Answer
Let $h(n)$ count how many good numbers are in $\{n,n+1,n+2,n+3\}$. Then $h(n)$ is a natural number between $0$ and $4$, and furthermore, the difference between $h(n+1)$ and $h(n)$ is at most $1$ (when passing from $\{n,n+1,n+2,n+3\}$ to $\{n+1,n+2,n+3,n+4\}$, we lose at most one good number and gain at most one).
The main property of such functions is that "discrete intermediate value theorem" holds for them – for any $a<b$ every natural number in the interval $[h(a),h(b)]$ is attained as some $h(c)$ with $c \in [a,b]$. This is very intuitive – as in each step $h$ changes by at most $1$, we cannot jump over $h(c)$.
In particular, using your reasoning, if we have even $n$ which is good, and with $h(n)=1$, then $h(2n) \geqslant 2$, so there is at least one $m \in [n,2n]$ with $h(m)=2$. This is already half of the problem – if we had only finitely many $n$ with $h(n)=2$, then for large enough $n$ we need to have either $h(n) \leqslant 1$ or $h(n) \geqslant 3$. The first case follows from your solution, and you can try to solve the other one in a similar fashion – you take some particular large $n$, and you try to produce some number with $h(m) \leqslant 2$.