# Puzzles

## 20 December

What is the largest number that cannot be written in the form \(10a+27b\), where \(a\) and \(b\) are nonnegative integers (ie \(a\) and \(b\) can be 0, 1, 2, 3, ...)?

#### Show answer & extension

#### Hide answer & extension

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,

$$219 = 10\times30 - 27\times3$$ $$= 10 + 10\times29 - 27\times3 $$ $$= 1\times10 + 27\times11$$

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":

$$10\times(-1) + 27\times13 = 10\times28 + 27\times(-1) = 233$$

So the answer is 233.

#### Extension

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?

## Square pairs

Source: Maths Jam

Can you order the integers 1 to 16 so that every pair of adjacent numbers adds to a square number?

For which other numbers \(n\) is it possible to order the integers 1 to \(n\) in such a way?

#### Show answer

#### Hide answer

Yes: 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16.

It is clearly possible for the numbers 1 to 15 (remove the 16 from the end of the sequence above) and 1 to 17 (add 17 to the start of the sequence above).

The OEIS sequence

A090461 gives other numbers for which this is possible. It starts 15, 16, 17, 23, then includes every number from 25 onwards. It is conjectured, but not proven, that it is possible for every number above 25.

## 14 December

Today's number is the largest number that cannot be written in the form \(27a+17b\), where \(a\) and \(b\) are positive integers (or 0).

## Combining multiples

In each of these questions, positive integers should be taken to include 0.

1. What is the largest number that cannot be written in the form \(3a+5b\), where \(a\) and \(b\) are positive integers?

2. What is the largest number that cannot be written in the form \(3a+7b\), where \(a\) and \(b\) are positive integers?

3. What is the largest number that cannot be written in the form \(10a+11b\), where \(a\) and \(b\) are positive integers?

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

#### Show answer & extension

#### Hide answer & extension

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\):

Multiple | Remainder |

0 | 0 |

3 | 3 |

6 | 6 |

9 | 2 |

12 | 5 |

15 | 1 |

18 | 4 |

21 | 0 |

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.

#### Extension

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?

## Subsum

1) In a set of three integers, will there always be two integers whose sum is even?

2) How many integers must there be in a set so that there will always be three integers in the set whose sum is a multiple of 3?

3) How many integers must there be in a set so that there will always be four integers in the set whose sum is even?

4) How many integers must there be in a set so that there will always be three integers in the set whose sum is even?

#### Show answer & extension

#### Hide answer & extension

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:

#### 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?

## Santa

Each of the letters D, A, Y, S, N, T, B, R and E represents a different non-zero digit. The following sum is true:

$$
\begin{array}{cccccc}
D&A&D&D&Y\\
B&E&A&R&D&+\\
\hline
S&A&N&T&A
\end{array}
$$

This has a unique solution, but I haven't found a way to find the solution without brute force. This less insightful sum is also true with the same values of the letters (and should allow you to find the values of the letters using logic alone):

$$
\begin{array}{ccccc}
R&A&T&S\\
N&E&R&D&+\\
\hline
S&A&N&E
\end{array}
$$