This is a response to
Warwick Maths Challenge, 9 Nov 2009. The problem (should it be gone at the time of reading) sets the scene where Robin Hood and Friar Tuck have been shooting at a circular target. The target is painted with consecutive rings, each one the same width as the last. They observe that while the smallest ring Tuck hit was bigger than the biggest ring Hood hit, the total area of Tuck's and Hood's rings are equal. It then asks which rings they could have hit.
Reading through and trying to understand what I've done near to the end will help a great deal in solving a number of problems on Project Euler, namely those where you are required to solve certain types of 3 variable quadratic integer equations.
The problem asks a variety of minimisation questions about sums of odd numbers. Let's first work out why that is. We want to find the area of those rings. A ring is made by removing a small circle from a big circle, so we actually need to find the area of the circles. The circle numbered
n is
n times as big in all directions as the circle numbered
1 and we'll pretend for the sake of argument that the target is picked so that the smallest circle has area equal to 1.
Early on in school, you learn that multiplying the lengths of something by
n will multiply the area by
n×n. This is obvious for a square as its area is the side lengths multiplied together, so a square with side length
1 has area
1 and side length
2 has area
2×2=4, so the big circle for ring number
n has area
n×. The area of the rings is the area of the big circle, minus the area of the little circle, and the little circle is just the previous big one, so it's
n×n - (n-1)×(n-1). A bit of algebra tells us that the answer is
2n-1 or the
nth odd number.
So, first we have to find the first answer where the sum of some small rings equals the sum of some bigger ones. A few facts aren't too hard to see: First, Tuck, hitting the outer rings must have hit less rings than Hood, hitting the inner ones (as all of his are worth more). Second, since odd+odd=even and odd+even=odd, we find that Hood actually hit a multiple of two more rings than Tuck (otherwise one of them hit an odd total area and the other hit an even total area). So the smallest example likely has Hood hitting 3 and Tuck hitting 1. In fact, rings 1, 2 and 3 have total area
1+3+5=9, which is the area of ring 5, so this is the smallest example.
We've definitely picked the smallest example here, and so it's the only one using 5 rings. (If Hood hits a different ring, his total will be more, so Tuck has to hit something further out.) What's the next one? Well, if Hood's smallest ring is increased, so must the rest, giving rings 2, 3 and 4. This has area
3+5+7=15 which is a lot higher. It adds much less area to only make one ring bigger, so we have to change ring 3. It turns out that rings 1, 2 and 4 have total area
1+3+7=11, which is the area of ring 6, so with 6 rings there are two ways they could have hit the target as described. Actually, this works in general: If you make Hood hit a ring that's further out than his original set, you can balance it by moving one of Tuck's rings out by the same amount. Again, it turns out that there are no more examples with 6 or less rings.
With seven rings, things are different. The method described above gives two more examples: Hood can hit 1, 2 and 5 or 1, 3 and 4 for a total area of
1+3+9=1+5+7=13 while Tuck hits ring 7 which also has area
14. As well as this, we can bump up the number of rings they hit. Hood can hit 2, 3, 4 and 5 with total area
3+5+7+9=24 while Tuck hits 6 and 7 with total area
11+13=24. This also must be the first example where Hood hits 4 rings and Tuck hits 2 (if you move Hood's smallest ring in you find there's a ring that both Tuck and Hood must have hit). It's also the first example where Tuck and Hood hit a completely consecutive run of rings (with 3 rings for Hood, you always miss at least one before getting to a Tuck ring) and the second example where Hood and Tuck's rings are consecutive but a gap between is allowed.
The answers to the three questions are, then, as follows. What's the smallest number of rings required for
- There to be a solution? 5
- There to be 2 solutions? 6
- There to be two solutions where both Hood and Tuck hit a run of rings, missing none inbetween? 7
I found this question pretty interesting, not for the above solutions, but for the following, other question: What are the examples where both Tuck and Hood's rings are all consecutive, like with 2, 3, 4, 5 and 6, 7?
In this case, there's four runs of rings on the target: Small ones that Hood and Tuck both miss, ones Hood hits, ones Tuck hits and big ones that they both miss. Let's say that there's
i small ones that they both miss, that Hood hits
j and that Tuck hits
k. The total areas here are pretty easy to work out, since they're just the areas of big circles, minus the areas of smaller ones. The area that get missed is
i×i, Hood hits
(i+j)×(i+j)-i×i and Tuck hits
(i+j+k)×(i+j+k)-(i+j)×(i+j). We want Hood and Tuck to total the same, so we want:
(i+j)×(i+j)-i×i = (i+j+k)×(i+j+k)-(i+j)×(i+j)In fact, notice that
i+j is the biggest ring Hood hits and
i+j+k is the biggest ring Tuck hits, so let's make the equation simpler by setting
m=i+j and
n=i+j+k. Notice that we can re-arrange these as
j=m-i and
k=n-m, so we can work out
j and
k if we know
i,
m and
n. Anyway, we now want:
m×m - i×i = n×n - m×mOr in other words:
2×m×m = i×i + n×nAnd we need
i,
m and
n to be whole numbers with
0≤i<m<n. We'll not worry about the ineqations for now, so some of the values we get might not make sense in the context of the question at hand.
I'm going to switch to squared symbols now, so
a2 = a×a and
ab=a×b. An interesting observation is that we can divide both sides by
m2 to get:
(i÷m)2 + (n÷m)2 = 2If you know your geometry, you'll know that
x2+y2=2 is the equation you use to find if the co-ordinates
(x, y) represent a point on the circle of radius the square root of 2, centre
(0, 0). This works in reverse, too! If
x=p÷q and
y=r÷s then
p2+r2=2(q×s)2. That's pretty useful, as we now know that if we can find a point on the circle with co-ordinates
(p÷q, r÷s) then we can set
m=qs,
i=ps and
n=rq to get a solution to what we want to solve, and vice versa. So now we want a list of these
p,
q,
r and
s.
Notice that if we multiply or divide
p and
q by some number, we will multiply or divide
i,
m and
n by the same number. We can therefore assume that
p÷q and
r÷s are in their lowest terms (ie. you can't do any cancellation).
There's one pretty obvious point on the circle,
(1,1). It corresponds to
i=m=n, in other words where neither Tuck nor Hood hit anything at all. If you think about the situation a bit, it's pretty clear that lines coming out of
(1,1) (except vertical ones) are described by their gradient, and each line hits exactly one point on the circle other than
(1,1) (except for the tangent at that point). Let's calculate the gradient of a line from
(1,1) to
(p÷q, r÷s). It's equal to
(1-r÷s)÷(1-p÷q). Notice that this is a fraction whenever the point's co-ordinates are fractions and vice versa.
Let
a÷b be the gradient in its lowest terms so that the line hits the point
(p÷q,r÷s)=(1-bt,1-at). At what value of
t do we find this? In other words, can we write
p,
q,
r and
s in terms of
a and
b? The answer is when
(1-bt)2+(1-at)2=2, in other words when
(tb)2+(ta)2=2×(a+b)t. A bit of re-arrangement gives
t=2(a+b)÷(a2+b2). Notice that
p÷q=1-t=1-2b(a+b)÷(a2+b2)=(a2+b2-2b(a+b))÷(a2+b2) and similarly
r÷s=(a2+b2-2a(a+b))÷(a2+b2), so we can set
p=a2+b2-2b(a+b)r=a2+b2-2a(a+b)q=s=a2+b2A bit of fiddling shows that the two cases we ignored above (vertical line and tangent line) also fit into this schema, so all solutions come from values
a and
b in this way. I'm not going to explain the following analysis so deeply as it involves some number theory that I don't want to explain.
Suppose that
p÷q is not in lowest terms. Then
2b(a+b) has a prime common with
q=a2+b2. Let's assume
a+b=1 mod 2, so that this prime is not 2. Then
gcd(a(a+b),q) is nontrivial. Computing the greatest common denominator, we find this means
gcd(b(a-b),a(a+b)) is nontrivial. We know
gcd(a,b)=1, so this means
gcd(a,a-b) or
gcd(b,a+b) is nontrivial, both of which are contradictions. So the additional constraint of
a+b=1 mod 2 ensures the results are in lowest terms. Retrieving
i,
m and
n, we find:
i=ps=(a2+b2-2b(a+b))(a2+b2)m=qs=(a2+b2)2n=qr=(a2+b2-2a(a+b))(a2+b2)These are clearly not in their lowest terms; the reason is that we've multiplied through by
qs instead of
lcm(q,s). Doing this, we find:
i=p=a2+b2-2b(a+b)m=q=s=a2+b2n=r=a2+b2-2a(a+b)Back to those inequalities, we now need
a2+b2 ≥ 2b(a+b) and
2b(a+b) > 0 > 2a(a+b) to ensure the solution makes sense. If
a+b > 0 then
-b < a < 0 < b, otherwise the inequality is reversed. The first condition doesn't seem to simplify too well. To summarise everything, the complete set of distinct solutions is:
i=k(a2+b2-2b(a+b))m=k(a2+b2)n=k(a2+b2-2a(a+b))Where
k is a positive integer, and
a and
b satisfy:
gcd(a,b)=1,
a+b=1 mod 2,
-b < a < 0 < b or
-b > a > 0 > b, and
a2 ≥ 2ba+b2As a quick check, setting
a=1 and
b=-2 gives us the original example with
i=1,
m=5 and
n=7!
If you were paying attention, this should help you solve certain Project Euler problems, for example those that ask you for a list of Pythagorean triples.
