N1: 77×87−76×87 = (77−76)×87 = 1×87 = 87
N2: 1012−992 = (101−99)×(101+99) = 400. (Neither this, nor N1, as familiar to Year 12 Further Maths students as you’d think).
N3: Can be proved by (strong) induction. Or, better:
N = a + 10b + 100c + 1000d + …
= a + (b + 9b) + (c + 99c) + (d + 999d) + …
= (a + b + c + d + …) + (9b + 99c + 999d + …)
= (a + b + c + d + …) + 9×(b + 11c + 111d + …)
N = (sum of digits of N) + 9×(some number)
N4: Six. Let b=the units digit of N, so N2 = (10a+b)2 = 100a2+20ab+b2
So the tens digit of N2 is odd only if the tens digit of b2 is odd.
But among the numbers 1, 2,…9, only two have squares with odd tens digits, 4 and 6. And in both those cases the units digit of the square is 6.
N5 (borrowed from Terry Tao). If there are s sheep, and each brother has had n×10 roubles before they come to the last share-out, and the younger brother gets a roubles in the last share-out,
s2 = (2n+1)×10 + a
So, by N4, a=6. The knife is worth 2 roubles.
N5. It makes the angles of an equilateral triangle 66⅔ degrees. 360 has the advantage of more divisibility.
N6. Longer until the weekend.
N7. It was originally 12 hours in a day, when all clocks depended on the sun, so there were no hours when it was dark. The 12 seems to have come from 10 (as in usual base-10) plus one hour for dawn and one for dusk. Originally hours were longer in summer than in winter (though there was not much difference around the Mediterranean, where this scheme originated).
N8. You need to check only prime numbers because if a number is divisible by a composite number, then it is divisible by a smaller prime number too. You need to check primes only up to 7, because if any prime ≥ 11 divides a number ≤ 100, then that prime ≥ 11 must go into the number ≤ 10 times, so there is also a prime ≤ 10 which divides the number.
N9. 2, 3, 5, 7, 11, 13, 17 – all the primes less than the square root of 300.
N10. There will always be at least four students in the right order. First, forget about students and heights: label each student with their number in the height order, so we get a sequence of numbers, e.g. 7 4 8 6 9 0 3 1 5 2.
Let x(i) = the i’th number, a(i) = length of the biggest ascending sequence including x(i), and d(i) = length of the biggest descending sequence including x(i). [For this problem we start counting from 0. In the example, x(0)=7, a(0)=3 (the sequence 7, 8, 9), and d(0)=4 (the sequences 7, 6, 3, 2 or 7, 4, 3 2].
Then each number x(i) has a unique combination of a(i) and d(i), in other words if, for some j, a(i)=a(j) and d(i)=d(j) then i=j.
Why? Suppose j>i. Then either x(j)>x(i), and so a(j) is at least a(i)+1; or x(j)<x(i), and so d(j) is at least d(i)+1. By a similar argument it’s impossible that i>j.
If there is no sequence of four students in the right order, then for all i the only possible values of a(i) and d(i) are 1, 2, and 3. There only 9, i.e. 3×3, possible combinations of a(i) and d(i), i.e. only 9 possible values of i. But there are ten numbers in the sequence. So that’s impossible. There must be a sequence of at least four students in the right order.
M1: 1. If the longer sides of the rectangle are 1+d, the smaller are 1-d. Area = (1+d)(1–d) = 12 − d2
M2: √3. Equilateral triangle. Either guessing that the maximum-area triangle is equilateral, or trial and error by drawing triangles, are ok methods of getting there. Better to prove as in M3.
M3: First prove that of all triangles with the same perimeter on the same base, the isosceles triangle has the greatest area. We do it by proving that any non-isosceles triangle with the same area as the isosceles must have a greater perimeter.
ABC is the isoceles triangle on the given base AC, and ADC is another triangle on the same base, i.e. with the same height relative to AC. Construct BC’ as a continuation of AB with length equal to BC.
Then angle DBC = angle ACB (alternate) = angle CAB (isosceles) = angle DBC’ (corresponding)
So triangles DBC and DBC’ are congruent, so DC’ = DC
AD + DC’ > AC’ (two sides of triangle add up to more than the third), so AD + DC > AB + BC, i.e. the non-isosceles triangle has a greater perimeter.
Now suppose we have a non-equilateral triangle of maximum area with given perimeter.
At least two sides are unequal. But then there is an isosceles triangle of the same perimeter, based on the third side, with greater area than this non-equilateral triangle, which is a contradiction. Therefore the triangle of maximum area with given perimeter is equilateral.
M5. I don’t know, despite puzzling about it a bit. Something to do with invariants, I suspect.
M6. Four. Let 0.5m=1 unit, then the floor is approx a 6-unit square, so has area a bit less than 36. Or this could be done by drawing the floor on squared paper. Strictly speaking, we don’t know the angles, so the floor might be a long, thin diamond-shape and of very small area. But then you’d have worse problems than some carpet tiles left over. The interesting follow-up is to see that the divergence from area 36 by two sides being 6+6Δ and 6– 6Δ is of order Δ2 (the “top” vertex of the half-floor triangle containing those sides moves along an ellipse as Δ varies), and the divergence from area 36 by the floor’s angles being 90 + Δ and 90 – Δ is also of order Δ2. The area is within 10% of 36 even if Δ = 26 degrees.
M7. The diagonal. Then we could use Heron’s formula or draw an exact diagram on squared paper.
M8. Tie twelve knots on the rope, equally spaced, and make a 3-4-5 triangle.
M9. Because weight increases by the cube of an animal’s size and area (e.g. of cross-section of leg) only by the square. For the same reason, Arctic animals are bigger than animals that live in hot climates, giants would break their ankles every time they walked, large birds can’t fly. (Even eagles, apparently, cannot strictly speaking fly, but only glide on warm-air currents).
P1. Choosing any one particular number if you choose a number genuinely at random from the infinitely many possibilities between, say, 0 and 1. This is of some practical importance. For example, also, with the normal distribution, the probability of the random variable taking any particular precise value is zero. With the Collatz conjecture – “take any natural number n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1” – it can be proved that the probability of eventually getting back down to 1 is 1, but the conjecture could still be untrue for infinitely many n.
P2. (2n − 1)(2n − 3)….5.3.1, or (2n − 1)!/(n − 1)!2(n−1)
List the competitors in alphabetical order. We have (2n–1) choices for who’ll play the first competitor, (2n–3) for who’ll play the second, and so on down to 1 choice for the last pair.
P3. Yes. P(prize in box you first picked)=⅓. P(prize in box host opened)=0. P(prize in other box)=⅔.
P4. 15 = 6C2. (You can do it just by drawing and counting).
P5. 15, as in P4.
P6. 15, as in P4.
P7. 465 = 31C2.
P8. 27. Reckon “no ice cream” as an option, then we can consider only triple-scoop possibilities. With N flavours plus “no ice cream” we get (N+1)C3 − 1 options. If (N+1)C3 − 1 > 3000, then (N+1)N(N–1)>18006, so N is a bit more than the cube root of 18006. Check out 26 and 27 for N.
P9. About 51% = 1−365×364×….×343/36523 = 1−0.4927.
P10. 2.65×1032, or 30! If these seating plans could be reviewed at the rate of 1 per second, 24 hours a day, 365 days a week, it would take about 1025 years to review, a time as much longer than the life of the Universe than the life of the Universe is longer than a nanosecond.
P11. 65% = 1−0.910
P12. Suppose for simplicity that before the shuffle the deck was the spades in order from ace through king to 2, followed by the hearts in order, the clubs in order, and the diamonds in order, so the first card was the ace of spades. Find the ace of spades in the shuffled deck and swap it with the card now (after the shuffle) in the first position. Find the king of spades and swap it with the card now (after the shuffle) in the second position. And so on. That produces a series of swaps which reverses the shuffle. Do those same swaps in reverse order, and that’s a series of swaps which equals the shuffle.
To prove the shuffle must be even or odd, start by proving that any series of swaps which brings the cards back to exactly the same order as before must be an even number of swaps.
Suppose a friend is doing that series of swaps. You mimic her with a slight change. When she does her first swap, say the first card, the ace of spades, for the three of diamonds, card no.51, you make no swap. You leave those cards where they are, but put a tag on the 51st place in the deck.
From then on, when she swaps her first card with another, you swap the card in the tagged place with that other. When she swaps the card in the tagged place (in her deck) with the card in another position, you swap cards in the same two places, but move the tag to that other place. When she makes any move not involving the first or the tagged places, you mimic exactly.
In that way, your tagged place will always hold the card she has in her first place, her tagged place will always hold her ace of spades, and your first place will always hold your ace of spades.
At some point she has to swap the ace of spades (from her tagged place) back to first place, and to do that put the card she has in her first place into the tagged place. At that point you make no swap, because you already have the ace of spades in our first place, and your friend’s first-place card in your tagged place.
In the end you both get the deck of cards back to the same order, but you’ve done it in two swaps fewer.
So any series of swaps which brings the deck back exactly as it was can be reduced in length by two. That means the series must include an even number of swaps. Otherwise it could be reduced, in stages, by two swaps each time, until it was one swap long. But a single swap cannot leave the deck exactly as it was.
Now take any permutation, and two chains of swaps s1s2…..sn and t1t2…..tm which are equivalent to it. If we apply the s-swaps, and then the t-swaps in reverse order, we must get back to the original order. Therefore n+m, the length of the total chain of s-swaps and then reversed t-swaps, must be even. That means that if n is even, m must be even; if n is odd, m must be odd. Which is what we wanted to prove ▇
P13. 2/π. See http://www.cut-the-knot.org/fta/Buffon/buffon9.shtml
A1. (Borrowed from Terry Tao). Tie your shoelace on the walkway. If the distance is d, the speed of the walkway is u and your walking speed is v, and it takes t seconds to tie your laces, then your journey time tying-off-walkway is [d/(u+v) + t] and tying-on-walkway is [(d–ut)/(u+v) + ut/u]. Alternatively: if A gets on walkway, while B first stops to tie laces, then A gets (u+v)t ahead of B. B reduces that lead by only vt when A stops to tie laces.
A2. 1019. More generally sum from r=1 to r=m of rp = [1/(p+1)]. m(p+1) + terms of lower order
(r+1) r (r–1) (r–2)… (r–8)−r (r–1) (r–2) ….(r–9) = 10 r (r–1) (r–2)… (r–8)
So, summing from r=1 to r= 100, sum for r=1 to r=100 of r9 = 1/10 X 10010 + terms of order 109 and lower
This general knowledge is probably more important than the specific formulas for sums of r, r2, and r3
ln (n!) = sum from x=1 to x=n of ln(x)
≈integral from 1 to n of ln(x)
≈[x.ln(x)-x] evaluated between 1 and n
Therefore n! is approx exp [n.ln(n)−n+1]
This is a very crude version of Stirling’s approximation, but tells us for example that 100! (which Casio scientific calculators won’t calculate) is of the order of 37100, so 10100.3.7100, so 10157.
A4. Prove that e is irrational.
Write out e = an infinite series
For any n, multiply both sides by n!
Then n!e = a whole number (first n terms of the series, multiplied by n!) + a remainder
Remainder = 1/(n+1) + 1/(n+1)(n+2) + 1/(n+1)(n+2)(n+3) + ….
Remainder > 0, and remainder < 1/(n+1) + 1/(n+1)2 + 1/(n+1)3 + ….
So remainder < [1/(n+1)]/[1 − 1/(n+1)] = 1/n < 1
So n!e is not a whole number for any n
e cannot be rational, because it if were rational it would have a denominator N, and N!e would be a whole number.
C1. Zero, since |f(h)|≤h2 and thus |[f(h)–f(0)]/h|≤h. Shows that the line of slope f'(a) may cross the curve y=f(x) infinitely many times in any neighbourhood of a.
T1. G, I (if written without serifs), J (ditto), L, M, N, O, P, Q, R, S, U, V, W, Z can.
E, F, H, K, T, X, Y can’t, because they have more than two nodes with an odd number of lines meeting.
T2. No. Too many odd nodes, as above.
G1. The shape of 50p and 20p coins. Having constant width suits them to slot machines, being not circular makes them easier for blind people to identify.
G2. With a drill bit based on the simplest constant-width non-circle shape, the Reuleaux triangle.
Area of triangle made by connecting the centres of the three circles = √3
Area of inside-circles bits within that triangle = ½π
G4. 9.3%. The entire space is made up of “circle-centre-joining” triangles, so the percentage of the total space which is “outside” = percentage of space inside a “circle-centre-joining” triangle which is “outside” = (√3−½π)/√3 = 9.3%.
G5. Three (as in the congruence cases).
G6. Five (four sides and a diagonal, or four sides and an angle, etc.)
G7. 2n–3. You prove this by induction.
G8. 14 = (2×17−3)−17
G9. At least one of x, y, and z must be even, because odd2+odd2=even. In fact, one of x and y must be even, because odd2+odd2=a number of form 4n+2, which can’t be a square. Say y is even and x and z are odd. Then z2 and x2 are of form 4n2+4n+1 and 4m2+4m+1 for some n and m. Thus y2 must be of form:
hence divisible by 8 [because one of (n−m) and (n+m+1); must be even];
hence y must be divisible by 4.
Then consider the equation x2+y2=z2 in modular (“clock”) arithmetic mod 3 and mod 5. There are not enough square numbers mod 3 or mod 5 for the equation to have a solution without one of the square numbers being 0, i.e. without x or y or z being divisible by 3 or by 5.
G10. From a given point X, draw two lines of lengths a and b at right angles to each other. Then draw another line joining the ends of those lines opposite to X, to form a triangle T. By Pythagoras, that third line has length c defined by c2 = a2+b2 and c>0.
Let S be any other triangle with sides a, b, and c. S is congruent to T (SSS case). Therefore S is right-angled.
G11. It’s the sum of the first 5 elements of the (n−1) row of Pascal’s triangle.
G12. The pattern for number of points on the circumference and number of areas is:
1 point – 1 area
2 points – 2 areas
3 – 4
4 – 8
5 – 16
6 – 31
7 – 57
Claim: for n points on the circumference, we get nC4+nC2+1 areas. This is also equal to the sum of the first 5 elements of the (n−1) row of Pascal’s triangle.
Proof: If necessary, tilt the circle microscopically so that every meeting-point of lines (or of a line and the circumference) is at a different height.
Then every region in the circle has exactly one meeting-point as its lowest vertex, and every meeting-point which is inside the circle (rather than on the circumference) is the lowest vertex of exactly one region.
There are nC4 meeting-points inside the circle, because every four points on the circumference define such a meeting point. Each is a lowest vertex of one region.
There are nC2 lines joining points. If we go round the circle from the lowest point, each such line defines a region (which we have not already counted) to its right at the lower of the two points which the line connects.
And then there is one more region to the left of the left-most line at the bottom point.
Therefore total regions = nC4+nC2+1
Since nC2=(n−1)C1+(n−1)C2 and nC4=(n−1)C3+(n−1)C4 and (n−1)C0=1, also:
total regions = sum from r=0 to r=4 of (n−1)Cr = sum of first 5 elements of (n−1) row of Pascal’s triangle, which explains why total regions = 2(n−1) for n<6. ▇
Note that we can tell straight off that the apparent pattern for n=1,2,3,4,5 can’t continue forever. With n points there are only ½n(n−1) crosslines, therefore the number of regions is certainly less than the number of regions created in the whole plane by ½n(n−1) lines. It is at most of the order of n4, which for large n is much less than 2n.