Puzzles
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)$$
Lots of ones
Is any of the numbers 11, 111, 1111, 11111, ... a square number?
Show answer
Hide answer
No. If one of them were a square number, then its square root must end in 1 or 9 (as this is the only way to make the final digit a one). So the square root is of the form \(10n\pm1\).
$$111...1=(10n\pm1)^2$$$$=100n^2\pm20n+1$$
$$=10(10n^2\pm2n)+1$$
If \(10(10n^2\pm2n)+1\) is of the form 111...1, then \(10n^2\pm2n\) is also of the form 111...1 (as it has just had the final 1 taken off). But \(10n^2\pm2n\) is even and 111...1 is odd, so this is not possible.
An integral
What is
$$\int_0^{\frac\pi2}\frac1{1+\tan^a(x)}\,dx?$$
Show answer & extension
Hide answer & extension
Surprisingly, the value of the integral does not depend on \(a\). To show this, first use \(\tan(x)=\frac{\sin(x)}{\cos(x)}\) on both integrals:
$$I_1=\int_0^{\frac\pi2}\frac1{1+\tan^a(x)}\,dx
$$$$=\int_0^{\frac\pi2}\frac{\cos^a(x)}{\cos^a(x)+\sin^a(x)}\,dx$$
$$I_2=\int_0^{\frac\pi2}\frac1{1+\cot^a(x)}\,dx
$$$$=\int_0^{\frac\pi2}\frac{\sin^a(x)}{\cos^a(x)+\sin^a(x)}\,dx$$
Now consider \(I_1+I_2\):
$$I_1+I_2 = \int_0^{\frac\pi2}\frac{\cos^a(x)+\sin^a(x)}{\cos^a(x)+\sin^a(x)}\,dx$$$$=\int_0^{\frac\pi2}1\,dx$$$$=\frac\pi2$$
By substituting \(u=\tfrac\pi4-x\) into \(I_2\), it can be shown that \(I_1 = I_2\).
Therefore \(I_1=\tfrac\pi4\).
Extension
What is
$$\int_0^{\frac\pi2}\frac1{1-\tan^a(x)}\,dx?$$
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?
More doubling cribbage
Brendan and Adam are playing lots more games of
high stakes cribbage: whoever
loses each game must double the other players money. For example, if Brendan has £3 and Adam has £4 then Brendan wins, they will have £6
and £1 respectively.
In each game, the player who has the least money wins.
Brendan and Adam notice that for some amounts of
starting money, the games end with one player having all the money; but for other amounts, the games continue forever.
For which
amounts of starting money will the games end with one player having all the money?
Show answer & extension
Hide answer & extension
If Adam has £\(a\) and Brendan has £\(b\), we will write this as £\(a\):£\(b\).
First, we can take
\(a\) and \(b\) to have no common factors, as dividing both by a common factor gives an equivalent starting point. For example,
£3:£6 and £6:£12 will have exactly the same behaviour (imagine £6 and 3 £2 coins).
£\(a\):£\(b\) is also clearly equivalent to £\(b\):£\(a\) (but with the two players swapping places).
A game starting £\(a\):£\(b\) will end with one player having the money if \(a+b\) is a power of two. This is because:
If \(a+b=2^n\), then if \(n=1\), either the game has already ended or it sits at £1:£1 and is about to end. If \(n>2\), then the starting
position can be written as £\(2^n-k\):£\(k\) with \(k<2^n-k\). After another game this will be £\(2^n-2k\):£\(2k\). This is equivalent to
£\(2^{n-1}-k\):£\(k\). Therefore by
induction, if \(a+b=2^n\) then the
game ends with one player having all the money.
It can also be shown by induction, that if a game ends then it must be £\(a\):£\(b\)
with \(a+b=2^n\).
Extension
What would happen if the losing player has to triple the winning player's money?
Doubling cribbage
Brendan and Adam are playing high stakes cribbage: whoever loses each game must double the other players money. For example, if Brendan has £3 and Adam has £4 then Brendan wins, they will have £6 and £1 respectively.
Adam wins the first game then loses the second game. They then notice that they each have £180. How much did each player start with?
Show answer & extension
Hide answer & extension
Working backwards: before the second game, Brendan must have had £90 and so Adam had £270.
Before the first game, Adam must have had £135, so Brendan had £225.
Extension
After the next game, one player will have all the money and no more games can be played. Hence £135 and £225 lead to a finite number of games being played.
If the player with the most money always loses, which starting values £\(A\) and £\(B\) will lead to finite and infinite numbers of games?
![](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"))