3
$\begingroup$

A problem in the 2005 Indian National Math Olympiad states:

Let $a,b \in \mathbb{N}$ such that:

$$\frac{43}{197} < \frac{a}{b} < \frac{17}{77} .$$

Find ${\rm min}(b)$.

(Incidentally, the answer is $b=32$ with $a=7$.)

There is an algorithm for finding the solution in which we invert all ratios (which of course reverses $<\ \to\ >$), then subtract off integers from all terms (thereby preserving the inequalities). If the flanking rationals have different integral parts, then choose the unknown middle fraction to be the upper integer (thereby preserving the inequalities but minimizing the size of the numerator). If instead the flanking numbers have the same integer parts, invert the ratios and iterating this procedure.

Frankly, this method is very obscure, complicated, and of narrow applicability.

I'm wondering if there is a more direct method exploiting Mathematica's symbol manipulation functionality, including functions such as Rationalize, Minimize, and so on. I'm very much not interested in some exhaustive search of positive integers for numerators and denominators, as that truly doesn't exploit abstract symbol manipulation.

As for instance the naive and dull and computationally costly approach here:

thelist = Flatten[Table[a/b, {a, 1, 40}, {b, 1, 40}]];
Select[thelist, 43/197 < # < 17/77 &]

(* 7/32 *)

(Or said another way, one could perform such a search in Python or other language without using true symbol manipulation.)

Unfortunately, all of my attempts, which exploit Rationalize, Maximize, and logical tests as variations on:

Minimize[{a, 43/197 < a/b < 17/77}, {a, b} \[Element] Integers]

all fail.

I could find no similar problems on this site.

Suggestions?

GOT IT!!!

z = N[Mean[{43/197, 17/77}]];

Rationalize[z, (17/77 - 43/197)/2]

(* 7/32 *)

Let $z$ be the mean of the two limits. Then use Rationalize WITH A TOLERANCE that is half the range between the limits. This finds any number in the full range that has the smallest denominator.... just as needed.

Bingo!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Your approach using Rationalize is essentially using Mathematica as a black box to solve the problem. That is, you don't know what it is doing inside the black box. It could be doing "some exhaustive search of positive integers" inside. $\endgroup$
    – Somos
    Commented Aug 25, 2021 at 18:41
  • 1
    $\begingroup$ The whole point is that we need NOT know what Mathematica is doing inside some black box. Yes... we're using it as a black box, and that is great! That is the whole point of automation. Regardless, it is almost certainly not doing some exhaustive search of positive integers. A simple test of timing for illustrative cases proves that (e.g., Rationalize[6.25] versus Rationalize[6.25000000001], where the latter is faster.). see: ted.com/talks/… $\endgroup$
    – David G. Stork
    Commented Aug 25, 2021 at 19:04
  • 1
    $\begingroup$ I like the Rationalize method. This also works: In[307]:= Minimize[{b, 197*a > 43*b, 77*a < 17*b, a > 0, b > 0}, {a, b}, Integers] Out[307]= {32, {a -> 7, b -> 32}} $\endgroup$
    – Daniel Lichtblau
    Commented Aug 27, 2021 at 14:00
  • $\begingroup$ Yep... closely equivalent. Thanks. $\endgroup$
    – David G. Stork
    Commented Aug 27, 2021 at 16:23

1 Answer 1

Reset to default
6
$\begingroup$ 
cd = CylindricalDecomposition[a > 0 && 43/197 < a/b < 17/77, {a, b}]

Minimize[{b, cd}, {a, b}, Integers]

(*   {32, {a -> 7, b -> 32}}   *)

Or for negatives

cd = CylindricalDecomposition[a < 0 && 43/197 < a/b < 17/77, {a, b}]

Maximize[{b, cd}, {a, b}, Integers]

(*   {-32, {a -> -7, b -> -32}}   *)
Improve this answer
$\endgroup$
5
  • $\begingroup$ I certainly had never heard of this function, and am still trying to understand it. But thanks very much! ($+1$) $\endgroup$
    – David G. Stork
    Commented Aug 25, 2021 at 14:52
  • 1
    $\begingroup$ red = Reduce[a > 0 && 43/197 < a/b < 17/77, {a, b}] does the same in this case. $\endgroup$
    – Akku14
    Commented Aug 25, 2021 at 15:44
  • $\begingroup$ Again, very helpful. I still don't fully understand why either of your two solutions work (while my first did not), but I'll read and think about it. $\endgroup$
    – David G. Stork
    Commented Aug 25, 2021 at 15:54
  • $\begingroup$ Minimize/Maximize often have problems with denominators. In other cases it helps to apply //Together or for equations (lhs-rhs//Together//Numerator)==0 $\endgroup$
    – Akku14
    Commented Aug 25, 2021 at 16:01
  • $\begingroup$ I didn't know that problem concerning denominators. I'll keep in mind Together[] in the future... and I've used in in other contexts. (I'm impressed you knew about CylindricalDecomposition... quite an esoteric function!) $\endgroup$
    – David G. Stork
    Commented Aug 25, 2021 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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