4
$\begingroup$

As the question explains, we have a two digit number

$$X = x_1x_2 = 10x_1 + x_2$$

reversing it we get,

$$Y = x_2x_1 = 10x_2 + x_1$$

Let $x_1>x_2$, so $X>Y \ \ \ \ \ ... \ \ \ \ (0)$.

The question is to find X such that $R = X\%Y$ is maximized.

Bonus part : Will the answer change if the question had been "A two digit number is reversed. What is the largest possible remainder possible by dividing the two?" i.e. what if we also considered $Y\%X$ where $Y<X$ can we now find a larger reminder?


Edit : I am actually looking for a general solution to this kind of problems where this particular question can be considered a special case. I hope that by solving this question I will be able to tackle the generalized problem, find the $n$ digit number $X$ such that flipping the first and last digit gives you a number $Y$, $X>Y$ and for a fixed $n$, $X\%Y$ is maximum.


Ok full disclosure, this question is taken from a very popular exam in India - UPSC Prelims Exam 2017 - General Studies-2 (CSAT) Paper (SET-B) Q - 33. I have managed to reach the answer through a sort of brute force approach (detailed below) and verified the answer using a python script. But I am not satisfied and wish to find a systematic solution to reach the answer definitely.


My approach

$$R = X \% Y = (10x_1 + x_2)\% (10x_2 + x_1)$$

Let $$k = \left \lfloor \frac{X}{Y} \right \rfloor \ \ \ \ \ ... \ \ \ \ (1)$$

Then

$$X = k\times Y + R \ \ \ \ \ ... \ \ \ \ (2)$$ $$(10x_1 + x_2) = k\times (10x_2 + x_1) + R$$

So

$$R(x_1,x_2,k) = (10x_1 + x_2) - k\times (10x_2 + x_1) $$

$$ R = x_1(10-k) + x_2(1-10k) \ \ \ \ \ ... \ \ \ \ (3)$$

At this point I wondered what values $k$ could take. It could be as low as $1$, but because we are working only with an $X$ with two digits it's maximum value can be found with the largest $X$ and smallest $Y$ ( from equation $(1)$ )

The maximum two digit $X$ with a tolerable $Y$ would be $91$ and $19$. So we can conclude the $k$ we are looking for will be an integer in $[1,5]$ range.

So I had the idea of substituting a couple of integers in place of $k$. I then saw that $R$ was,

$$R(x_1,x_2,1) = 9x_1 - 9x_2 $$ $$R(x_1,x_2,2) = 8x_1 - 19x_2 $$ $$R(x_1,x_2,3) = 7x_1 - 69x_2 $$

This trend showed me that with larger $k$ the remainder seems to fall fast. So here we can assume

$$k=1 \ \ \ \ \ ... \ \ \ \ (4)$$

in order to maximize $R$.

Ok so now,

$$R(x_1,x_2) = 9(x_1 - x_2) \ \ \ \ \ ... \ \ \ \ (5)$$

At this point we might be tempted to maximize $(x_1 - x_2)$ thus getting $(9-1) = 8$. But $19$ doesn't go once in $91$, it goes $4$ times inside $91$ ($k = 4$ not $1$) and leaves only $15$ as the reminder. This shows us our flaw in fixing $k$ which is actually dependent on $x_1$ and $x_2$. But bear with me here as other values of $k$ seem to be penalizing for larger values of $x_2$ thereby limiting $x_2$, to values like $1$ or at max $2$. This is not desirable as the smaller number $Y$ would then be in the $10$'s or $20$'s.

Here the point is we do not want a number like $91$ and $19$ to be $X$ and $Y$, as $Y$ should not be too small, because as per equation $(2)$ and $(0)$ we have

$$X > Y > R$$

See how the remainder can never be larger than $Y$ as per equation $(2)$. Thus we want $Y$ to be as large as possible too. $19$ would never be a good choice. This reinforces the idea that $k$ should be $1$. As a large $Y$ would go only once inside a comparable $X$ (because both are 2 digits).

So now we have two issues here, we want the difference between the digits to be large and $Y$ to be pretty large not too small.

Lets start with large Y as the first priority, $Y = 89$. $98 = 89 + 9$, this shows how if X and Y are too close then the remainder will be small. But we can safely assume one digit is 9, $$x_1 = 9 \ \ \ \ \ ... \ \ \ \ (6)$$

as it allows for the most flexibility in choosing the other digit to get maximum ($x_1-x_2$), also it causes $k$ to be $1$ for a lot of values of $x_2$.

$$ 97 = 79 + 18 $$ $$ 96 = 69 + 27 $$ $$ 95 = 59 + 36 $$ $$ 94 = 49 + 45 $$ After $x_2 = 4$ as $x_2$ decreases we find $k$ increases to $2$. $$ 93 = 2 \times 39 + 15 $$ Then to $3$ causing the remainder to drastically fall. $$ 92 = 3 \times 29 + 5$$

Thus I concluded $94 = 49 + 45$ is the best deal. i.e. the highest possible remainder is $45$.

