Let $x, y$ and $k$ be three positive integers. Prove that there exist a positive integer $N$ and a set of $k + 1$ positive integers $\{b_0,b_1, b_2, ... ,b_k\}$, such that, for every $i = 0, 1, ... , k$ , the $b_i$-ary expansion of $N$ is a $3$-digit palindrome, and the $b_0$-ary expansion is exactly $\overline{\mbox{xyx}}$. proposed by Bojan Basic, Serbia
Problem
Source: RMM Shortlist 2017 N2
Tags: number theory, palindromes, binary representation
05.08.2021 18:16
BUMP ON THIS!Anyone has a solution?
21.10.2021 19:08
Yet another construction:- Choose \begin{align*} N \equiv b_1(x-20) \pmod {b_1^2+1} \\.\\.\\.\\.\\.\\.\\.\\.\\.\\.\\ N \equiv b_k(x-20) \pmod {b_k^2+1} \end{align*}Notice that $$N = b_k (x-20)+(k^2+1)$$since obviously we can select $n$ such that \begin{align*} n^2 \equiv -1 \pmod {b_1^2+1} \\.\\.\\.\\.\\.\\.\\.\\.\\.\\.\\ n^2 \equiv -1 \pmod {b_k^2+1} \\ q_1,.....,q_{\tau(n^2+1)}|n^2+1 \implies \prod_{j=1}^{\tau(n^2+1)-1} q_j \equiv 1 \pmod {q_{\tau(n^2+1)}} \end{align*}hence $$ \left( \overline{N} \right)_{q_{\tau(n^2+1)}}=xyx$$
21.10.2021 19:44
Quote: suppose that it works for $k=n$ and at the $n+1$th step increase all the $b_i$ to sufficiently large number $a_i$ Why can you substitute the $b_i$ with some (aribtrarily large) $a_i$ which still preserve the equality between the $n$ expressions? How can you pick the new $x_{i,1},x_{i,2}$ given the new $a_i$s? Did you prove that the system (with $n$ fixed from the induction hypothesis) has infinitely many, and thus arbitrarily large, solutions?
23.10.2021 16:30
Problem is to prove there exist as many as we want $a$ which satisfies $(b_0^2+1)x+b_0y=(a^2+1)z+at$ and there is at least one $(z,t)$ with $z,t \le a-1$. Any solution? How can I find the official solutions?
23.10.2021 17:41
Here is the official solution (copied verbatim). Solution. We provide a general construction which may be specified in many different ways. To start, we choose some distinct positive integers $d_1, d_2, \ldots , d_k$ satisfying the following conditions: (i) each of them is coprime with $x$; (ii) $d_i > 100(x + y)$ for all $i$; and (iii) the number $L = \text{lcm}(d_1 + 1, d_2 + 1, \ldots , d_k + 1)$ is coprime with $D = d_1d_2 \cdots d_k$. Such $k$-tuples of numbers exist; for instance, one may choose $d_i=2^{p_i}-1$, where $p_i$ are distinct large primes. Another option is to choose some large odd $d_1$ coprime with $x$, and then proceed inductively by setting $d_{i+1} = xd_1(d_1 + 1)d_2(d_2 + 1) \cdots d_i(d_i + 1) + 1$. Since $gcd(xL, D) = 1$, the multiples of $xL$ represent all residue classes modulo $D$; in particular, there exists a positive integer $m$ such that $xLm \equiv -y \pmod D$. Set $B = Lm$. Finally, we define \[ b_0=B, ~ c_i =\frac{B}{d_i + 1}, ~ b_i=d_ic_i=B-c_i, ~ \text{and}~ N = \overline{xyx}_B = x(B^2 + 1) + yB. \]We claim that these values satisfy all the requirements; moreover, for every $i = 1, \cdots , k$ the $b_i$-ary representation of $N$ has three digits, starting and ending with $x$. To show this, notice that for every $i \in \{1, 2, \ldots , k \}$ we have \[ N = x(d_i + 1)^2 c_i^2+y(d_i + 1)c_i + x = (x \cdot (d_ic_i)^2 + x)+ (2c_ix + y) \cdot (d_ic_i) + (xc_i^2+yc_i). \]Clearly, $x$ is a $b_i$-ary digit, since $b_i \ge d_i > x$. Denote $\ell_i = (2c_ix + y) \cdot (d_ic_i)$ and $r_i = xc_i^2 + yc_i$. Now it remains to prove that the number $\ell_i + r_i$ is divisible by $b_i = d_ic_i$, and that $\ell_i + r_i < b_i^2$. Notice that \[ xc_i + y = \frac{xB + y(d_i + 1)}{d_i + 1}=\frac{(xB + y) + d_iy}{d_i + 1}. \]The numerator of the last fraction is divisible by $d_i$ (due to the choice of $B$), and the denominator is coprime with $d_i$; so $d_i | xc_i + y$. Thus $bi = d_ic_i | r_i$; set $r_i = b_iq_i$. Notice that $q_i \le xc_i + y$. Hence, $\ell_i+r_i = b_i(2c_ix+y+q_i)$, where $0 \le 2c_ix+y+q_i \le 3c_ix+2y < 100c_i(x+y) < c_id_i = b_i$. Thus the $b_i$-ary expansion of $N$ is a palindrome of the form $N = \overline{x(2c_ix + y + q_i)x}_{b_i}$.