23
$\begingroup$

Say, you are given ruler $A$ of length $72.84 \text{ cm}$ and ruler $B$ of length $86.63\text{ cm}$. Neither of them have any marking/gradation of any sort on them. They are blank, except for their total length written on them.

Using only A and B, can you measure a length of $31.23\text{ cm}$?

Also, is it possible to generalize this concept further?

That is to say:

Given any two blank rulers, measure any given length.

|cite|improve this question
$\endgroup$
  • 21
    $\begingroup$ An observation which may or may not be helpful: $\gcd (7284, 8663) = 1$ $\endgroup$ – TheMathsGeek Jul 17 '18 at 17:24
  • 8
    $\begingroup$ I think a better title would be "measure a given length". No pair of rulers can measure every length. $\endgroup$ – BallpointBen Jul 17 '18 at 20:26
  • 2
    $\begingroup$ @BallpointBen do you mean irrational and complex measures? $\endgroup$ – Nick Jul 18 '18 at 4:13
  • 1
    $\begingroup$ A similar problem :) $\endgroup$ – user170231 Jul 18 '18 at 18:00
52
$\begingroup$

Yes. It is Possible

Here's a useful fact: If $a$ and $b$ are integers with $\gcd(a,b) = d$, then there exist integers $x$ and $y$ such that $ax + by =d$. In fact, one can compute exactly what $x$ and $y$ are by the extended Euclidean algorithm.

In this case, we have $$ 3539 \times 8663 - 4209 \times 7284 = 1$$

Or, $$ 3539 \times 86.63 - 4209 \times 72.84 = 0.01 $$

So, in theory, you could measure $0.01$ cm by marking off $3539 \times 86.63$ cm along a line, and then marking off $4209 \times 72.84$ cm along the same line; the difference in the markings will be $0.01$ cm.

Of course, now that you can measure $0.01$ cm, you can measure any multiple thereof.

For your generalization, given two blank rulers, you can measure any length that is a multiple of the gcd of their lengths. (Make sure you choose units where the lengths of the rulers are integers. Here, we chose 0.01 cm)

Edit: As noted by Silverfish in the comments, the interesting fact I mention above is Bézout's identity

|cite|improve this answer
$\endgroup$
  • 6
    $\begingroup$ This question gives a great picture for the extended euclid's algorithm that i've never seen before. $\endgroup$ – Calvin Khor Jul 17 '18 at 18:03
  • $\begingroup$ A question out of curiosity: how did you find out that $3539\times 8663 - 4208\times 7284 = -1$? Did you search it with a computer program, did you have a hitch, did you already know...? $\endgroup$ – Andrea Jul 17 '18 at 20:41
  • 4
    $\begingroup$ @AndreaDiBiagio I'd assume it was calculated through the linked extended Euclidean algorithm. Which might well have been, itself, run through a computer program, but it wasn't a "search". $\endgroup$ – Nic Hartley Jul 17 '18 at 21:24
  • $\begingroup$ @NicHartley makes total sense. I didn’t read through the answer properly. $\endgroup$ – Andrea Jul 17 '18 at 21:43
  • 5
    $\begingroup$ For "here's a useful fact" it might be worth stating its name - it's Bézout's identity $\endgroup$ – Silverfish Jul 17 '18 at 23:28
15
$\begingroup$

This all boils down to (using 0.01 cm as the unit) as

Does $\gcd(7284,8663)$ divide 3123?

The answer is yes: the gcd turns out to be 1. The generalisation is obvious: two blank rulers of lengths $a$ and $b$ units ($a,b$ are natural numbers) can measure any length that is a multiple of $\gcd(a,b)$ units.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Actually, if a/b is rational and therefore gcd(a,b) exists then you can measure any multiple of gcd(a,b) exactly. If a/b is irrational then you can approximate any number with arbitrary precision, but not exactly. $\endgroup$ – gnasher729 Jul 18 '18 at 22:26
8
$\begingroup$

The other answers are in the affirmative and consider measuring multiples of the GCD of the two rulers, or $0.01\text{ cm}$ in the original problem.

