November 2003
—————————
In my November diary I posed the following brain-teaser. In what follows, M and N stand for non-negative integers — that is, whole numbers greater than or equal to zero.
Consider the expression 9M + 16N, where M and N range over all possible non-negative integers. Some numbers can be represented in this form: for example, the number 59 (when M = 3 and N = 2). Some numbers, on the other hand, can't be represented in this form: for example, 55. No matter what values you give to M and N, 9M + 16N will never be equal to 55.
What is the largest number that can't be expressed in the form 9M + 16N ? Why is this number the largest?
And: Suppose that I substitute "positive" for "non-negative" in the above? In other words, neither M nor N may be zero. Now what is the largest number? Why?
—————————
Solution
The whole thing is easier if you think in hexadecimal. Hexadecimal is the number notation
we'd have if we had eight
fingers on each hand, instead of five. Counting in hexadecimal goes like this: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C,
D, E, F, 10, 11, 12, 13, 14,
15, 16, 17, 18, 19, 1A, 1B, 1C, 1D, 1E, 1F, 20, 21, 22, 23, … Here A stands for ten, B stands for
eleven, C stands for twelve, D
stands for thirteen, E stands for fourteen, and F stands for fifteen. Working from right to left of a number, instead
of having a units position, a
tens position, a hundreds position, and so on, you have a units position, a sixteens position, a two hundred
fifty-sixes position (because sixteen
times sixteen is two hundred fifty-six), and so on. The number of cavalrymen in Tennyson's poem "The Charge of
the Light Brigade" would be
written "600" in ordinary decimal notation. In hexadecimal, it would be written "258" (2 two
hundred fifty-sixes, 5 sixteens,
and 8 ones). The actual number of men and horses is of course the same; only the notation, the way we write it is
different, just as it would be if
we said the words "six hundred" in Japanese or Hungarian instead of English.
OK, now let's take some number that can be represented as 9M + 16N, and think of its
hexadecimal representation.
Obviously the units digit just depends on M. It doesn't depend on N at all. As N goes
through 0, 1, 2,
3, … the only digits affected in the hexadecimal representation are those in the sixteens position
and those to the west of
it.
How, exactly, does the units digit depend on M? Well, if M is zero, the units position will also be
zero. If M is 1, then the
units digit will be 9. If M is 2, the units digit will also be 2, because 9 times 2 is 18, which is a sixteen
and a two. If M is
3, the units digit will be B (that is, eleven), because 9 times 3 is 27, which is a sixteen and an
eleven … And so on. In fact,
for any desired units digit, there is exactly one value of M that will give you that digit.
To be precise, for M = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, you will get a units position of,
respectively, 0, 9, 2, B, 4,
D, 6, F, 8, 1, A, 3, C, 5, E, 7.
Let's fix our attention on some particular units digit. I'll take the hexadecimal digit B (that is, eleven) just at
random. How can we get this
digit? Well, if N is zero and M is three, then 9M + 16N will be
twenty-seven, which looks like this in
hexadecimal: 1B. If N is one and M is three, you'll get forty-three, which is 2B in hexadecimal. And
so on; increasing N
in steps of one gets you 3B, 4B, 5B, …
What's the biggest number with units digit B that I can't get? Obviously it's the one before 1B in the list 1B, 2B,
3B, 4B, 5B, …
That would just be B, i.e. eleven.
Similarly, to get a units digit of 3, M needs to be eleven. Nine times eleven is ninety-nine, which looks
like this in hexadecimal: 63.
With N equal to 0, 1, 2, 3, … I get hexadecimal 63, 73, 83, 93, … The
biggest number I can't get with
units digit 3 is hexadecimal 53, which is eighty-three.
And the biggest number of all that I can't get is one with a 7 in the units position. To be exact, nine times fifteen
(which is a hundred
thirty-five, hexadecimal 87), minus sixteen: a hundred and nineteen (hexadecimal 77).
In case the picture is still not clear, here is … a picture.
This table shows, in hexadecimal form, all the possible results, for the first few values of M and N.
Clearly the table could be
continued downward and rightward indefinitely. There is no point extending it downwards, though, since the pattern is
clear, and you will just be
seeing bigger and bigger numbers with a given units digit that can be represented as
9M + 16N. We're interested in ones
that can't. Similarly, there is no point extending the table rightwards, to values of M bigger than
fifteen, because the units
digits will start to cycle through 0, 9, 2, B, 4, … again with bigger digits in the sixteens
positions.