Puzzles

496

You can find my write up of a solution to this here. Pedro Freitas (@pj_freitas) sent me the following nice alternative solution:

Any number can be written as \(10a+27b\) with integer \(a\) and \(b\), since \(1=3\times27-8\times10\). So the problem may be thought of as asking when one of \(a\) and \(b\) must be negative.

Given one way of writing a number, you can get the others by shifting by 14*29. For example,

So the question now becomes: When does this adjustment fail to eliminate negative numbers?

This is when you are at what Pedro calls "limit coefficients":

So the answer is 233.

Let \(n\) and \(m\) be integers. What is the largest number that cannot be written in the form \(na+mb\), where \(a\) and \(b\) are nonnegative integers?

15, 18 and 45 are elastic.

15's factors are 5 and 3. 105, 1005, 10005, etc will all be multiples of 5 (because they end in 5) and multiples of 3 (as their digits add to 6). Hence they are all multiples of 15.

Similarly, 108, 1008, 10008, etc are all multiples of 9 (adding digits) and 2 (they are even), so they are multiples of 18; and 405, 4005, 40005, etc are all multiples of 9 (adding digits) and 5 (last digits are 5), so they are multiples of 45.

How many elastic numbers are there in other bases?

543

415

768

414

Incredibly, the result will always be \(n^2\).

To see why, imagine writing every number, \(n+1\leq k\leq 2n\), in the form $$k=2^ab$$ where \(b\) is an odd number and also the \(k\)'s largest odd factor. The next largest number whose largest odd factor is \(b\) will be \(2^{a+1}b=2k\). But this will be larger than \(2n\), so outside the range. Therefore each number in the range has a different largest odd factor.

Each of the largest odd factors must be one of \(1, 3, 5, ..., 2n-1\), as they cannot be larger than \(2n\). But there are \(n\) odd numbers here and \(n\) numbers in the range, so each number \(1, 3, 5, ..., 2n-1\) is the highest odd factor of one of the numbers (as the highest odd factors are all different).

Therefore, the sum of the odd factors is the sum of the first \(n\) odd numbers, which is \(n^2\).