The Cayley math contest today

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.

2 thoughts on “The Cayley math contest today

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s