Does there exist a set $A\subseteq\mathbb{N}^*$ such that for any positive integer $n$, $A\cap\{n,2n,3n,...,15n\}$ contains exactly one element? Please prove your conclusion.
Problem
Source: 2018 China Southeast MO Grade 10 P4
Tags: number theory
30.07.2018 08:57
30.07.2018 10:08
Same idea with very recent Poland 2017.
30.07.2018 13:10
MarkBcc168 wrote:
Hello, may I ask how you found this?
03.08.2018 08:13
NikoIsLife wrote: MarkBcc168 wrote:
Hello, may I ask how you found this? Same question. Whats your motivation?
03.08.2018 12:36
Here is a full solution with motivation. Such set exists. To construct it, define function $f:\mathbb{N}\to\mathbb{N}$ by $$f(n) = \nu_2(n) + 4\nu_3(n) + 9\nu_5(n) + 11\nu_7(n) + 7\nu_{11}(n) + 14\nu_{13}(n).$$The merit of this function is $f(ab) = f(a)+f(b)$ for any $a,b$. Moreover, it's easy to verify that $\{f(1),f(2),...,f(15)\} = \{0,1,2,...,14\}$. Take $A = \{n\mid f(n)\equiv 0\pmod{15}\}$. By the above observation, $\{f(n), f(2n), ..., f(15n)\}$ is the set of $15$ consecutive integers. Hence exactly one of them is divisible by $15$, implying the conclusion. Motivation The construction seems intimidating. But these numbers come from attempting to define more general form of $f$. $$f(n) = a\nu_2(n) + b\nu_3(n) + c\nu_5(n) + d\nu_7(n) + e\nu_{11}(n) + f\nu_{13}(n).$$It's easy to see that we need the following numbers to be distinct in modulo $15$. $$a, 2a, 3a, b, 2b, c, d, e, f, a+b, a+c, a+d, b+d, 2a+b$$and I have to pick $a, b, c, d, e, f$. My strategy is to pick the smallest $a, b, c, d, e, f$ which works in that order. It worked out in the first attempt, resulting in above construction.
03.08.2018 13:18
Actually in grade 11 edition,this also requires to have infinite integer $a$ such that $a$ and $a+2018$ are both in the set.That's also not difficult.
03.08.2018 16:45
MarkBcc168 wrote: It's easy to see that we need the following numbers to be distinct in modulo $15$. $$a, 2a, 3a, b, 2b, c, d, e, f, a+b, a+c, a+d, b+d, 2a+b$$resulting in above construction. Why?
09.07.2022 12:19
GorgonMathDota wrote: MarkBcc168 wrote: It's easy to see that we need the following numbers to be distinct in modulo $15$. $$a, 2a, 3a, b, 2b, c, d, e, f, a+b, a+c, a+d, b+d, 2a+b$$resulting in above construction. Why? Because this function can tell us that there is only one in A and that's what the problem need us to do.