3-digit palindrome and binary expansion \overline {xyx}

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

3-digit palindrome and binary expansion \overline {xyx}

G H J

Reveal topic tags

binary representation

L

G H BBookmark kLocked kLocked NReply

Source: RMM Shortlist 2017 N2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

30651 posts

#1 h Jul 4, 2019, 7:46 PM • 4 Y

Y by jhu08, Sprites, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

41 posts

dzy47

#2 h Aug 5, 2021, 3:16 PM • 2 Y

Y by jhu08, Sprites

BUMP ON THIS!Anyone has a solution?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#3 h Oct 21, 2021, 4:08 PM

Y by

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$

This post has been edited 11 times. Last edited by Sprites, Oct 24, 2021, 4:31 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

701 posts

#4 h Oct 21, 2021, 4:44 PM • 1 Y

Y by Sprites

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?

This post has been edited 4 times. Last edited by cadaeibf, Oct 21, 2021, 7:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

892 posts

#5 h Oct 23, 2021, 1:30 PM • 1 Y

Y by Sprites

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathematics2004

82 posts

mathematics2004

#6 h Oct 23, 2021, 2:41 PM • 1 Y

Y by Sprites

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#7 h Apr 10, 2025, 4:17 AM

Y by

any other $\huge\huge{solution?}$

This post has been edited 1 time. Last edited by imzzzzzz, Apr 10, 2025, 4:18 AM
Reason: fix

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a