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.

$\endgroup$
4
  • 21
    $\begingroup$ An observation which may or may not be helpful: $\gcd (7284, 8663) = 1$ $\endgroup$
    – TheMathsGeek
    Jul 17, 2018 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, 2018 at 20:26
  • 2
    $\begingroup$ @BallpointBen do you mean irrational and complex measures? $\endgroup$
    – Nick
    Jul 18, 2018 at 4:13
  • 1
    $\begingroup$ A similar problem :) $\endgroup$
    – user170231
    Jul 18, 2018 at 18:00

4 Answers 4

Reset to default
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

$\endgroup$
6
  • 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, 2018 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, 2018 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
    Jul 17, 2018 at 21:24
  • $\begingroup$ @NicHartley makes total sense. I didn’t read through the answer properly. $\endgroup$
    – Andrea
    Jul 17, 2018 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, 2018 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.

$\endgroup$
1
  • 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, 2018 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).

$\endgroup$
5
  • $\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, 2018 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, 2018 at 12:22
  • $\begingroup$ Note it’s not proven that $\pi/e$ is irrational. $\endgroup$
    – Roman Odaisky
    Jul 18, 2018 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, 2018 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, 2018 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.

$\endgroup$
8
  • $\begingroup$ At just over 12.5 thousand km, I’m not sure the answer to the question is “yes”. $\endgroup$
    – Ian MacDonald
    Jul 17, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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.