The positive integer $k$ and the set $A$ of distinct integers from $1$ to $3k$ inclusively are such that there are no distinct $a$, $b$, $c$ in $A$ satisfying $2b = a + c$. The numbers from $A$ in the interval $[1, k]$ will be called small; those in $[k + 1, 2k]$ - medium and those in $[2k + 1, 3k]$ - large. It is always true that there are no positive integers $x$ and $d$ such that if $x$, $x + d$, and $x + 2d$ are divided by $3k$ then the remainders belong to $A$ and those of $x$ and $x + d$ are different and are: a) small? $\hspace{1.5px}$ b) medium? $\hspace{1.5px}$ c) large? (In this problem we assume that if a multiple of $3k$ is divided by $3k$ then the remainder is $3k$ rather than $0$.)
Problem
Source: JBMO Shortlist 2020
Tags: Junior, Balkan, shortlist, 2020, number theory
Lukaluce
04.07.2021 18:22
This problem was proposed by Bulgaria
gnoka
09.07.2021 07:28
Lukaluce wrote: It is always true that there are no positive integers $x$ and $d$ such that if $x$, $x + d$, and $x + 2d$ are divided by $3k$ then the remainders belong to $A$ and those of $x$ and $x + d$ are different and are: a) small? $\hspace{1.5px}$ b) medium? $\hspace{1.5px}$ c) large? This is too hard to understand for me(and maybe sombody else). Strongly suggest you to use shorter sentences.
Sprites
09.07.2021 09:30
Lukaluce wrote: The positive integer $k$ and the set $A$ of distinct integers from $1$ to $3k$ inclusively are such that there are no distinct $a$, $b$, $c$ in $A$ satisfying $2b = a + c$. The numbers from $A$ in the interval $[1, k]$ will be called small; those in $[k + 1, 2k]$ - medium and those in $[2k + 1, 3k]$ - large. It is always true that there are no positive integers $x$ and $d$ such that if $x$, $x + d$, and $x + 2d$ are divided by $3k$ then the remainders belong to $A$ and those of $x$ and $x + d$ are different and are: a) small? $\hspace{1.5px}$ b) medium? $\hspace{1.5px}$ c) large? (In this problem we assume that if a multiple of $3k$ is divided by $3k$ then the remainder is $3k$ rather than $0$.) If $d=1$ it would work for $k \ge 3$ and $x>3k$ so the answer for all the cases would be no.
Lukaluce
11.07.2021 11:53
gnoka wrote: Lukaluce wrote: It is always true that there are no positive integers $x$ and $d$ such that if $x$, $x + d$, and $x + 2d$ are divided by $3k$ then the remainders belong to $A$ and those of $x$ and $x + d$ are different and are: a) small? $\hspace{1.5px}$ b) medium? $\hspace{1.5px}$ c) large? This is too hard to understand for me(and maybe sombody else). Strongly suggest you to use shorter sentences. I do not propose these problems, and it is not my duty nor right to alter the original texts. I did not translate this problem, I just copied the shortlist text word for word (in case that isn't clear).
sarjinius
24.10.2021 17:03
For a), let $k = 3$, $A = \{1, 2, 9\}$, $x = 2$, and $d = 8$.
Then the remainders of $x, x+d$, and $x+2d$ when divided by $3k$ are $2, 1$, and $9$ respectively. Since $2$ and $1$ are both small, then the answer is $\boxed{\text{no}}$.
For b), we will show that the answer is yes.
Assume the answer is no, so there exist integers $0 < x \le 3k$ and $0 < d < 3k$ that satisfy the above conditions (if $d = 3k$ then $x$ and $x+d$ will have the same remainders when divided by $3k$).
Case 1: $x+d \le 3k$.
Then since the remainders of $x$ and $x+d$ when divided by $3k$ are medium, $x, x+d \in [k+1, 2k]$ and $d < k$. Hence, $x+2d = (x+d)+d < 2k+k = 3k$. So $x, x+d, x+2d \in A$ and $2(x+d)=x+(x+2d)$, contradiction.
Case 2: $x+d > 3k$.
Then since the remainder of $x+d$ when divided by $3k$ is medium, $x+d \in [4k+1, 5k]$ and the remainder when $x+d$ is divided by $3k$ is $x+d-3k \in A$. Since $x \in [k+1, 2k]$, then $d = (x+d)-d \ge 4k+1-2k = 2k+1 > 2k$. Hence, $6k = 4k + 2k < (x+d) + d < 5k + 3k = 8k$, and the remainder when $x + 2d$ is divided by $3k$ is $x + 2d - 6k \in A$. Obviously, $x \in A$. So $x, x+d-3k, x+2d-6k \in A$ and $2(x+d-3k) = x + (x+2d-6k)$, contradiction.
Therefore, the answer to b) is $\boxed{\text{yes}}$.
For c), let $k = 3$, $A = \{1, 8, 9\}$, $x = 8$, and $d = 1$.
Then the remainders of $x, x+d$, and $x+2d$ when divided by $3k$ are $8, 9$, and $1$ respectively. Since $8$ and $9$ are both large, then the answer is $\boxed{\text{no}}$.