»  Solutions to puzzles in my National Review Online Diary

  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.

    M = 0     M = 1     M = 2     M = 3     M = 4     M = 5     M = 6     M = 7     M = 8     M = 9     M = A     M = B     M = C     M = D     M = E     M = F  
 N = 0   0   9   12   1B   24   2D   36   3F   48   51   5A   63   6C   75   7E   87 
 N = 1   10   19   22   2B   34   3D   46   4F   58   61   6A   73   7C   85   8E   97 
 N = 2   20   29   32   3B   44   4D   56   5F   68   71   7A   83   8C   95   9E   A7 
 N = 3   30   39   42   4B   54   5D   66   6F   78   81   8A   93   9C   A5   AE   B7 
 N = 4   40   49   52   5B   64   6D   76   7F   88   91   9A   A3   AC   B5   BE   C7 
 N = 5   50   59   62   6B   74   7D   86   8F   98   A1   AA   B3   BC   C5   CE   D7 

For any given hexadecimal digit, the biggest number that can't be represented by 9M + 16N is the one in the (invisible) row above the N = 0 row. That is, it is the number in the N = 0 row, minus sixteen. The biggest such number is hexadecimal 87 minus sixteen, which is hexadecimal 77, which is one hundred nineteen.

If M and N are not allowed to be zero, we lose the first row and first column of our table. However, to get the case where the units digits is zero, we must now include a new column at the right, headed "M = 10." That's hexadecimal "10," of course, i.e. sixteen. Reading down that column, and remembering that the first row, the N = 0 row, has disappeared, we shall have: A0, B0, C0, D0, … Just as before, the biggest number that can't be represented is hexadecimal A0 minus sixteen, i.e. hexadecimal 90, i.e. one hundred forty-four.