But there is two main assumptions I make - the $k = 1$ and $x_1 =9$ and while I feel I can establish a solid chain of reasoning why. I am not at all satisfied with this protracted approach.


To kind of formalize the last part, instead of substituting different values of $x_2$ we can,

from equation $(1)$,$(4)$ and $(6)$ we can say,

$$k = 1 = \left \lfloor \frac{10\times x_1 + x_2}{10\times x_2 + x_1} \right \rfloor $$

Also keep in mind from equation $(5)$ that we wish to maximize $(x_1 - x_2) = (9-x_2)$, thus we want a small $x_2$.

$$\left \lfloor \frac{90 + x_2}{10\times x_2 + 9} \right \rfloor = 1$$

$$1 < \frac{90 + x_2}{10x_2 + 9} < 2$$

$$10x_2 + 9 < 90 + x_2 < 20x_2 + 18$$

$$9x_2 < 81 < 19x_2 + 9$$

$$x_2 < 9 < 2.111x_2 + 1$$

So $x_2 <9$ and $x_2>\frac{8}{2.111} = 3.78$

Thus we can conclude the value of $x_2$ should be $4$ as we want a small $x_2$ to maximize the difference between the digits.


$\endgroup$
4
$\begingroup$

Obviously the remainder is less than the smaller value.

We know that the answer (the maximum remainder) will be less than $50$, since if the smaller number is $50$ or greater, the larger number will still be less than $100$. The two obvious candidates for the smaller number close to $50$ that give a large remainder are $49$ and $59$, giving remainders $45$ and $36$. With the value $45$ in hand, it's easy to check that having the smaller number from $46$ to $53=99-46$ does not give higher answers (and the numbers $50-53$ are not viable smaller numbers anyway).

This requires some checking that your analysis (showing that the larger number must be $>90$) would perhaps avoid, but is a reasonable path in exam conditions.


For $N$-digit numbers, $N\ge 2$, a similar concept applies. The answer must be less than $h:=5\cdot 10^{N-1}$. Then $h{-}1$ and its reverse gives remainder $h{-}5$ and the other numbers close to $h$ cannot exceed it. Switching only the first and last digits gives the same result for the same reasons.

$\endgroup$
  • $\begingroup$ Is there any analytical way to reach the answer. A method that can be applied to solve it even if the question had asked say switching the first and last digit in a $n$ digit number? $\endgroup$ – Aditya P Aug 7 '17 at 19:08
  • 2
    $\begingroup$ I think it just so happens that $X=4999...9$ always gives you the biggest remainder; you'll end up with $10^k-6 \pmod {5(10^{k-1})-1} \equiv 5(10^{k-1})-5$ every time. To beat this, we need $5(10^{k-1})-4 \leq X' \leq 5(10^{k-1})+6$, but we would also need the last digit to be $9$, which is otherwise impossible. $\endgroup$ – platty Aug 7 '17 at 20:21
  • $\begingroup$ @platty agreed, we'd be checking the same few cases each time (and immediately dismissing them). $\endgroup$ – Joffan Aug 7 '17 at 20:35
  • $\begingroup$ For problems like this, a heuristic analysis that gives a good answer followed by checking the few cases that might make a better one is a common approach. $\endgroup$ – Ross Millikan Aug 8 '17 at 4:11
1
$\begingroup$

I wrote a relaxed problem in a Convex form:

cvx_begin
    variable vX(2)
    maximize( 10 * vX(1) + vX(2) - 10 * vX(2) - vX(1) ) %<! 10 vX(1) + vX(2) is assumed to be the larger
    subject to
        vX <= 9;
        -vX <= 0;
        vX(1) >= vX(2);
        20 * vX(2) + 2 * vX(1) >= 10 * vX(1) + vX(2);
cvx_end

The idea is simple.
It is clear the problem is symmetric and we're looking for a case where the divider is 1 + reminder.
Namely, twice the smaller number must be not smaller than the bigger number.
In this case, the reminder is the subtraction.

If you round the answer you get from above the answer is simple - 94 <-> 49.
It is easy to solve the above by hand using KKT or something.
Moreover, you can see the optimal gap is 46.9 for continuous number and the optimal in integer is 45.

In the code above I allowed the case 50 -> 05.
Though it doesn't change the optimal point, if you want the small digit to be larger than 0 it is easy to do (Add -vX(2) <= -1).

Enjoy...

$\endgroup$
1
$\begingroup$

We exclude easily $y=0$ which would give $R=0$

If $$k(10y+x)\lt10x+y\lt(k+1)(10y+x)$$ then for $k=1$ one has$$R=9(x-y)$$ for $k=2$ one has $$R=8(x-y)-11y$$ and for other values among the possible ones, one clearly obtains smaller possible values for $R$ positive.

Thus we search with $k=1$

We looking for $x-y$ maximum and such that $10x+y\lt 2(10y+x)$.

It follows after a simple calculation that $x-y=5$ which is fulfilled when $(x,y)=(9,4)$ as only solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.