For really small problems, it would be better to have an irrational ratio between the two lengths, e.g. a ruler of length $1$ and a ruler of length $\pi$. One can get multiples of $\pi$ arbitrarily close to the integers and thus construct basic units of measurement arbitrarily small.

Doing so, you can measure ANY non-negative real length to ANY desired positive degree of accuracy. Contrast such a ruler with the $0.01\text{ cm}$ ruler mentioned above which can only measure any non-negative real within $0.01\text{ cm}$ of accuracy ($0.005$ really, but there's an uncertainty in the measurement in which side it is actually closer to, so you wind up with up to $0.01$ from the further side).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ brilliant. I should have asked a ruler length $\pi$ and another of length $e$. I didn't think about irrationals. $\endgroup$ – Nick Jul 18 '18 at 7:41
  • 1
    $\begingroup$ Nice observation. A fancy way to say this is that the subgroup of $(\mathbb R,+)$ generated by $\{a, b\}$ is discrete if $\frac{a}{b}\in \mathbb Q$ and dense otherwise. $\endgroup$ – lisyarus Jul 18 '18 at 12:22
  • $\begingroup$ Note it’s not proven that $\pi/e$ is irrational. $\endgroup$ – Roman Odaisky Jul 18 '18 at 22:11
  • $\begingroup$ @RomanOdaisky True, but either $\frac{e\pi+1}{e}$ or $\frac\pi e$ must be irrational. $\endgroup$ – Hans Musgrave Jul 18 '18 at 22:54
  • $\begingroup$ @HansMusgrave Irrelevant — in the (highly unlikely) event $\pi/e$ is rational, $\pi$ and $e$ would have a GCD and better accuracy than the GCD would be impossible. $\endgroup$ – Roman Odaisky Jul 19 '18 at 14:31
5
$\begingroup$

We can write it as the equation $7284y - 8663x = 3123$

or $y = \frac{8663x + 3123}{7284}$

From this we can see that $8663x\equiv 7284-3123 \mod 7284$

$8663x \equiv 4161 \mod 7284$

$8663 \equiv 1379 \mod 7284$

So, $x \equiv \frac{4161}{1379} \mod 7284$

$x \equiv 4161\cdot \frac{1}{1379} \mod 7284$

$x = 4161\cdot 3539 = 14725779$........ where $3539$ is the multiplicative inverse of $1379$

So, $x = 14725779$ and $y = 17513650$

So, if we measure out $17513650$ lengths of the $72.84$ stick and then measure back with $14725779$ lengths of the $86.63$ stick, we achieve a distance of $31.23$ from our starting point.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ At just over 12.5 thousand km, I’m not sure the answer to the question is “yes”. $\endgroup$ – Ian MacDonald Jul 17 '18 at 21:20
  • 1
    $\begingroup$ $5727 \times 72.84 - 4815 \times 86.63 = 31.23$ as well; you can always subtract $k \times 8663$ instances of the short stick and $k \times 7284$ instances of the long stick to get the same total length, and for this $k = 2021$ works. Granted this is still $4\text{km}$ or so of measuring to get something about $1/12000$ that length... $\endgroup$ – Dan Uznanski Jul 17 '18 at 21:37
  • 1
    $\begingroup$ I took your solution and got $x \% 8663$ and $y \% 7284$. Note that obviously $8663 \times 72.84 - 7284 \times 86.63 = 0$, so adding or removing that many copies of each stick will not change the final length at all. Actually, if we go one step further, removing more sticks than are there and measuring in the other direction $2469 \times 86.63 - 2936 \times 72.84$ also works and is somewhat smaller! $\endgroup$ – Dan Uznanski Jul 18 '18 at 5:50
  • 1
    $\begingroup$ @Ian I suppose you could sequence the positive and negative measurements cleverly to avoid going around the world, you go back and forth through the origin instead. In fact you should be able to do it given no more than a couple hundred meters of space. $\endgroup$ – Oscar Lanzi Jul 18 '18 at 16:50
  • 1
    $\begingroup$ I meant a couple hundred centimeters. I could not see the units while commenting. Could not correct the comment due to the time limit, which major sucks. $\endgroup$ – Oscar Lanzi Jul 18 '18 at 16:59

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.