Sunday Afternoon Maths LIV
Hat check
Three logicians, A, B and C, are wearing hats. Each has a strictly positive integer written on it. The number on one of the hats is the sum of the numbers on the other two.
The logicians say:
A: I don't know the number on my hat.
B: The number on my hat is 15.
Which numbers are on hats A and C?
Show answer
Hide answer
Each of the logicians can see two numbers and knows that her number is either the sum of or the difference between these numbers.
The only way in which A could've known her number was if B and C had the same number (as the difference would be 0, not positive). So after A speaks, B knows that B\(\not=\)C.
There are two ways in which B could know her number: (1) if A=C, or (2) if the information revealed by A removed one of the options.
(1) is not possible, as this would mean that B is the sum of A and C and therefore even (but 15 is odd.
Therefore (2) must have happened. Learning B\(\not=\)C removed one of B's options, so B=C must have been one of B's options. This is only possible if A=2C, giving B's options as being equal to C or 3C.
As B cannot be C, B must therefore be 3C, so the numbers are: A=10, B=15, C=5.
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?
Cross diagonal cover problem
Draw with an \(m\times n\) rectangle, split into unit squares. Starting in the top left corner, move at 45° across
the rectangle. When you reach the side, bounce off. Continue until you reach another corner of the rectangle:
How many squares will be coloured in when the process ends?
Show answer
Hide answer
$$\mathrm{lcm}(m-1,n-1)+1 - \frac12\left(\frac{\mathrm{lcm}(m-1,n-1)}{m-1}-1\right)\left(\frac{\mathrm{lcm}(m-1,n-1)}{n-1}-1\right)$$
![](javascript:showlimage("cross_p1.png"))
![](javascript:showlimage("cross_p2.png"))
![](javascript:showlimage("cross_p3.png"))
![](javascript:showlimage("cross_p4.png"))
![](javascript:showlimage("cross_p5.png"))
![](javascript:showlimage("cross_pend.png"))