The Cayley math contest today

February 26, 2010

Today me and a few of my friends took the Cayley math contest. This is another University of Waterloo contest with 25 multiple choice problems and a time limit of 60 minutes.

I did not get the last problem, and did the second last problem incorrectly. Probably no medal for me, even if I answered everything else correctly.

I think the most challenging problem on this contest was the last one:

The numbers 0 to 9 are arranged in a circle in order (like a clock). Steve places a counter at 0. On his first move, he moves the counter 1^1 step clockwise (to 1). On the second move he moves it 2^2 steps (to 5). If this continues, what position will the counter be after 1234 moves?

My solution

It’s funny that I had thought there were 12 numbers on the circle, where there was actually 10. Probably because there was already a clock related problem earlier in the contest. It would be slightly easier with 10.

The diagram in the booklet looked something like this:

The problem is needlessly confusing. It really just wants you to find the value of this expression:

(\displaystyle\sum_{x=1}^{1234} x^x) \mod 10

So we’re basically looking for the last digit of the expression. We just have to keep track of the units digit as we go along.

In the list [1..1234] there are 123 numbers ending with 0, 123 ending with 5, 123 ending with 6, and so on. Also there are 124 ending with 1, 2, 3, and 4.

Now we construct a chart somewhat like this:

0 -> 0
1 -> 1
2 -> 4 -> 8 -> 6 -> 2
3 -> 9 -> 7 -> 1 -> 3
4 -> 6 -> 4
5 -> 5
6 -> 6
7 -> 9 -> 3 -> 1 -> 7
8 -> 4 -> 2 -> 6 -> 8
9 -> 1 -> 9

What we are doing here is taking each number from 0 to 9, and on each iteration multiplying the number and taking it units digit. When it comes back to the original number, the cycle repeats.

Take 17. When multiplying it by itself, you have 17 -> 289 -> 4913 -> 83521. This property holds for 27, 37, 1557, or any other number ending with 7.

What good is this for? Let’s find the units digit of 7^{500}. Since 7′s cycle has a length of 4, 7^{500} has the same units digit as 7^{496}, and so on, down to 7^0, which has a units digit of 1. So 7^{500} has a units digit of 1.

My process for determining the sum is: separate the numbers into groups by their unit digits, and tally up the individual sums by modular arithmetic. We will add them together to get the final result.

The tedious part

We are doing modular arithmetic not on the base, but on the exponent. Let’s start tallying up the digits:

Any number ending with 0 will not have any effect on the units digit.

Any number ending with 1 adds one to the units digit. There are 124 such numbers.

Any number ending with 5 adds 5 to the units digit. There are 123 such numbers, giving a total of 615.

Any number ending with 6 adds 6 to the units digit. There are 123 such numbers, giving a total of 738.

For numbers ending with 4, the exponent must also be ending with 4, and so even. Each even exponent adds 6 to the units digit, giving a total of 744 (there are 124 such numbers).

For numbers ending with 9, the exponent must also end with 9, and be odd. Each odd exponent adds 9 to the units digit, giving a total of 1107.

Because 1234 \mod 4 is 2, there are 309 numbers x where x \mod 4 = 1 and x \mod 4 = 2. Also there are 308 numbers x where x \mod 4 = 0 and x \mod 4 = 3.

This image is a little difficult to explain. The numbers at the top is the exponent mod 4. The numbers down the column with the red arrow are the bases.

Of the 124 numbers ending with 2, 62 of them are 0 when mod 4, and 62 of them are 2 when mod 4. The total for this is 62*6 + 62*4 = 620.

Of the 124 numbers ending with 3, 62 of them are 1 when mod 4, and 62 of them are 3 when mod 4. The total for this is 62*3 + 62*7 = 620.

Of the 123 numbers ending with 7, 62 of them are 1 when mod 4, and 61 of them are 3 when mod 4. The total for this is 62*3 + 61*4 = 613.

Of the 123 numbers ending with 8, 62 of them are 0 when mod 4, and 61 of them are 2 when mod 4. The total for this is 62*6 + 61*4 = 616.

Add up all the bolded numbers, and you should get 5797. We only care about the units digit, so the answer is 7.

This is a very tedious and error prone process. I think the official solution would be much neater.


A Geometry Exercise

February 22, 2010

This post was inspired by a problem I came across when studying for a math contest, namely problem 23 in the 2007 Cayley Contest.

I think this is an interesting problem because the solution is not so obvious, and there are several incorrect approaches that I’ve tried (and given up on). I’ve modified the problem slightly to make it more interesting.

Here we have a rectangle, ABCD. It’s rotated to the right by \theta degrees, using A as the pivot. This forms AEFG as the new rectangle. We are given x and y, we are asked to find the area of the shaded region.

Can you come up with a general formula for the area of the shaded region, using the given variables x, y, and \theta?

Solution

I will use the notation (ABC) to denote the area of triangle \triangle ABC.

The solution is to draw a line parallel to BC through E, the blue line. This splits the lower shaded area into two triangles: \triangle AXE and \triangle EYH, and a rectangle: BCYX.

Since ABCD is the same as AEFG, the top shaded area is the same as the bottom shaded area.

Let’s find the area of triangle \triangle AXE.

The angle \angle BAE is equal to \theta. Of course, AE is equal to y. Using some basic trigonometry, AX = y \cos \theta, XE = y \sin \theta, and BX = y - y \cos \theta. Now we know the area of triangle \triangle AXE:

\begin{array}{rcl} (AXE) &=& \frac{1}{2} (y \cos \theta) (y \sin \theta) \\ &=& \frac{1}{4} y^2 \sin(2 \theta)\end{array}

Next we find the area of \triangle EYH. EY = x - y \sin \theta, and using trigonometry again, HY = \tan \theta (x - y \sin \theta).

\begin{array}{rcl} (EYH) &=& \frac{1}{2} (x - y \sin \theta) [\tan \theta (x - y \sin \theta)] \\ &=& \frac{1}{2} (x - y\sin \theta)^2 \tan \theta \end{array}

Finally, for the rectangle BCYX:

\begin{array}{rcl} (BCYX) &=& x (y - y \cos \theta) \end{array}

Now we add all this up and simplify (T is total):

\begin{array}{rcl} T &=& 2[(AXE) + (EYH) + (BCYX)] \\ &=& 2[\frac{1}{4} y^2 \sin(2 \theta) + \frac{1}{2}(x - y \sin \theta)^2 \tan \theta + x (y - y \cos \theta)] \\ &=& \tan \theta (x^2+y^2) - 2xy (\sec \theta - 1)\end{array}

It’s rather tedious to get from the second to the last step, but Wolfram Alpha could do it for me.

Notice that we assume that EF intersects DC. If \theta is large enough, then EF would intersect AD, and this formula would no longer work.

Of course it would also fail if y is greater than x, so my formula works for only a rather limited range of values.


Follow

Get every new post delivered to your Inbox.

Join 73 other followers