Let $N$ be a positive integer with $2k$ digits. Its chunks are defined by the two numbers formed by the digits from $1$ to $k$ and $k+1$ to $2k$ (e.g. the chunks of 142856 are 142 and 856). We define the $N$-reverse as the number formed by switching its chunks (e.g. the reverse of 142856 is 856142 and for 1401 it is 114). We call a number cearense is it satisfies the following conditions: Has an even number of digits Its chunks are relatively prime Divides its reverse Find the two smallest cearense integer.
Problem
Source: Cono Sur 2024/P4
Tags:
29.09.2024 03:15
? what happened here?
29.09.2024 03:23
very interesting thread title $\phantom{for reference, it is currently "NT hand job"}$
29.09.2024 03:38
aidan0626 wrote: very interesting thread title $\phantom{for reference, it is currently "NT hand job"}$ It really takes a lot of hand work
29.09.2024 06:12
The answer is $11$ and $142857$, respectively, which clearly work (the latter because $142857 \cdot 6 = 857142$). Clearly $11$ is the smallest such number, so we now show the second smallest is $142857$. Assume $N > 11$. Let $a,b$ be the chunks. We have $N = 10^k a + b$ and $\gcd(a,b) = 1$. Thus, \[ 10^k a + b \mid 10^k b + a\] This implies $10^k a + b \mid 10^k b + a + 10^k a + b = (10^k + 1)(a + b)$, so $10^k a + b$ divides \[ (10^k + 1) (10^k a + b) - (10^k + 1)(a + b) = (10^{2k} - 1) a\]Note that $\gcd(10^k a + b, a) = 1$ (as $a,b$ are relatively prime), so \[ N = 10^k a + b \mid 10^{2k} - 1,\]which indeed is a necessary and sufficient condition, as we can reverse our steps. Claim: $k > 1$ Then $N \mid 10^2 - 1 = 99$ and $N$ is a two digit number. Since $N > 11$, $N \in \{33,99\}$, but those clearly don't satisfy the relatively prime condition, so $k > 1$. $\square$ Claim: $k > 2$ Then $N \mid 10^4 - 1 = 9999$ and $N$ has four digits. The only four digit divisors of $9999$ are $1111, 3333, 9999$ (the proof of this being that the only divisors of $9999$ less than $10$ are $1, 3, $ and $9$), but none of these satisfy the relatively prime condition, so $k > 2$. $\square$ Claim: $142857$ is the only possible solution for $k = 3$ Proof: If $k = 3$, then $N \mid 10^6 - 1 = 999999$ and $N$ has six digits. Hence $\frac{999999}{N} \le 9$. The only divisors of $999999$ less than or equal to $9$ are $1, 3, 7, 9$, but $\frac{999999}{N} \in \{1,3,9\}$ obviously do not satisfy the relatively prime condition. Hence $N = \frac{999999}{7} = 142857$, as desired. $\square$ Since $k \ge 3$ for all solutions except $11$, and $k = 3$ has a solution of $142857$ only, the second smallest solution must be $142857$.
29.09.2024 12:18
Nice problem, but why not ask for the third smallest $N$? Only then one is forced to think systematically about the problem...
30.09.2024 18:42
This is problem is so easy that we can find all cearense integers. Lemma if $N$ is cearense, then $N\vert10^{2k}-1$
Using the lemma and looking at the size, we notice that the quotient $q\leq9$. Clearly, $2$, $4$, $5$, $6$ and $8$ don’t work, and $1$, $3$ and $9$ break the gcd, so $q=7$. Analyzing the order mod $7$, we get that $3\vert k$, then $N=142857142857…142857$. If $k$ is even it doesn’t work, and for $k$ odd, it suffices to prove that the gcd works, which is clearly true. So all the cearense numbers (apart from 11) are $\frac{10^{6k}-1}{7}$ for $k$ odd.