Puzzles

The number can contain no 1 (as all numbers are multiples of 1). It's first and last digits cannot be 2 (as it would then be even and so a multiple of 2).

The lowest three-digit palindrome containing no 0 or 1 and not ending in 2 is 323. This is not a multiple of 2 or 3 and so is the solution.

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?

415

1. 7

2. 11

3. 90

First, if \(n\) and \(m\) share a common factor other than 1, there will be no largest number: any number that is not a multiple of the common factor will be impossible to make.

If \(n\) and \(m\) are coprime, then considered the remainders when the multiples of \(n\) are divided by \(m\). For example, if \(n=3\) and \(m=7\):

Once a number with a given remainder is reached, then all other numbers with that remainder can be reached by repeatedly adding \(m\). Once \(mn\) is reached, the remainders column will repeat itself. Before \(mn\), all remainders will appear (this can be shown by showing that there are \(m\) rows which much all have different remainders). Hence above \(mn\) all numbers can be made.

In the 3,7 example, the last remainder to be hit is 4. The highest number that cannot be made will be the highest number with remainder 4 that is less than 18 (when remainder 4 is hit).

In general, the last remainder will be hit at \(mn-n\). The number before this with the same remainder will be \(mn-n-m\). This will be the highest number that cannot be made.

Given \(n\), \(m\) and \(k\), what is the largest number that cannot be written in the form \(na+mb+kc\), where \(a\), \(b\) and \(c\) are positive integers?

1) Yes, there must be either at least two even integers or at least two odd integers. The sum of two even integers is even. The sum of two odd integers is even.

2) Five.

3) Five.

4) An infinite number: in a list of odd integers, there will never be three integers which add up to an even number.

This puzzle leads naturally into the following extension:

How many integers must there be in a set so that there will always be \(a\) integers in the set whose sum is a multiple of \(b\)?

For which values of \(a\) and \(b\) will the answer to this be finite?

Many more puzzles like this one can be found in my post on the Chalkdust blog.

Let the two digit number chosen by \(10a+b\), with \(a\) and \(b\) one digit integers. Reversed this will be \(10b+a\). The sum of these will be \(11a+11b\) which is divisible by 11.

This will work for any integer with an even number of digits. Let our number have \(2n\) digits. It can be written as:

Adding it to its reverse, we get:

\(10^{i-1}+10^{2n-i}\) is divisible by 11 (for \(n \in \mathbb{N}\), \(i \in \mathbb{N}\), \(i\leq 2n\)). This can be shown by induction on \(n\):

If \(n=1\): \(10^{i-1}+10^{2n-i} = 10^{i-1}+10^{2-i}=11\), which is clearly divisible by 11.

Suppose result is true for \(n-1\). Now consider \(10^{i-1}+10^{2n-i}\).

If \(i>1\), then \(10^{i-1}+10^{2n-i}= 10(10^{(i-1)-1}+10^{(2n-2)-(i-1)}\) which is divisible by 11 by the inductive hypothesis.

If \(i=1\), then:

Which numbers with an odd number of digits will be divisible by 11 when added to their reverse?